Singly Linked List Fundamentals

1. The Anatomy of a Linked List

Unlike an array, which stores elements in a single, contiguous block of memory, a linked list is a dynamic data structure where elements are scattered across memory. Each element, called a node, contains two pieces of information:

1. The data it holds.
2. A reference (or "pointer") to the next node in the sequence.

This chain of nodes forms the list. The entry point to the list is a special pointer called the head, which points to the very first node. The last node in the chain points to null, signaling the end of the list.

Linked lists have distinct trade-offs compared to arrays.

2. The Building Blocks: Node and LinkedList Classes

To implement a linked list in Java, we need two classes:

1. A Node class to represent each element.
2. A LinkedList class to manage the overall structure and operations.

Since you are aiming for Java mastery in a backend context, we'll use generics (<T>) for our implementation. This allows our linked list to hold any type of data (Strings, Integers, custom objects) in a type-safe way, which is a standard practice in modern Java.

First, let's define the Node. It's a simple container. We'll make it a private inner class within our LinkedList because its existence is solely to support the list itself.

// This will be inside the LinkedList class
private class Node {
    private T value;
    private Node next;

    public Node(T value) {
        this.value = value;
        // this.next is null by default
    }

    public Node(T value, Node next) {
        this.value = value;
        this.next = next;
    }
}

Next, we define the LinkedList class itself. It will manage the nodes using head and tail pointers. We also include a size field to keep track of the number of elements, which is an O(1) way to know the list's length.

The following video from Kunal Kushwaha provides an excellent walkthrough of setting up these classes.

Here's the skeleton for our CustomLinkedList class based on this structure:

public class CustomLinkedList<T> {

    private Node head;
    private Node tail;
    private int size;

    public CustomLinkedList() {
        this.size = 0;
    }

    // --- Inner Node Class ---
    private class Node {
        private T value;
        private Node next;

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

        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    // --- We will add our methods here ---
}

3. Core Operations: Traversal, Insertion, and Deletion

Now, let's implement the methods that bring our linked list to life.

Traversal: Displaying the List

To see the contents of our list, we need to traverse it from head to tail. A common mistake is to move the head pointer itself. This would permanently modify the list, effectively losing the beginning of your list after one traversal!

Instead, we use a temporary temp node that starts at head and iterates through the list.

Here is the code for the display method:

public void display() {
    Node temp = head;
    while (temp != null) {
        System.out.print(temp.value + " -> ");
        temp = temp.next;
    }
    System.out.println("END");
}

Insertion

There are three main places to insert a node: at the beginning, at the end, or at a specific index.

1. Inserting at the Beginning (insertFirst)

This is the most efficient insertion. We create a new node, make it point to the current head, and then update head to be this new node.

The logic is explained clearly in this part of the video.

Here's the implementation:

public void insertFirst(T val) {
    Node node = new Node(val);
    node.next = head;
    head = node;

    if (tail == null) {
        tail = head;
    }
    size++;
}

2. Inserting at the End (insertLast)

If we only had a head pointer, we'd have to traverse the entire list (an O(n) operation) to find the last node. By maintaining a tail pointer, we can do this in constant time, O(1).

The implementation is straightforward:

public void insertLast(T val) {
    if (tail == null) {
        // If the list is empty, inserting last is the same as inserting first
        insertFirst(val);
        return;
    }
    Node node = new Node(val);
    tail.next = node;
    tail = node;
    size++;
}

3. Inserting at a Specific Index (insert)
This is more involved. To insert a node at index i, we must traverse to the node at index i-1, and then carefully rewire the pointers.

Here's the code:

public void insert(T val, int index) {
    if (index == 0) {
        insertFirst(val);
        return;
    }
    if (index == size) {
        insertLast(val);
        return;
    }
    
    Node temp = head;
    // Traverse to the node at index - 1
    for (int i = 1; i < index; i++) {
        temp = temp.next;
    }

    Node node = new Node(val, temp.next);
    temp.next = node;
    size++;
}

Deletion

Deletion follows a similar logic to insertion, requiring careful pointer manipulation.

1. Deleting the First Node (deleteFirst)
This is simple: move the head pointer to the next node. The garbage collector will eventually clean up the old head node.

2. Deleting the Last Node (deleteLast)
This operation highlights a key limitation of a singly linked list. To delete the last node, you must set the next pointer of the second-to-last node to null. This requires an O(n) traversal to find that node.

3. Deleting at a Specific Index (delete)
Similar to insertion, you must find the node before the one you want to delete and update its next pointer to "skip over" the deleted node.

4. Your Turn: A Complete Implementation

Below is the complete CustomLinkedList class with all the methods we've discussed. Your task is to study this code, compile it, and run it. Before you run the main method, try to trace the operations on paper and predict the output at each display() call. This exercise will solidify your understanding of how the pointers change with each operation.

Create a file CustomLinkedList.java:

public class CustomLinkedList<T> {

    private Node head;
    private Node tail;
    private int size;

    public CustomLinkedList() {
        this.size = 0;
    }

    public void insertFirst(T val) {
        Node node = new Node(val);
        node.next = head;
        head = node;

        if (tail == null) {
            tail = head;
        }
        size++;
    }

    public void insertLast(T val) {
        if (tail == null) {
            insertFirst(val);
            return;
        }
        Node node = new Node(val);
        tail.next = node;
        tail = node;
        size++;
    }

    public void insert(T val, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            insertFirst(val);
            return;
        }
        if (index == size) {
            insertLast(val);
            return;
        }

        Node temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.next;
        }

        Node node = new Node(val, temp.next);
        temp.next = node;
        size++;
    }
    
    public T deleteFirst() {
        if (size == 0) {
            throw new RuntimeException("List is empty");
        }
        T value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }

    public T deleteLast() {
        if (size <= 1) {
            return deleteFirst();
        }

        Node secondLast = get(size - 2);
        T value = tail.value;
        tail = secondLast;
        tail.next = null;
        size--;
        return value;
    }

    public T delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            return deleteFirst();
        }
        if (index == size - 1) {
            return deleteLast();
        }

        Node prev = get(index - 1);
        T value = prev.next.value;
        prev.next = prev.next.next;
        size--;
        return value;
    }

    // Helper method to get the node at a specific index
    public Node get(int index) {
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.value + " -> ");
            temp = temp.next;
        }
        System.out.println("END");
    }

    private class Node {
        private T value;
        private Node next;

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

        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

Create a Main.java file to test it:

public class Main {
    public static void main(String[] args) {
        CustomLinkedList<Integer> list = new CustomLinkedList<>();

        System.out.println("--- Inserting elements ---");
        list.insertFirst(3);
        list.insertFirst(8);
        list.insertFirst(2);
        list.insertFirst(17);
        list.display(); // Predict: 17 -> 2 -> 8 -> 3 -> END

        list.insertLast(99);
        list.display(); // Predict: 17 -> 2 -> 8 -> 3 -> 99 -> END

        list.insert(100, 3);
        list.display(); // Predict: 17 -> 2 -> 8 -> 100 -> 3 -> 99 -> END
        
        System.out.println("\n--- Deleting elements ---");
        System.out.println("Deleted first: " + list.deleteFirst());
        list.display(); // Predict: 2 -> 8 -> 100 -> 3 -> 99 -> END

        System.out.println("Deleted last: " + list.deleteLast());
        list.display(); // Predict: 2 -> 8 -> 100 -> 3 -> END

        System.out.println("Deleted from index 2: " + list.delete(2));
        list.display(); // Predict: 2 -> 8 -> 3 -> END
    }
}

Conclusion

Congratulations on building a singly linked list from scratch! This is a significant milestone in your journey to mastering core Java and data structures. You've gone beyond just knowing what a linked list is to understanding how it works under the hood.

Key Takeaways:

• A linked list is a chain of Node objects, each containing data and a reference to the next node.
• The head pointer is the entry point, and the last node points to null. Maintaining a tail pointer optimizes insertion at the end.
• Traversal must be done with a temporary pointer to avoid modifying the list's structure.
• Insertion and deletion involve carefully re-assigning the next pointers of the surrounding nodes.
• Operations at the beginning are O(1), while operations at the end or in the middle are O(n) for a singly linked list (unless you have a tail pointer for insertion).

In our next lesson, we'll explore two other fundamental data structures: stacks and queues. You'll see how to use Java's built-in Deque interface, which can be implemented using a linked list, to model Last-In, First-Out (LIFO) and First-In, First-Out (FIFO) behaviors.