Question
What is the implementation of a doubly linked list in Java?
public class DoublyLinkedList {
Node head, tail;
static class Node {
int data;
Node prev, next;
Node(int d) {
data = d;
prev = next = null;
}
}
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
head.prev = null;
tail.next = null;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
tail.next = null;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
}
Answer
A doubly linked list is a type of linked list in which each node contains a reference to both the next node and the previous node in the sequence. This allows for traversal in both directions—forward and backward. In this guide, I will provide a Java implementation of a doubly linked list, including methods for adding nodes and displaying the list.
public class DoublyLinkedList {
Node head, tail;
static class Node {
int data;
Node prev, next;
Node(int d) {
data = d;
prev = next = null;
}
}
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
head.prev = null;
tail.next = null;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
tail.next = null;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
}
Causes
- Need for bidirectional traversal in data structures.
- Ability to efficiently insert and delete nodes from both ends.
Solutions
- Utilize a class to define the structure of nodes containing pointers to both next and previous nodes.
- Implement methods for various operations like insertion, deletion, and traversal.
Common Mistakes
Mistake: Not properly setting previous and next pointers for new nodes.
Solution: Always ensure that the new node's previous pointer points to the last node and the last node's next pointer points to the new node.
Mistake: Forgetting to handle edge cases, such as inserting into an empty list.
Solution: Implement checks for head and tail nodes to manage the list's state appropriately.
Helpers
- Doubly Linked List in Java
- Java Data Structures
- Java Linked List Implementation
- Bidirectional Linked List in Java
