Linked List Data Structure

Intro

Linked List is a special type of data structure where elements besides holding data, have pointers.
The element can have up to two pointers.

In Linked List, elements are not stored in a contiguous order in memory, like with Arrays. The elements are spread around in memory and each element has a pointer to the element next to each other, which makes traversing the Linked List easier since we just need to follow the pointers.

We have two types of Linked Lists:

1. Singly Linked List
2. Doubly Linked List

In Singly Linked List, the element can have a pointer to the previous element or to the next element. It depends on how we build and construct the list itself.
In Doubly Linked List, the element has a pointer to the previous element and to the next element.

Here is one good illustration of both types of Linked Lists:

As you can see, the first element in the Linked List is considered as head and the last element is considered as the tail of a list.

Linked List - custom implementation in Java

Let's build our own Linked List from scratch.

First, let's prepare the basic structure. We need a class that represents the Singly Linked List and a class that represents an element - called node.

public class LinkedList<T> {

  public Node<T> head;
  private int size;

  public LinkedList() {
    this.root = null;
    this.size = 0;
  }

}

class Node<T> {

  public T data;
  public Node next;

  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}

We need to track what is the head node at all times and also it is useful to keep track of the size.

Let's create a method for adding an element at the end of the list:

public void addAtEnd(T data) {
  Node<T> nodeToAdd = new Node<>(data);

  // if head is null - that means the list is empty, so add the new node as a root
  if (head == null) {
    head = nodeToAdd;
  } else {

    Node<T> current = head;

    // traverse the list until we get to the tail - the node which next pointer is null
    while (current.next != null) {
      current = current.next;
    }

    // set the new node as a new tail
    current.next = nodeToAdd;
  }

  size++;
}

You see, for most of the operations, we need to traverse the list using pointers (node.next) to get to the desired position/element.

Now, let's see how we can add an element at a given position:

public void add(int index, T data) {
  Node<T> nodeToAdd = new Node<>(data);
  int i = 0;

  // check if provided index is valid
  if(index < 0 || index > size + 1) {
    throw new IllegalArgumentException("Invalid index");
  }

  if(index == 0 && head == null) {
    add(data);
  }

  if(index == 0) {
    nodeToAdd.next = head;
    head = nodeToAdd;
  } else {

    Node<T> current = head;

    // traverse until we get to the index - 1
    while(i < index - 1) {
      current = current.next;
      i++;
    }

    // set nodeToAdd.next to the node that the current node is currently pointing to
    nodeToAdd.next = (Node<T>) current.next;
    // set the current node to point to the new node - nodeToAdd
    current.next = nodeToAdd;

  }
  size++;
}

Here, inside the while loop, we are iterating until we get to the node that is placed one position before the provided index.

When we get to the element that should now point to the new node, we stop and set the pointers accordingly.

Method for adding node at the start of the list:

public void addAtStart(T data) {
  Node<T> nodeToAdd = new Node<>(data);
  nodeToAdd.next = head;
  head = nodeToAdd;
  size++;
}

Now, let's create a method for removing an element at the start of the array:

public T removeAtStart() {
  T data = null;

  if (head != null) {
    data = head.data;
    head = head.next;
    size--;
  }

  return data;
}

Method for removing a node at the end of the list:

public T removeAtEnd() {
  if (size == 0) {
    throw new RuntimeException("List is empty");
  }

  Node<T> current = head;
  Node<T> previous = null;

  // traverse until we get to the element that we want to remove
  // keep track of the previous element so that we can remove the pointer
  while (current.next != null) {
    previous = current;
    current = current.next;
  }

  T data = (T) previous.next.data;

  // remove the pointer to the last element - The last node object will be removed at the next run of GC -
  // since it does not have any reference to it
  previous.next = null;

  size--;
  return data;
}

Here is the complete LinkedList class:

@SuppressWarnings("unchecked")
public class LinkedList<T> {

  public Node<T> head;
  private int size;

  public LinkedList() {
    this.head = null;
    this.size = 0;
  }

  public void add(T data) {
    Node<T> nodeToAdd = new Node<>(data);

    // if head is null - that means the list is empty, so add the new node as a head
    if (head == null) {
      head = nodeToAdd;
    } else {

      Node<T> current = head;

      // traverse the list until we get to the tail - the node which next pointer is null
      while (current.next != null) {
        current = current.next;
      }

      // set the new node as a new tail
      current.next = nodeToAdd;
    }

    size++;
  }

  public void add(int index, T data) {
    Node<T> nodeToAdd = new Node<>(data);
    int i = 0;

    // check if provided index is valid
    if (index < 0 || index > size + 1) {
      throw new IllegalArgumentException("Invalid index");
    }

    if (index == 0 && head == null) {
      add(data);
    }

    if (index == 0) {
      nodeToAdd.next = head;
      head = nodeToAdd;
    } else {

      Node<T> current = head;

      // traverse until we get to the index - 1
      while (i < index - 1) {
        current = current.next;
        i++;
      }

      // set nodeToAdd.next to the node that the current node is currently pointing to
      nodeToAdd.next = (Node<T>) current.next;
      // set the current node to point to the new node - nodeToAdd
      current.next = nodeToAdd;

    }
    size++;
  }

  public void addAtStart(T data) {
    Node<T> nodeToAdd = new Node<>(data);
    nodeToAdd.next = head;
    head = nodeToAdd;
    size++;
  }

  public T removeAtStart() {
    T data = null;

    if (head != null) {
      data = head.data;
      head = head.next;
      size--;
    }

    return data;
  }

  public T removeAtEnd() {
    if (size == 0) {
      throw new RuntimeException("List is empty");
    }

    Node<T> current = head;
    Node<T> previous = null;

    // traverse until we get to the element that we want to remove
    // keep track of the previous element so that we can remove the pointer
    while (current.next != null) {
      previous = current;
      current = current.next;
    }

    T data = (T) previous.next.data;

    // remove the pointer to the last element - The last element will be removed at the next run of GC -
    // since it does not have any reference to it
    previous.next = null;

    size--;
    return data;
  }

  public void print() {
    if (head != null) {
      Node<T> current = head;

      while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
      }
    }
  }

  public int size() {
    return size;
  }

}

class Node<T> {

  public T data;
  public Node next;

  public Node(T data) {
    this.data = data;
    this.next = null;
  }
}

LinkedList - analysis

Let's see what are the time complexities of some of the most important operations in Linked List:

Adding node at the beginning - O(1).

Adding node at the end - O(n).

Adding node at the middle of the list: O(n).

Removing node at the beginning - O(1).

Removing node at the end - O(n).

Removing node at the middle of the list: O(n).

For the operations we perform on the middle node or the node at the end, the time complexity is O(n) because we need to traverse through the list until we get to that node.