Linked lists

A linked list is a data structure storing an ordered collection of elements as nodes that hold the element’s value along with a reference to the next node in the sequence.

Singly-linked lists

In a singly-linked list, each node consists of a record with a data field and a field containing a reference to the next element in the list. The first node in the list is called the head and the last node is the tail.

Doubly-linked lists

In a doubly-linked list, each node contains an additional field referencing the previous node in the list.

This is advantageous because it allows traversal of the list backwards from a given node, increasing the number of $\mathcal{O}(1)$-time operations that can be performed.

Operations

Access

Unlike arrays , linked lists do not offer efficient direct access . Instead, finding the element at a given position requires iterating through each node until it is reached, resulting in an $\mathcal{0}(n)$ average time complexity.

Insertion

Unlike arrays, the time complexity of inserting a new node is constant, given a reference to the node after which the insertion should occur (or the node before, in the case of a doubly-linked list).

By maintaining a reference to both the head and tail nodes, it is possible to insert an element at the beginning or end of a linked list in $\mathcal{0}(1)$-time.

Deletion

Unlike arrays, the time complexity of deleting a node is constant, given a reference to the node preceding the node to be deleted.

Deletion requires updating the next reference for the preceding node to “skip” the deleted node. This operation has $\mathcal{O}(1)$-time complexity when deleting the first item of the list for both singly- and doubly-linked lists.

Since singly-linked list nodes don’t contain references to their preceding nodes, deletion of the last element cannot be performed in $\mathcal{O}(1)$ time. Doubly linked list nodes do store references to preceding nodes, which allows deletion of the last element in constant time, as long as the implementation maintains a reference to the tail node.

Implementation

Singly-linked list example

The node subclass is a record storing the value for each node, along with a reference to the next node (which may be null).

The list class stores a reference to the head node (which is null when the list is empty). It also stores a reference to the tail node, which allows efficient access/insertion at the end of the list.

 1public class SinglyLinkedList<E> {
 2    private static class Node<E> {
 3        private final E data;
 4        private Node<E> next;
 5
 6        public Node(E data, Node<E> next) {
 7            this.data = data;
 8            this.next = next;
 9        }
10    }
11
12    private Node<E> head = null;
13    private Node<E> tail = null;
14    private int size = 0;
15
16    public int size() { return size; }
17
18    public boolean isEmpty() { return size == 0; }
19
20    public E first() {
21        if (isEmpty()) return null;
22        return head.data;
23    }
24
25    public E last() {
26        if (isEmpty()) return null;
27        return tail.data;
28    }
29
30    public void addFirst(E e) {
31        head = new Node<>(e, head);
32        if (tail == null) tail = head;
33        size++;
34    }
35
36    public void addLast(E e) {
37        Node<E> newNode = new Node<>(e, null);
38        if (isEmpty())
39            head = newNode;
40        else
41            tail.next = newNode;
42        tail = newNode;
43        size++;
44    }
45
46    public E removeFirst() {
47        if (isEmpty()) return null;
48        var result = head.data;
49        head = head.next;
50        size--;
51        if (isEmpty()) tail = null;
52        return result;
53    }
54}

Doubly-linked list example

This implementation employs a “dummy” sentinel node , which reduces the number of special cases to consider when removing nodes. The sentinel node contains no data, and circularly refers to the head and tail of the list (with its next and previous fields, respectively).

The removeLast operation can now be performed in $\mathcal{O}(1)$-time, due to the doubly-linked nature of the list (as explained above).

Also, the doubly-linked list happens to exactly implement the interface of the deque ADT .

 1public class DoublyLinkedList<E> implements DequeADT<E> {
 2    private static class Node<E> {
 3        private final E data;
 4        private Node<E> next;
 5        private Node<E> prev;
 6
 7        public Node(E data, Node<E> prev, Node<E> next) {
 8            this.data = data;
 9            this.prev = prev;
10            this.next = next;
11        }
12    }
13
14    private final Node<E> header;
15    private int size = 0;
16
17    public DoublyLinkedList() {
18        header = new Node<E>(null, null, null);
19        header.next = header.prev = header;
20    }
21
22    public int size() { return size; }
23
24    public boolean isEmpty() { return size == 0; }
25
26    public E first() { return header.next.data; }
27
28    public E last() { return header.prev.data; }
29
30    public void addFirst(E e) { addAfter(e, header); }
31
32    public void addLast(E e) { addAfter(e, header.prev); }
33
34    public E removeFirst() {
35        if (isEmpty()) return null;
36        return remove(header.next);
37    }
38
39    public E removeLast() {
40        if (isEmpty()) return null;
41        return remove(header.prev);
42    }
43
44    private void addAfter(E e, Node<E> node) {
45        var newNode = new Node<>(e, node, node.next);
46        newNode.prev.next = newNode.next.prev = newNode;
47        size++;
48    }
49
50    private E remove(Node<E> node) {
51        node.prev.next = node.next;
52        node.next.prev = node.prev;
53        size--;
54        return node.data;
55    }
56}