Insertion

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

Insert At Beginning

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.

Update the Next Pointer

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

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.

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;
}

print("We're Working")

console.log("We're Working");

Insert At Position

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.

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.

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.

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.

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.

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;
}

print("We're Working")

console.log("We're Working");

Insertion At Tail

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.

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.

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.

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.

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;
}

print("We're Working")

console.log("We're Working");

Insertion

On this page