Skip to main content

Linked List Code Implementation

labuladongOriginalAbout 6470 words

Prerequisites

Before reading this article, you need to learn:

Key Points

I will provide a simple implementation of MyLinkedList using both doubly and singly linked lists, including basic operations like addition, deletion, search, and update. Here are some key points to focus on while reviewing the code.

Key Point 1: Retaining References to Both Head and Tail Nodes

In coding challenges on platforms like LeetCode, you are usually given the head pointer of a singly linked list. However, in real-world development, doubly linked lists are commonly used, which typically retain references to both head and tail nodes.

In software development, adding elements to the end of a container is a common operation. If a doubly linked list holds a reference to the tail node, you can append elements in constant time, O(1)O(1).

For singly linked lists, retaining a reference to the tail node can also be beneficial. When adding an element to the end of a singly linked list, if there is no tail node reference, you must traverse the entire list to find the tail node, which is O(n)O(n) in time complexity. With a tail node reference, this operation can be done in O(1)O(1) time.

Attentive readers might point out that if you delete a tail node in a singly linked list, the tail node reference becomes invalid, requiring a traversal to find the new tail node.

Indeed, but consider this: when deleting the tail node of a singly linked list, you must traverse to the second-to-last node (the predecessor of the tail) to remove the tail node using pointer manipulation. At that point, you can conveniently update the tail node reference.

Key Point Two: Dummy Head and Tail Nodes

In the previous article Linked List Basics, I mentioned the "dummy head and tail node" technique. The concept is simple: when creating a doubly linked list, a dummy head node and a dummy tail node are established, and these nodes exist whether the list is empty or not. This approach prevents null pointer issues and simplifies handling many edge cases.

For example, assume the dummy head and tail nodes are dummyHead and dummyTail, then an empty doubly linked list looks like this:

dummyHead <-> dummyTail

If you add elements 1, 2, 3, the list will look like this:

dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail

Previously, you needed to separately handle cases for inserting elements at the head, tail, and in the middle of the list. With dummy head and tail nodes, regardless of whether the list is empty, you only need to consider inserting elements in the middle. This simplifies the code significantly.

Of course, the dummy head node does consume a little extra memory space, but compared to the issues it resolves, this space consumption is worthwhile.

For singly linked lists, a dummy head node simplifies some operations, but a dummy tail node is not very useful.

Dummy Nodes Are Internal and Invisible

Dummy nodes are a technique for implementing data structures internally and are invisible externally. For instance, the get(index) method to retrieve an element by index calculates the index from real nodes, not from dummy nodes.

Key Point Three: Memory Leak?

In the previous article Dynamic Array Implementation, I mentioned the issue of memory leaks when deleting elements. So, does deleting elements in a linked list also lead to memory leaks?

Especially with the following code, do you think there is an issue?

// Assume the head node of the singly linked list is head = 1 -> 2 -> 3 -> 4 -> 5

// Delete the head node of the singly linked list
head = head.next;

// At this point, head = 2 -> 3 -> 4 -> 5

Careful readers might worry about a potential memory leak here, because the original head node 1 still has its next pointer pointing to node 2.

However, this is actually fine. In Java, the garbage collector determines whether an object should be reclaimed based on whether it is still referenced by other objects. It does not care if the object itself still points to other nodes.

Although node 1's next still points to node 2, if no other pointers reference node 1, it will eventually be reclaimed by the garbage collector. This is different from deleting an element in an array. You can think more about this difference.

That said, when deleting a node, it is still good practice to set all pointers in the deleted node to null. This does not have any real cost and can help prevent potential issues. Therefore, in the following implementation, I will set the pointers of deleted nodes to null, regardless of whether it is strictly necessary.

How to Verify Your Implementation?

You can use LeetCode Problem 707: "Design Linked List" to check whether your implementation is correct. Note that the API names for add, delete, search, and update in Problem 707 are different from the ones used here, so you may need to adjust your code to pass all tests.

Doubly Linked List Implementation

java
import java.util.NoSuchElementException;

public class MyLinkedList<E> {
    // virtual head and tail nodes
    final private Node<E> head, tail;
    private int size;

    // doubly linked list node
    private static class Node<E> {
        E val;
        Node<E> next;
        Node<E> prev;

        Node(E val) {
            this.val = val;
        }
    }

    // constructor initializes virtual head and tail nodes
    public MyLinkedList() {
        this.head = new Node<>(null);
        this.tail = new Node<>(null);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }


    // ***** Add *****

    public void addLast(E e) {
        Node<E> x = new Node<>(e);
        Node<E> temp = tail.prev;
        // temp <-> x
        temp.next = x;
        x.prev = temp;

        x.next = tail;
        tail.prev = x;
        // temp <-> x <-> tail
        size++;
    }

    public void addFirst(E e) {
        Node<E> x = new Node<>(e);
        Node<E> temp = head.next;
        // head <-> temp
        temp.prev = x;
        x.next = temp;

        head.next = x;
        x.prev = head;
        // head <-> x <-> temp
        size++;
    }

    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size) {
            addLast(element);
            return;
        }

        // find the Node corresponding to index
        Node<E> p = getNode(index);
        Node<E> temp = p.prev;
        // temp <-> p

        // new Node to be inserted
        Node<E> x = new Node<>(element);

        p.prev = x;
        temp.next = x;

        x.prev = temp;
        x.next = p;

        // temp <-> x <-> p

        size++;
    }

    // ***** Remove *****

    public E removeFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        // the existence of virtual nodes prevents us from having to consider null pointers
        Node<E> x = head.next;
        Node<E> temp = x.next;
        // head <-> x <-> temp
        head.next = temp;
        temp.prev = head;

        E val = x.val;
        x.prev = null;
        x.next = null;
        // head <-> temp

        size--;
        return val;
    }

    public E removeLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        Node<E> x = tail.prev;
        Node<E> temp = tail.prev.prev;
        // temp <-> x <-> tail

        tail.prev = temp;
        temp.next = tail;

        E val = x.val;
        x.prev = null;
        x.next = null;
        // temp <-> tail

        size--;
        return val;
    }

    public E remove(int index) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node<E> x = getNode(index);
        Node<E> prev = x.prev;
        Node<E> next = x.next;
        // prev <-> x <-> next
        prev.next = next;
        next.prev = prev;

        E val = x.val;
        x.prev = null;
        x.next = null;
        // prev <-> next

        size--;
        return val;
    }

    // ***** Get *****

    public E get(int index) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node<E> p = getNode(index);

        return p.val;
    }

    public E getFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        return head.next.val;
    }

    public E getLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        return tail.prev.val;
    }

    // ***** Set *****

    public E set(int index, E val) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node<E> p = getNode(index);

        E oldVal = p.val;
        p.val = val;

        return oldVal;
    }

    // ***** Other utility functions *****

    public int size() {
        return size;
    }

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

    private Node<E> getNode(int index) {
        checkElementIndex(index);
        Node<E> p = head.next;
        // TODO: Can be optimized by deciding whether to
        // traverse from head or tail based on index
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    // Check if the index position can contain an element
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // Check if the index position can add an element
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    private void display() {
        System.out.println("size = " + size);
        for (Node<E> p = head.next; p != tail; p = p.next) {
            System.out.print(p.val + " <-> ");
        }
        System.out.println("null");
        System.out.println();
    }

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addFirst(0);
        list.add(2, 100);

        list.display();
        // size = 5
        // 0 <-> 1 <-> 100 <-> 2 -> 3 -> null
    }
}

Singly Linked List Implementation

java
import java.util.NoSuchElementException;

public class MyLinkedList2<E> {

    private static class Node<E> {
        E val;
        Node<E> next;

        Node(E val) {
            this.val = val;
            this.next = null;
        }
    }

    private Node<E> head;
    // actual reference to the tail node
    private Node<E> tail;
    private int size;

    public MyLinkedList2() {
        this.head = new Node<>(null);
        this.tail = head;
        this.size = 0;
    }

    public void addFirst(E e) {
        Node<E> newNode = new Node<>(e);
        newNode.next = head.next;
        head.next = newNode;
        if (size == 0) {
            tail = newNode;
        }
        size++;
    }

    public void addLast(E e) {
        Node<E> newNode = new Node<>(e);
        tail.next = newNode;
        tail = newNode;
        size++;
    }

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size) {
            addLast(element);
            return;
        }

        Node<E> prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> newNode = new Node<>(element);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    public E removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Node<E> first = head.next;
        head.next = first.next;
        if (size == 1) {
            tail = head;
        }
        size--;
        return first.val;
    }

    public E removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        Node<E> prev = head;
        while (prev.next != tail) {
            prev = prev.next;
        }
        E val = tail.val;
        prev.next = null;
        tail = prev;
        size--;
        return val;
    }

    public E remove(int index) {
        checkElementIndex(index);

        Node<E> prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node<E> nodeToRemove = prev.next;
        prev.next = nodeToRemove.next;
        // deleting the last element
        if (index == size - 1) {
            tail = prev;
        }
        size--;
        return nodeToRemove.val;
    }

    // ***** Retrieve *****

    public E getFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return head.next.val;
    }

    public E getLast() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return tail.val;
    }

    public E get(int index) {
        checkElementIndex(index);
        Node<E> p = getNode(index);
        return p.val;
    }

    // ***** Update *****

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> p = getNode(index);

        E oldVal = p.val;
        p.val = element;

        return oldVal;
    }

    // ***** Other Utility Functions *****
    public int size() {
        return size;
    }

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

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    // Check if the index position can have an element
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // Check if the index position can add an element
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // Return the Node corresponding to the index
    // Note: Please ensure that the passed index is valid
    private Node<E> getNode(int index) {
        Node<E> p = head.next;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    public static void main(String[] args) {
        MyLinkedList2<Integer> list = new MyLinkedList2<>();
        list.addFirst(1);
        list.addFirst(2);
        list.addLast(3);
        list.addLast(4);
        list.add(2, 5);

        System.out.println(list.removeFirst()); // 2
        System.out.println(list.removeLast()); // 4
        System.out.println(list.remove(1)); // 5

        System.out.println(list.getFirst()); // 1
        System.out.println(list.getLast()); // 3
        System.out.println(list.get(1)); // 3
    }
}
Last Updated:

© 2019 - 2025 labuladong All rights reserved.