A singly linked list is a data structure of nodes in which every previous node has a reference to the next node. Here’s a simple implementation of a singly linked list in Java.

class Node {
  Node next = null;
  int data;

  public Node(int val) {
    data = val;
  }
}

class LinkedList {
  Node head = null;

  ...

  public append(int val) {
    if(head == null) {
      head = new Node(val);
    }
    else {
      Node n = head;
      while(n.next != null) {
        n = n.next;
      }

      n.next = new Node(val);
    }
  }
}

In the above implementation, it only keeps track of the head of the list. Therefore, whenever we want to append a new node, we need to traverse the whole list to get to the tail node and it costs O(n) time. To reduce this, often we have a ‘tail’ reference pointing to the last node in the list. This reduces the append time to O(1).

// LinkedList with tail reference
class LinkedList {
  Node head = null;
  Node tail = null;
  
  ...

  public append(int val) {
    if(tail == null) {
      head = new Node(val);
      tail = head;
    }
    else {
      tail.next = new Node(val);
      tail = tail.next;
    }
  }
}

However, if we need to insert a node after a specific node. We still need O(n) time to search that node.

class LinkedList {
  
  ...

  public void insertAfter(Node node, int val) {

    if(head == null)
      return;

    Node n = head;
    while(n != null) {
      if(n == node) {
        Node oldNext = n.next;
        Node newNode = new Node(val);
        n.next = newNode;
        newNode.next = oldNext;

        if(newNode.next == null)
          tail = newNode;

        break;
      }
      n = n.next;
    }
  }
}

Deleting a node is similar to inserting a node. After deleting the node, we need to connect the previous node to the next node. To get the previous node, we need to search the node from the head of the list because there’s no reference to it.

Double Linked List

Double linked list could solve the issue easily. For every node in a double linked list, except from the next node reference, there’s another node reference pointing to the previous node.

class Node {
  Node next = null;
  Node previous = null;

  public Node(int d) {
    data = d;
  }
}

class DoubleLinkedList {
  
  ...

  public void insertAfter(Node node,
    int val) {

    if(node == null) {
      return;
    }

    Node newNode = new Node(val);

    newNode.next = node.next;
    newNode.previous = node;
    node.next = newNode;
  }

  public void delete(Node node) {
    if(node == null) {
      return;
    }

    // if the node is the head
    if(node.previous == null) {
      head = node.next;
    }

    // if the node is the tail
    if(node.next == null) {
      tail = node.previous;
    }

    if(node.previous != null) {
      node.previous.next 
        = node.next;
    }

    if(node.next != null) {
      node.next.previous 
        = node.previous;
    }
  }
}

Obviously both the delete and insertAfter methods have O(1) time performance. Overall, double linked list is more flexible than singly linked list.

RelatedPost