We have covered our basics in linked list and also covered various applications. It is the time to understand how insertion is performed on a linked list whether we need to insert node in the beginning of a linked list, insertion of node at a given specified location, as well as the insertion at the end of the node.
In this blog we will be covering entire insertion operations of linked list and some related interview questions that might help you to crack te software development roles in the job market.
What is a linked list data structure?
Linked List data structure is a linear data structure in which data is stored in the node which is of struct type and the next node contains the address of the next node in the sequence of a linked list.
There are different types of linked list which includes singly linked list, doubly linked lists as well as circular linked list data structure. The time complexity differs upon the operations performed on it.
Insertion in linked list from the beginning
To insert a node at the beginning of a linked list we first create a new node with the value we want to add. Then we make this new node point to the current first node of the list. After that we update the head of the list to this new node. Now this new node becomes the first element of the list. This is a quick and simple way to add elements at the front of a linked list.
C Implementation
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** headRef, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = *headRef;
*headRef = newNode;
}
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 30);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 10);
printList(head);
return 0;
}
C++ Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node(newData);
newNode->next = head;
head = newNode;
}
void printList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 100);
insertAtBeginning(head, 50);
insertAtBeginning(head, 25);
printList(head);
return 0;
}
Insertion in linked list at a specified location
To insert a node at a specific position in a linked list we first create a new node with the value we want to add. Then we move through the list to find the node just before the desired position. Once we are at the right spot, we make the new node point to the next node and then we update the previous node to point to the new node. This way the new node is placed exactly where we want in the list without breaking the chain.
C Implementation
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtPosition(struct Node** headRef, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (position == 1) {
newNode->next = *headRef;
*headRef = newNode;
return;
}
struct Node* temp = *headRef;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) return;
newNode->next = temp->next;
temp->next = newNode;
}
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtPosition(&head, 10, 1);
insertAtPosition(&head, 20, 2);
insertAtPosition(&head, 15, 2);
insertAtPosition(&head, 5, 1);
printList(head);
return 0;
}
C++ Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
void insertAtPosition(Node*& head, int data, int position) {
Node* newNode = new Node(data);
if (position == 1) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 1; i < position - 1 && temp != nullptr; i++) {
temp = temp->next;
}
if (temp == nullptr) return;
newNode->next = temp->next;
temp->next = newNode;
}
void printList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = nullptr;
insertAtPosition(head, 100, 1);
insertAtPosition(head, 200, 2);
insertAtPosition(head, 150, 2);
insertAtPosition(head, 50, 1);
printList(head);
return 0;
}
Insertion in linked list at the end
To insert a node at the end of a linked list we first create a new node with the value we want to add. If the list is empty, this new node becomes the first node. Otherwise we start from the head and move through the list until we reach the last node.
Then we have to make the last node point to our new node. This places the new node at the very end of the list, extending the chain.
C Implementation
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtEnd(struct Node** headRef, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*headRef == NULL) {
*headRef = newNode;
return;
}
struct Node* temp = *headRef;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
printList(head);
return 0;
}
C++ Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
void insertAtEnd(Node*& head, int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
void printList(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
int main() {
Node* head = nullptr;
insertAtEnd(head, 100);
insertAtEnd(head, 200);
insertAtEnd(head, 300);
printList(head);
return 0;
}
FAQs
What is a linked list?
A linked list is a data structure where each element called a node which points to the next one in the list.
What is insertion in a linked list?
Insertion means adding a new node to the list at the beginning, middle, or end.
How do you insert at the beginning?
Create a new node, point it to the current head and update head to this new node.
How do you insert at the end?
Create a new node then go to the last node and point its next to the new node.
What happens if we insert at position 1?
It is the same as inserting at the beginning where the new node becomes the head.
