Linked List Data Structures

A linked list is a linear data structure made of nodes. Each node stores a value and a reference (link) to the next node. The first node is called the head, and the last node points to null. Unlike an array, the nodes do not need to be next to each other in memory.

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

The next field holds the reference to the following node; it is null for the last node.

• Singly linked list: each node points to the next node only.
• Doubly linked list: each node points to both the next and the previous node.
• Circular linked list: the last node points back to the first node instead of null.
• Circular doubly linked list: a doubly linked list whose ends are connected.

Use two pointers: slow moves one step and fast moves two steps. When fast reaches the end, slow is at the middle:

static Node findMiddle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;     // for 1->2->3->4->5 returns 3
}

This takes O(n) time and O(1) space, with only one pass.

Use Floyd's cycle detection (tortoise and hare). If the fast pointer ever meets the slow pointer, the list has a cycle; if the fast pointer reaches null, it does not:

static boolean hasCycle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

static Node merge(Node a, Node b) {
    Node dummy = new Node(0);
    Node tail = dummy;
    while (a != null && b != null) {
        if (a.data <= b.data) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;   // attach whatever is left
    return dummy.next;
}

For 1→3→5 and 2→4→6 the result is 1→2→3→4→5→6. It runs in O(n + m) time and reuses the existing nodes.

• Insert or delete at the head: O(1).
• Insert at the tail: O(1) with a tail reference, otherwise O(n).
• Search for a value: O(n).
• Access the k-th element: O(k).

Move a lead pointer n steps ahead, then move both pointers together. When lead reaches the end, the second pointer is n nodes from the end:

static Node nthFromEnd(Node head, int n) {
    Node lead = head;
    for (int i = 0; i < n; i++) {
        if (lead == null) {
            return null;            // list is shorter than n
        }
        lead = lead.next;
    }
    Node follow = head;
    while (lead != null) {
        lead = lead.next;
        follow = follow.next;
    }
    return follow;
}

The head is the only entry point to a singly linked list. If you move the head variable itself while traversing, there is no way back to the first node, and the earlier nodes become unreachable and are garbage collected. Always traverse with a separate variable, such as current.

Yes. java.util.LinkedList is a doubly linked list that implements both List and Deque. It provides methods such as addFirst, addLast, removeFirst and removeLast, all in O(1).