Menu

Difference between singly and doubly linked lists

Difference between singly and doubly linked lists

Certainly! Let’s differentiate between singly and doubly linked lists:

1. Singly Linked List

  • In a singly linked list, each node contains a reference to the next node in the sequence.
  • Singly linked lists allow traversal in only one direction, from the head (first node) to the tail (last node).
  • Each node in a singly linked list stores data and a reference to the next node.
  • Singly linked lists are memory efficient as they require only one reference per node.

2. Doubly Linked List

  • In a doubly linked list, each node contains references to both the next node and the previous node in the sequence.
  • Doubly linked lists allow bidirectional traversal, meaning you can traverse the list both forward and backward.
  • Each node in a doubly linked list stores data, a reference to the next node, and a reference to the previous node.
  • Doubly linked lists require more memory compared to singly linked lists due to the additional reference to the previous node in each node.

singly and doubly linkedlists

Example
Example - Singly LinkedList:
java
class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SinglyLinkedListExample {
    public static void main(String[] args) {
        // Creating nodes
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        
        // Linking nodes
        head.next = second;
        second.next = third;
        
        // Traversing the list
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

Example
Example - Doubly LinkedList:
java
class Node {
    int data;
    Node next;
    Node prev;
    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

public class DoublyLinkedListExample {
    public static void main(String[] args) {
        // Creating nodes
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        
        // Linking nodes forward
        head.next = second;
        second.next = third;
        
        // Linking nodes backward
        second.prev = head;
        third.prev = second;
        
        // Traversing forward
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
        
        // Traversing backward
        current = third;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
    }
}

Singly and Doubly linked lists Examples

In the examples above, we demonstrate the implementation of singly and doubly linked lists in Java. In a singly linked list, each node (Node) has a reference to the next node (next), allowing traversal only in one direction. In a doubly linked list, each node has references to both the next node (next) and the previous node (prev), enabling bidirectional traversal.

Homepage

Readmore