Introduction to Doubly Linked List in Data Structure
Doubly Linked List stand as a fundamental data structure in computer science, offering enhanced functionality compared to their singly linked counterparts. In this comprehensive introduction, we delve into the intricacies of doubly linked list, exploring their structure, operations, and real-world applications.
Unlike singly linked lists, doubly linked list feature nodes with two pointers, allowing traversal both forwards and backwards. This bidirectional traversal capability empowers efficient insertion, deletion, and searching operations within the list, making doubly linked list a versatile tool in various programming scenarios.
Doubly linked list program in data structure
Here’s a basic implementation of a Doubly Linked List in Java:
public class DoublyLinkedList {
// Node class representing each element of the linked list
private static class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// Head and tail pointers of the doubly linked list
private Node head;
private Node tail;
// Constructor to initialize an empty doubly linked list
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
// Method to check if the doubly linked list is empty
public boolean isEmpty() {
return head == null;
}
// Method to insert a node at the beginning of the doubly linked list
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
// Method to insert a node at the end of the doubly linked list
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// Method to display the doubly linked list in forward direction
public void displayForward() {
if (isEmpty()) {
System.out.println("Doubly linked list is empty");
return;
}
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// Method to display the doubly linked list in backward direction
public void displayBackward() {
if (isEmpty()) {
System.out.println("Doubly linked list is empty");
return;
}
Node current = tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
System.out.println();
}
// Main method for testing the implementation
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertAtBeginning(10);
dll.insertAtEnd(20);
dll.insertAtBeginning(5);
dll.insertAtEnd(30);
System.out.println("Doubly Linked List in forward direction:");
dll.displayForward();
System.out.println("Doubly Linked List in backward direction:");
dll.displayBackward();
}
}
Singly Linked List: Explained, Examples, and Applications
Exploring the Efficiency and Applications of Circular Linked List
