WikiGalaxy
Insertion in Doubly Linked List
Introduction:
A doubly linked list is a type of linked list where each node contains a data part and two pointers, one pointing to the next node and the other pointing to the previous node. This allows traversal in both directions.
Insertion at the Beginning:
To insert a new node at the beginning of a doubly linked list, we need to adjust the pointers of the new node and the head node accordingly.
Insertion at the End:
Inserting at the end involves traversing to the last node and updating the pointers of the last node and the new node.
Insertion After a Given Node:
To insert after a given node, the pointers of the new node and the existing nodes need to be adjusted to maintain the list structure.
Step 1: Diagram for Insertion at the Beginning
[New Head] <-> [Old Head] <-> [Node 3] <-> [Node 4]
Step 2: Diagram for Insertion at the End
[Node 1] <-> [Node 2] <-> [Node 3] <-> [New Tail]
Step 3: Diagram for Insertion After a Given Node
[Node 1] <-> [Node 2] <-> [Given Node] <-> [New Node] <-> [Node 4]
class Node {
int data;
Node prev;
Node next;
Node(int d) { data = d; }
}
class DoublyLinkedList {
Node head;
// Insert at the beginning
public void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
if (head != null) head.prev = newNode;
head = newNode;
}
// Insert at the end
public void insertAtEnd(int newData) {
Node newNode = new Node(newData);
if (head == null) {
head = newNode;
return;
}
Node last = head;
while (last.next != null) last = last.next;
last.next = newNode;
newNode.prev = last;
}
// Insert after a given node
public void insertAfter(Node prevNode, int newData) {
if (prevNode == null) return;
Node newNode = new Node(newData);
newNode.next = prevNode.next;
prevNode.next = newNode;
newNode.prev = prevNode;
if (newNode.next != null) newNode.next.prev = newNode;
}
}
Detailed Explanation of Code:
The above code demonstrates how to perform insertions in a doubly linked list. Each method handles a different insertion scenario, ensuring that the pointers are properly updated to maintain the list's integrity.
