This post will show you how to insert nodes to start and end of a linked list in C++. The head of a linked list points to the start element of the list and the last element points to NULL.
Each element or node of the linked list that we are going to implement here can hold the value of an integer. We will write one program that will take one integer value from the user and based on user input, it will insert it to start or to end. Also, we can print all values of the list.
Node structure :
We will use one structure create the node. It looks as like below :
struct Node
{
int value;
Node *next;
};It can hold one integer value and one address of another node. Each node points to its next node. The pointer is used to hold the address of the next node. The last node holds NULL in this pointer variable.
Inserting a node at head :
The head pointer points to the starting node of the linked list. To insert a new node at head, we must point the head to this new node and point the new node to the old start node.
Node *node = new Node;
node->value = value;
if (head == NULL)
{
node->next = NULL;
}
else
{
node->next = head;
}
head = node;- Create one new Node
- If head is NULL, i.e. the linked list is empty, point the new node to NULL.
- Else, point the new node to the head node.
- Point head to the new node
Inserting a node at end :
This is almost similar to the above example. To insert a node at the end, traverse to the last node, point the last node to the new node and point the new node to NULL.
Node *node = new Node;
node->value = value;
node->next = NULL;
Node *flag = head;
while (flag->next != NULL)
{
flag = flag->next;
}
flag->next = node;We are using one while loop to traverse to the last node and then inserting the node. Note that we are using a different pointer variable to do the traversal.
Display a linked list :
To display one linked list, we need to use one loop. Starting from the head node, traverse to the last node, i.e. to the node that points to NULL.
Node *flag = head;
while (flag != NULL)
{
cout << "->"<<flag->value;
flag = flag->next;
}
cout<<endl;Complete C++ program :
Let’s write the complete C++ program.
#include <iostream>
using namespace std;
struct Node
{
int value;
Node *next;
};
class LinkedList
{
Node *head = NULL;
public:
void insertAtHead(int value)
{
Node *node = new Node;
node->value = value;
if (head == NULL)
{
node->next = NULL;
}
else
{
node->next = head;
}
head = node;
}
void insertAtEnd(int value)
{
Node *node = new Node;
node->value = value;
node->next = NULL;
Node *flag = head;
while (flag->next != NULL)
{
flag = flag->next;
}
flag->next = node;
}
void displayList()
{
Node *flag = head;
while (flag != NULL)
{
cout << "->" << flag->value;
flag = flag->next;
}
cout << endl;
}
};
int main()
{
int choice, value;
LinkedList linkedList;
while (1)
{
int exit = 0;
cout << "Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :" << endl;
cin >> choice;
switch (choice)
{
case -1:
exit = 1;
break;
case 1:
cout << "Enter a value :" << endl;
cin >> value;
linkedList.insertAtHead(value);
break;
case 2:
cout << "Enter a value :" << endl;
cin >> value;
linkedList.insertAtEnd(value);
break;
case 3:
linkedList.displayList();
break;
}
if (exit == 1)
{
break;
}
}
return 0;
}- LinkedList class is used to hold all linked list related methods.
- We are using one while loop that runs infinitely and takes the user input repeatedly.
Sample Output : **
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
1
Enter a value :
10
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
1
Enter a value :
12
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
1
(base) ➜ c++ ./example
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
1
Enter a value :
10
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
1
Enter a value :
11
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
1
Enter a value :
12
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
3
->12->11->10
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
2
Enter a value :
9
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
2
Enter a value :
8
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
2
Enter a value :
7
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
3
->12->11->10->9->8->7
Enter 1 to add node to the beginning, 2 to add to the end, 3 to print the linked list & -1 to exit :
-1