Before we dive into Linked Lists, it is worth mentioning that an array is nothing more than a set of back to back memory slots where each element of the array is stored in a single memory slot. A Linked List is similar to an array, with the difference that the allocated memory does not have to be back to back, rather it is random.

Overview

Time Complexity

To add an element in a linked list, we need to traverse the list till the last node and then set the new node on the last node’s next reference. That will lead to a time complexity of O(i), where i is the size of the list.

To get an element in a linked list, we need to traverse up to the ith element, similarly the time complexity is O(i)

Space Complexity

Space complexity is O(N), as each element takes a memory slot.

The Node

The node is a centerpiece of a Linked List and actually on most data structures. The node is the basic object that will hold the value of the element as well as point to the next node.

public class Node<T> {
    private T value;
    private Node<T> next;

    Node(T value) {
        this.value=value;
    }
}

Add Element

When adding an element, we traverse the list to the end and then add the element at the end.

    public class MyLinkedList<T> implements List<T> {
      private int size = 0;
      private Node<T> head;

      @Override
      public boolean add(T t) {
          final Node<T> newNode = new Node<>(t);

          if(head == null) {
              head = newNode;
          } else {
              final Node<T> lastNode = getLastNode();
              lastNode.setNext(newNode);
          }
          size++;
          return true;
      }

      private Node<T> getLastNode() {
          Node<T> lastNode = head;

          while(lastNode.getNext() != null) {
              lastNode = lastNode.getNext();
          }
          return lastNode;
      }
    }

Add Element - Optimized

Adding an element to a Linked List to the end can be inefficient if we need to traverse to the end to add an element. What if we kept track of the last node (AKA Tail) and just add the node to the tail? That would allow us to not traverse the list each time we add an element and that is exactly what we can do.

    public class MyLinkedList<T> implements List<T> {
      private int size = 0;
      private Node<T> head;

    @Override
    public boolean add(T t) {
        final Node<T> newNode = new Node<>(t);

        if(head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.setNext(newNode);
            tail = newNode;
        }
        size++;
        return true;
    }
}

Remove Element

To remove an element we will need to iterate the list and find the element and consider the following cases:

1. If the element found is the head, then set head to head.next. This effectively removes the head from the list.
2. If the element found is the tail, then set tail to the previous node and set the previous node next to null.
3. If the element found is not a head or tail, then set the previousNode.next to currentNode.next, this will remove the current found node

    public class MyLinkedList<T> implements List<T> {
      private int size = 0;
      private Node<T> head;

    @Override
    public boolean remove(Object o) {
        if (head == null || o == null) {
            return false;
        } else {
            Node<T> currentNode = head;
            Node<T> previousNode = null;

            while(currentNode!=null && !currentNode.getValue().equals(o)) {
                previousNode = currentNode;
                currentNode = currentNode.getNext();
            }

            if(currentNode !=null && currentNode.getValue().equals(o)) {
                if(currentNode == head) {
                    head = head.getNext();
                } else if(currentNode == tail) {
                    tail = previousNode;
                    previousNode.setNext(null);
                } else {
                    previousNode.setNext(currentNode.getNext());
                }

                size--;
                return true;
            } else {
                return false;
            }
        }
    }

When to use a Linked List?

• If the list has a lot of manipulation, a linked list will be faster as only the pointers need to be manipulated.
• If you need a Queue, linked list can act as a queue as well.

Conclusion

Making lists of reasons was sometimes a good way to figure things out

Lois Lowry