WikiGalaxy
Doubly Linked List Operations
Introduction:
A doubly linked list is a type of linked list in which each node contains a data part and two pointers: one pointing to the next node and another pointing to the previous node. This structure allows traversal in both directions.
Step 1: Initialize an empty list.
[Null] <-> [Null]
Step 2: Insert the first element.
[Null] <-> [Data | Null]
Step 3: Insert additional elements.
[Null] <-> [Data | Next] <-> [Data | Next] <-> [Data | Null]
Step 4: Traverse the list from start to end and end to start.
Forward: Head -> [Data] -> [Data] -> Tail
Backward: Tail -> [Data] -> [Data] -> Head
Example 1: Insertion at the Beginning
The new node is inserted before the head, and the head pointer is updated.
class Node {
int data;
Node prev;
Node next;
Node(int d) { data = d; }
}
class DoublyLinkedList {
Node head;
void insertAtBeginning(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
}
}
Example 2: Insertion at the End
The new node is appended after the last node, and the last node's next pointer is updated.
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;
}
Example 3: Insertion After a Given Node
The new node is inserted after the specified node, adjusting the pointers accordingly.
void insertAfter(Node prevNode, int newData) {
if (prevNode == null) {
System.out.println("Previous node cannot be 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;
}
}
Example 4: Deletion of a Node
The specified node is removed, and the pointers of the adjacent nodes are updated.
void deleteNode(Node del) {
if (head == null || del == null) {
return;
}
if (head == del) {
head = del.next;
}
if (del.next != null) {
del.next.prev = del.prev;
}
if (del.prev != null) {
del.prev.next = del.next;
}
}
Example 5: Traversing Forward
Traverse the list from head to tail, printing each node's data.
void printList() {
Node node = head;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
Example 6: Traversing Backward
Start from the last node and traverse back to the head, printing each node's data.
void printReverse() {
Node last = null;
Node node = head;
while (node != null) {
last = node;
node = node.next;
}
while (last != null) {
System.out.print(last.data + " ");
last = last.prev;
}
}
Example 7: Searching for a Node
Traverse the list to find a node with the specified data.
boolean searchNode(int key) {
Node node = head;
while (node != null) {
if (node.data == key) {
return true;
}
node = node.next;
}
return false;
}
Example 8: Updating a Node's Data
Locate the node with the target data and update it with new data.
boolean updateNode(int oldData, int newData) {
Node node = head;
while (node != null) {
if (node.data == oldData) {
node.data = newData;
return true;
}
node = node.next;
}
return false;
}
Example 9: Counting the Number of Nodes
Traverse the list and count the total number of nodes present.
int countNodes() {
int count = 0;
Node node = head;
while (node != null) {
count++;
node = node.next;
}
return count;
}
Example 10: Reversing the Doubly Linked List
Reverse the pointers of the list to change its direction.
void reverse() {
Node temp = null;
Node current = head;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}
