Insertion in Doubly Linked List

Inserting elements at different positions in a doubly 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.

  • Initialize the prev and next fields of the new node to NULL.

2

Update the Next Pointer

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

Update the Prev Pointer of the Current Head (if it exists)

  • If the current head is not NULL, set the prev field of the current head node to the new node.
4

*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;
struct Node {
int data;
Node* prev;
Node* next;

Node(int d) { 
  data = d; 
  prev = next = NULL;
}
};
Node* insertBegin(Node* head, int data) {
Node* newNode = new Node(data);
newNode->next = head;
if (head != NULL) {
    head->prev = newNode;
}
return newNode;
}
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->next;
}
cout << "\n";
}

int main() {
Node* head = new Node(2);
Node* second = new Node(3);
Node* third = new Node(4);
head->next = second;
second->prev = head;
second->next = third;
third->prev = second;

cout << "Original Linked List: ";
printList(head);
head = insertBegin(head, 1);

cout << "After inserting at beginning: ";
printList(head);

return 0;
}

Insert At Position

1

Create a New Node

  • Allocate memory for a new node.

  • Set the data field of the new node to new_data.

  • Initialize the prev and next fields of the new node to NULL.

2

Check for Insertion at the Beginning

  • If pos == 1:

  • Set the next field of the new node to the current head.

  • If the head is not NULL, set the prev field of the current head to the new node.

  • Update the head to point to the new node.

  • Return the updated head.

3

Traverse to the Desired Position

  • Initialize a pointer curr to the head.

  • Iterate through the list for pos - 1 steps or until curr becomes NULL.

4

Check for Valid Position

  • If curr is NULL before reaching the desired position, print an error message and exit the function. The position is out of bounds.
5

Insert the New Node

  • Set the prev field of the new node to curr.

  • Set the next field of the new node to curr->next.

  • Update curr->next to point to the new node.

  • If the new node is not being inserted at the end, update the prev field of the node following the new node to point to the new node.

6

Return the Updated Head

  • Return the head pointer after insertion.
//inseratposition.cpp
#include <iostream>
using namespace std;

struct Node {
int data;
Node *next, *prev;

Node(int new_data) {
    data = new_data;
    next = prev = nullptr;
}
};
Node *insertAtPosition(Node *head, int pos, int new_data) {
Node *newNode = new Node(new_data);
if (pos == 1) {
    newNode->next = head;
    if (head != NULL)
        head->prev = newNode;
    head = newNode;
    return head;
}
Node *curr = head;
for (int i = 1; i < pos - 1 && curr != NULL; ++i) {
    curr = curr->next;
}
if (curr == NULL) {
    cout << "Position is out of bounds." << endl;
    delete newNode;
    return head;
}
newNode->prev = curr;
newNode->next = curr->next;
curr->next = newNode;
if (newNode->next != NULL)
    newNode->next->prev = newNode;
return head;
}

void display(Node *head) {
Node *curr = head;
while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->next;
}
cout << endl;
}

int main() {
Node *head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(4);
head->next->next->prev = head->next;

cout << "Original Linked List: ";
display(head);

cout << "Inserting 3 at position 3: ";
int data = 3;
int pos = 3;
head = insertAtPosition(head, pos, data);

display(head);

return 0;
}

Insertion At Tail

1

Create a New Node

  • Allocate memory for the new node.

  • Set the data field of the new node to new_data.

  • Initialize the next and prev fields of the new node to NULL.

2

Check if the List is Empty

  • If head == NULL, set the head pointer to the new node (as it will be the only node in the list).

  • Return the updated head.

3

Traverse to the End of the List

  • Initialize a pointer curr to the head of the list.
  • Move curr through the list by following the next pointer until curr->next == NULL.
4

Insert the New Node at the End

  • Set the next pointer of the last node (curr) to the new node.
  • Set the prev pointer of the new node to curr.
5

Return the Updated Head

  • Return the head pointer after insertion.
// insertattail.cpp
#include <iostream>
using namespace std;

struct Node {
int data;
Node *next, *prev;

Node(int new_data) {
    data = new_data;
    next = prev = nullptr;
}
};
Node *insertEnd(Node *head, int new_data) {
Node *newNode = new Node(new_data);
if (head == NULL) {
    head = newNode;
}
else {
      Node *curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = newNode;
    newNode->prev = curr;
}
return head;
}

void display(Node *head) {
Node *curr = head;
while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->next;
}
cout << endl;
}

int main() {
Node *head = new Node(1);
head->next = new Node(2);
head->next->prev = head;
head->next->next = new Node(3);
head->next->next->prev = head->next;

cout << "Original Linked List: ";
display(head);

cout << "Inserting 4 at the end: ";
int data = 4;
head = insertEnd(head, data);

display(head);

return 0;
}