Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

We introduced linked lists in the last article. We also create a simple linked list with three nodes and discuss list traversal. All of the programs discussed in this article consider the following linked list representation.

// a list node
class Node
{
	public:
	int data;
	Node *next;
};
Copy the code

In this article, we discussed the method of inserting new nodes into linked lists. Nodes can be added in three ways: 1) at the beginning of the linked list and 2) after a given node. 3) At the end of the list.

Add a node in front :(4-step process) new nodes are always added before the head of a given linked list. And the newly added node becomes the new head of the linked list. For example, if the given list is 10->15->20->25 and we add an item 5 in front of it, the list becomes 5->10->15->20->25. Let’s call the function added to the front of the list is push(). Push () must receive a pointer to a header pointer because push must change the header pointer to point to the new node

Here are the four steps to add a node earlier.

/* Insert a new node in front of the list given a reference to the head of the list (a pointer to a pointer) and an int. * /
void push(Node** head_ref, int new_data)
{
	/* 1. Allocate nodes */
	Node* new_node = new Node(a);/* 2. Add data */
	new_node->data = new_data;

	/* 3. Use the next node of the new node as the head */
	new_node->next = (*head_ref);

	/* 4. Move the header to point to the new node */
	(*head_ref) = new_node;
}
Copy the code

The time complexity of push() is O(1) because the amount of work it does is constant. Add a node after the given node :(5 step procedure) we get a pointer to the node and insert the new node after the given node.

// Insert a new prev_node after the given prev_node
void insertAfter(Node* prev_node, int new_data)
{

	If (prev_node == NULL)
	{
		cout << "The previous node given cannot be NULL";
		return;
	}

	// 2. Assign a new node
	Node* new_node = new Node(a);// 3. Add data
	new_node->data = new_data;

	// 4. Set the next of the new node to prev_node
	new_node->next = prev_node->next;

	// 5. Move the next prev_node to new_node
	prev_node->next = new_node;
}
Copy the code

The time complexity of insertAfter() is O(1) because the amount of work it does is constant.

Add a node last :(6-step process) new nodes are always added after the last node in a given linked list. For example, if the given list is 5->10->15->20->25 and we add an item 30 at the end, the list becomes 5->10->15->20->25- > 30. Since a linked list is usually represented by its head, we must traverse the list to the end, and then change the penultimate node to the new node.

Here are the six final steps to add a node.

// Given a reference to the head of the list (a pointer to a pointer) and an int, append a new node to the end
void append(Node** head_ref, int new_data)
{

	// 1. Allocate nodes
	Node* new_node = new Node(a);// Used in Step 5
	Node *last = *head_ref;

	// 2. Add data
	new_node->data = new_data;

	// 3. This new node will be the last node, so set its next to NULL
	new_node->next = NULL;

	// 4. If the list is empty, start with a new node
	if (*head_ref == NULL)
	{
		*head_ref = new_node;
		return;
	}

	// 5. else iterate through to the last node
	while(last->next ! =NULL)
		last = last->next;

	// 6. Change the next node of the last node
	last->next = new_node;
	return;
}
Copy the code

The time complexity of append is O(n), where n is the number of nodes in the list. Since there is a loop from beginning to end, the function performs O(n) work. By keeping an extra pointer to the end of the list /

Here is a complete program that uses all of the above methods to create a linked list.

#include <bits/stdc++.h>
using namespace std;
class Node
{
	public:
	int data;
	Node *next;
};

void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; }void insertAfter(Node* prev_node, int new_data)
{
	if (prev_node == NULL)
	{
		cout<<"The previous node given cannot be NULL";
		return;
	}
	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; }void append(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); Node *last = *head_ref; new_node->data = new_data; new_node->next =NULL;

	if (*head_ref == NULL)
	{
		*head_ref = new_node;
		return;
	}
	while(last->next ! =NULL)
		last = last->next;
	last->next = new_node;
	return;
}
void printList(Node *node)
{
	while(node ! =NULL)
	{
		cout<<""<<node->data; node = node->next; }}int main(a)
{
	Node* head = NULL;
	append(&head, 6);
	push(&head, 7);
	push(&head, 1);
	append(&head, 4);
	insertAfter(head->next, 8);
	
	cout<<The linked list created is:;
	printList(head);
	
	return 0;
}
Copy the code

Output:

The linked list created is:1 7 8 6 4
Copy the code

🥇 past quality articles

Teach you make a small game gobang in Java Single AI minesweeping game using the python list of singly linked list data structure is introduced | first set of singly linked list data structure in the linked list and an array of | a second taught you how to use python snake game Taught you how to use Java AWT Make a great weather Web application using HTML, CSS, JS and apis

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.