WikiGalaxy
Introduction to Doubly Linked List
Concept Overview:
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 another pointing to the previous node in the sequence. This structure allows for traversal in both directions, forward and backward.
Key Characteristics:
- Each node has two links: one to the next node and one to the previous node.
- Allows bidirectional traversal.
- More complex to implement than singly linked lists due to the additional pointer.
Use Cases:
- Implementing browser history that allows moving back and forth.
- Navigating through a music playlist forwards and backwards.
Step 1: Initialize the list with a head node.
[Head] <-> [Node1] <-> [Node2] <-> [Node3] <-> [Tail]
Step 2: Traversal can be done both ways:
Forward: Head -> Node1 -> Node2 -> Node3 -> Tail
Backward: Tail -> Node3 -> Node2 -> Node1 -> Head
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
Node(int d) { data = d; }
}
public class DoublyLinkedList {
Node head;
// Adding a node at the front of the list
public void push(int new_data) {
Node new_Node = new Node(new_data);
new_Node.next = head;
new_Node.prev = null;
if (head != null)
head.prev = new_Node;
head = new_Node;
}
// Printing the list
public void printList(Node node) {
Node last = null;
System.out.println("Traversal in forward direction");
while (node != null) {
System.out.print(node.data + " ");
last = node;
node = node.next;
}
System.out.println();
System.out.println("Traversal in reverse direction");
while (last != null) {
System.out.print(last.data + " ");
last = last.prev;
}
}
}
Detailed Explanation of Code:
The code defines a `Node` class with three fields: `data`, `prev`, and `next`. The `DoublyLinkedList` class manages the nodes and provides methods to add a node to the front and print the list in both forward and reverse directions.
Adding Nodes:
The `push` method inserts a new node at the beginning, updating pointers to maintain the doubly linked structure.
Traversal:
The `printList` method demonstrates traversal from the head to the tail and then back to the head, showcasing the bidirectional nature of the list.
Console Output:
Traversal in forward direction
3 2 1
Traversal in reverse direction
1 2 3
