Singly Linked List vs Doubly Linked List - Internet Class

Table of Contents

• Introduction
• Singly Linked List (SLL) with example
• Doubly Linked List (DLL) with example 

Introduction

A singly linked list is a linear data structure that consists of a sequence of nodes, where each node stores a reference to an element and a reference to the next node in the sequence. The reference to the next node is called a "link". The last node in the list has a link to null, indicating the end of the list.

A doubly linked list is a linear data structure that consists of a sequence of nodes, where each node stores a reference to an element and references to the previous and next nodes in the sequence. The reference to the previous node is called the "back link" and the reference to the next node is called the "forward link". The first and last nodes in the list have null references for their back and forward links, respectively.

Singly Linked List (SLL) with example

A singly linked list is a linear data structure that consists of a set of nodes that are linked together in a sequence. Each node in a singly linked list has a data field and a single pointer that points to the next node in the list. This allows for forward traversal of the list, but not backward traversal.

Here is an example of a singly linked list class in Java:

    public class SinglyLinkedList {
 
    private Node head;  // head node of the list
 
    // Node inner class to represent a node in the list
    private class Node {
        private int data;
        private Node next;
 
        public Node(int data) {
            this.data = data;
        }
    }
 
    // method to add a new node at the beginning of the list
    public void addFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
 
    // method to add a new node at the end of the list
    public void addLast(int data) {
        Node newNode = new Node(data);
 
        if (head == null) {
            head = newNode;
            return;
        }
 
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
 
    // method to remove the first node from the list
    public void removeFirst() {
        if (head == null) {
            return;
        }
        head = head.next;
    }
 
    // method to remove the last node from the list
    public void removeLast() {
        if (head == null) {
            return;
        }
 
        if (head.next == null) {
            head = null;
            return;
        }
 
        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        current.next = null;
    }
 
    // method to check if the list is empty
    public boolean isEmpty() {
        return head == null;
    }
 
    // method to get the size of the list
    public int size() {
        int size = 0;
        Node current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        return size;
    }
 
    // method to print the list
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

      

To use this singly linked list, you can create an instance of the SinglyLinkedList class and call its methods to add, remove, or retrieve elements from the list. For example:

SinglyLinkedList list = new SinglyLinkedList();
list.addFirst(10);
list.addLast(20);
list.addLast(30);
System.out.println("Size: " + list.size());  // Output: Size: 3
System.out.print("List: ");
list.printList();  // Output: List: 10

      

Doubly Linked List (DLL) with example

A doubly linked list is a linear data structure that consists of a set of nodes that are linked together in a sequence. Each node in a doubly linked list has a data field and two pointers: one that points to the previous node in the list and one that points to the next node in the list. This allows for bidirectional traversal of the list.

Here is an example of a doubly linked list class in Java:

      class DoublyLinkedList {
  private static class Node {
    int data;
    Node next;
    Node prev;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node head;
  private Node tail;
  private int size;

  public void addFirst(int data) {
    Node node = new Node(data);
    if (isEmpty()) {
      head = tail = node;
    } else {
      head.prev = node;
      node.next = head;
      head = node;
    }
    size++;
  }

  public void addLast(int data) {
    Node node = new Node(data);
    if (isEmpty()) {
      head = tail = node;
    } else {
      tail.next = node;
      node.prev = tail;
      tail = node;
    }
    size++;
  }

  public int removeFirst() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    int data = head.data;
    head = head.next;
    if (head == null) {
      tail = null;
    } else {
      head.prev = null;
    }
    size--;
    return data;
  }

  public int removeLast() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    int data = tail.data;
    tail = tail.prev;
    if (tail == null) {
      head = null;
    } else {
      tail.next = null;
    }
    size--;
    return data;
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }
}

      

To use this doubly linked list class, you can create an instance of it and add elements to the list using the addFirst and addLast methods. You can remove elements from the list using the removeFirst and removeLast methods. You can check the size of the list using the size method and check if the list is empty using the isEmpty method.

For example:

DoublyLinkedList list = new DoublyLinkedList();
list.addFirst(10);
list.addFirst(20);
list.addLast(30);
list.addLast(40);
System.out.println(list.size());  // Output: 4
System.out.println(list.isEmpty());  // Output: false
int first = list.removeFirst();
System.out.println(first);  // Output: 20
int last = list.removeLast();
System.out.println(last);  // Output: 40
 

There are a few key differences between singly linked lists and doubly linked lists:

• Doubly linked lists have an extra link (the back link) for each node, which allows for faster insertion and deletion of elements.
• Singly linked lists can only be traversed in one direction (from the head to the tail), while doubly linked lists can be traversed in both directions.
• Doubly linked lists use more memory than singly linked lists because of the extra link in each node.
• Singly linked lists are simpler to implement than doubly linked lists because they do not require the extra link.
• In terms of performance, doubly linked lists are generally faster than singly linked lists for insertion and deletion operations. However, they are slower for traversal because they require two pointers to be followed instead of just one. Singly linked lists are generally faster for traversal, but they are slower for insertion and deletion because they require more updates to the list structure.
• It is important to choose the appropriate data structure for the task at hand. If you need fast insertion and deletion, a doubly linked list might be a good choice. If you need fast traversal, a singly linked list might be a better choice.