Singly Linked List: Implementation and Operations

1. The Concept of a Linked List

Unlike an array, which stores elements in a contiguous block of memory, a linked list is a collection of objects called nodes that can be scattered anywhere in memory. Each node contains two key pieces of information:

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

The list is accessed through a reference to the very first node, called the head. The last node in the sequence points to null, signaling the end of the list.

To get a clear understanding of why linked lists are useful and how they differ from arrays, let's start with a conceptual overview.

2. Building the Core Structure in Java

Now, let's translate this concept into Java code. We'll create two classes:

1. Node: A private inner class that represents a single element. Making it private encapsulates the node's implementation within the linked list itself.
2. SinglyLinkedList: The main class that will manage the collection of nodes and contain the logic for our operations.

Our SinglyLinkedList class will maintain a few crucial fields: head, tail, and size. Keeping references to both the head and tail allows for efficient O(1) insertions at both ends.

Here's a summary of the structure we will implement. Note that we'll be building instance methods within the SinglyLinkedList class, which is a more object-oriented approach than using static helper methods.

public class SinglyLinkedList {

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

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

    // Our insertion, deletion, and traversal methods will go here.

    private class Node {
        private int value;
        private Node next;

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

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

3. Traversal: Visiting Each Node

The most basic operation is traversal—visiting each node in order from head to tail. This is necessary for printing the list, searching for a value, or performing any operation that requires inspecting the elements.

A critical rule when traversing is to never move the head reference itself. The head is the permanent entry point to your list. If you reassign it, you lose the beginning of your list. Instead, we use a temporary reference variable (e.g., temp or current) that starts at the head and advances through the list.

Here is the implementation of our display method:

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

4. Insertion Operations

Let's implement the three main ways to insert a node: at the beginning, at the end, and at a specific index.

Insertion at the Beginning (O(1))

This is the most straightforward insertion.

1. Create a new Node.
2. Set the next reference of the new node to the current head.
3. Update the head to point to the new node.
4. If the list was empty, the new node is also the tail.

Insertion at the End (O(1))

Thanks to our tail reference, adding to the end is also an O(1) operation. Without a tail reference, we would have to traverse the entire list (O(n)) to find the last node.

1. Create a new Node.
2. Set the next reference of the current tail to the new node.
3. Update the tail to point to the new node.
4. If the list was empty, this is the same as inserting at the beginning.

Insertion at a Specific Index (O(n))

To insert at an index, we must first traverse the list to find the node before the desired insertion point.

1. Handle edge cases: if index is 0, call insertFirst. If index is size, call insertLast.
2. Traverse to the node at index - 1.
3. Create the new Node.
4. Set the new node's next to the (index-1) node's next.
5. Update the (index-1) node's next to point to the new node.

5. Deletion Operations

Now for the removal operations. Similar to insertion, we'll cover deletion from the beginning, end, and a specific index.

Deletion from the Beginning (O(1))

This is a simple pointer update.

1. If the list is empty, there's nothing to do.
2. Move the head reference to head.next.
3. If the list becomes empty after deletion, update tail to null.
4. Decrement the size.

Deletion from the End (O(n))

This is a classic interview question for singly linked lists. Because we can only move forward, we cannot simply update the tail. We must traverse from the head to find the second-to-last node.

1. Handle edge cases (list is empty or has only one element).
2. Traverse the list to find the node at size - 2.
3. Set this node as the new tail.
4. Set the new tail's next reference to null.
5. Decrement the size.

Deletion at a Specific Index (O(n))

Similar to insertion at an index, this requires traversing to the node before the one you want to delete.

1. Handle edge cases: if index is 0, call deleteFirst. If index is size - 1, call deleteLast.
2. Traverse to the node at index - 1 (let's call it prev).
3. Update prev.next to be prev.next.next, which effectively "skips" the node at index, removing it from the chain.

6. Complexity Analysis

Understanding the performance of these operations is vital for interviews. Let's summarize the time and space complexity.

Here is a summary table for quick reference:

Conclusion

In this lesson, you've built a complete singly linked list from the ground up, a significant step in mastering fundamental data structures. You now understand not just the "what" but the "how" and "why" behind its implementation.

Key Takeaways:

• A singly linked list is a dynamic data structure composed of nodes, where each node points to the next.
• We implemented the three core operations: traversal, insertion, and deletion.
• Maintaining a tail pointer is a crucial optimization, allowing for O(1) insertions at the end.
• Operations at the head are very efficient (O(1)), while operations involving the tail or a specific index are typically O(n) due to the need for traversal.

You now have a solid foundation with this new data structure. In our next lesson, we will build directly on what you've created today by tackling another common interview problem: reversing a singly linked list.