Insertion in Linked List

Inserting elements at different positions in a linked list, including at the beginning, end, and at specific positions

Insert At Beginning

1

Create a New Node

  • Allocate memory for a new node.
  • Set the data field of the new node to the given value.
2

Update the Next Pointer

  • Point the next field of the new node to the current head node (head).
3

Change the Head

  • Set the head of the list to the new node. The new node becomes the first node in the list.
  • The head pointer now points to the newly added node.
//insertatbeginning.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
    this->data = data;
    this->next = NULL;
}
};
void insertAtBeginning(Node * &head, int data)
{
Node *temp = new Node(data);
temp->next = head;
head = temp;
}
void display(Node* head){
while(head!=NULL){
    cout<<head->data<<" ";
    head=head->next;
}
 // 13->12->11->10
}
int main()
{
Node *head = NULL;
insertAtBeginning(head,10);
insertAtBeginning(head,11);
insertAtBeginning(head,12);
insertAtBeginning(head,13);
display(head);
}

Insert At Position

1

Check for Position `0`

  • If pos == 0, insert the new node at the beginning.
2

Create a New Node:

  • Allocate memory for a new node and set its data.
3

Traverse to Position

  • Start from the head and move to the (pos - 1)th node.
4

Update Pointers

  • Point the new node's next to the current node's next.
  • Update the current node's next to the new node.
5

Finish

  • The new node is inserted at the specified position.
//inseratposition.cpp
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
    this->data = data;
    this->next = NULL;
}
};
void insertAtBeginning(Node * &head, int data)
{
Node *temp = new Node(data);
temp->next = head;
head = temp;
}
void insertAtPosition(Node* &head,int data,int pos){
// If position is 0 then insert at beginning.
if(pos==0){
    insertAtBeginning(head,data);
    return;
}
Node* newNode=new Node(data);
Node* currNode=head;
int curr=0;
while(curr!=pos-1){
    currNode=currNode->next;
    curr++;
}
newNode->next=currNode->next;
currNode->next=newNode;
}
void display(Node* head){
while(head!=NULL){
    cout<<head->data<<" ";
    head=head->next;
}
//14->13->9->12->11->5->10 
}
int main(){
Node *head = NULL;
insertAtBeginning(head,10);
insertAtBeginning(head,11);
insertAtBeginning(head,12);
insertAtBeginning(head,13);
insertAtPosition(head,14,0);
insertAtPosition(head,9,2);
insertAtPosition(head,5,5);
display(head);
}

Insert At Tail

1

Check if the List is Empty

  • If the head is NULL, create a new node and make it the head.
2

Create a New Node

  • Allocate memory for a new node.
  • Assign the given data to the new node.
3

Link the New Node

  • Set the next pointer of the last node to the new node.
4

Finish

  • The new node is now the last node in the list.
// insertattail.cpp
#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
    this->data = data;
    this->next = NULL;
}
};
void insertAtTail(Node* &head,int data){
if(head==NULL){
    head= new Node(data);
    return;
}
Node *temp=new Node(data);
Node *curr=head;
while(curr->next){
    curr=curr->next;
}
curr->next=temp;
}
void display(Node* head){
while(head!=NULL){
    cout<<head->data<<" ";
    head=head->next;
}
// 1->2->3->4
}
int main()
{
Node *head = NULL;
insertAtTail(head,1);
insertAtTail(head,2);
insertAtTail(head,3);
insertAtTail(head,4);
display(head);
}