Doubly Linked List
A doubly linked list is like a two-way street. Each node has two pointers: one to the next node and one to the previous node. This allows traversal in both directions and easier deletion.
Node Structure for Doubly Linked List
public class DNode {
int data;
DNode prev;
DNode next;
DNode(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
Basic Operations
public class DoublyLinkedList {
DNode head;
// Insert at beginning
public void insertAtHead(int data) {
DNode newNode = new DNode(data);
newNode.next = head;
if (head != null) head.prev = newNode;
head = newNode;
}
// Insert at end
public void insertAtEnd(int data) {
DNode newNode = new DNode(data);
if (head == null) {
head = newNode;
return;
}
DNode temp = head;
while (temp.next != null) temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
}
// Delete a node by value
public void delete(int key) {
if (head == null) return;
if (head.data == key) {
head = head.next;
if (head != null) head.prev = null;
return;
}
DNode temp = head;
while (temp != null && temp.data != key) {
temp = temp.next;
}
if (temp == null) return;
if (temp.prev != null) temp.prev.next = temp.next;
if (temp.next != null) temp.next.prev = temp.prev;
}
}
Two Minute Drill
- Doubly linked list has prev and next pointers.
- Allows bidirectional traversal.
- Insertion/deletion can be done with knowledge of node (no need to find previous).
- Uses extra memory for prev pointer.
- Used in browser history, undo functionality, etc.
Need more clarification?
Drop us an email at career@quipoinfotech.com