Skip to main content

Linked List Code Implementation

labuladongOriginal

707. Design Linked List https://leetcode.com/problems/design-linked-list

This article will resolve

LeetCodeDifficulty
707. Design Linked List🟠

Prerequisites

Before reading this article, you need to learn:

Key Points

Here I will give simple implementations of MyLinkedList for both doubly and singly linked lists. These include basic operations like add, delete, search, and update. Here are some key points you should pay special attention to when reading the code.

Key Point 1: Keep References to Both Head and Tail

In most LeetCode problems, you usually get a head pointer to a singly linked list. But in real software development, we mostly use doubly linked lists. Doubly linked lists often have references to both the head and tail nodes.

This is because adding elements to the end of a list is very common. If you keep a tail reference in a doubly linked list, you can add elements to the end in O(1)O(1) time.

For singly linked lists, keeping a tail reference also helps. If you don't keep a tail reference and want to add a node to the end, you have to traverse the whole list to find the tail node, which takes O(n)O(n) time. With a tail reference, you can do it in O(1)O(1) time.

Some careful readers may say: even so, if you delete the tail node of a singly linked list, the tail reference becomes invalid and has to be updated again by traversing the list.

That’s true, but think a bit more: When deleting the tail node, don't you have to traverse to the second-to-last node anyway, so you can adjust the pointer to remove the last node? At that point, you can also update your tail reference.

Key Point 2: Dummy Head and Tail Nodes

In the previous article Linked List Basics, I mentioned the "dummy head and tail" technique. The idea is simple: when you create a doubly linked list, you also create a dummy head and a dummy tail node. These two nodes always exist, whether the list is empty or not. This avoids null pointer problems and saves you from handling many edge cases.

For example, let's say the dummy head and tail nodes are called dummyHead and dummyTail. An empty doubly linked list looks like:

dummyHead <-> dummyTail

If you add elements 1, 2, 3, the list looks like:

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

Before, you had to treat "insert at the head," "insert at the tail," and "insert in the middle" as different cases. With dummy nodes, there's no need—whether the list is empty or not, you just handle "insert in the middle," which makes your code much cleaner.

Dummy nodes use a bit of extra memory, but it's worth it for all the complexity they save you.

For singly linked lists, a dummy head helps simplify things, but a dummy tail usually does not help much.

Dummy nodes are for internal implementation only

Dummy nodes are used for your own implementation convenience. They should not be seen from outside. For example, when using the get(index) function, the index counting starts from the real node, not from the dummy node.

Key Point 3: Memory Leaks?

In the Dynamic Array Implementation, I mentioned that you should be careful with memory leaks when deleting elements. Does this problem happen in linked lists too?

For example, look at this code:

// Suppose the singly linked list head = 1 -> 2 -> 3 -> 4 -> 5

// Delete the head node
head = head.next;

// Now head = 2 -> 3 -> 4 -> 5

Some careful readers may think there is a memory leak here, since the original head node 1 still has its next pointer pointing to node 2.

But actually, this is fine. Java's garbage collector checks if the object is still referenced by someone else. It does not care if the object points to other objects. Since no pointer refers to node 1 anymore, it will be garbage collected. So this is different from deleting elements in an array.

Still, it is a good habit to set the pointers of the deleted node to null, even if it is not strictly necessary. This can avoid some possible hidden problems. In the following implementation, I will set all the pointers on the deleted node to null.

How to test your implementation?

You can use LeetCode Problem 707 "Design Linked List" to check if your code is correct. Note that the API names required by Problem 707 are not exactly the same as those in this article, so you need to adjust them to pass all test cases.

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.