Implementing a Singly Linked List in Java

1. From Contiguous Arrays to Linked Nodes

Arrays are powerful but have a key limitation: their size is fixed (or requires a costly resizing operation), and all elements must be stored together in memory. What if we could have a linear structure that grows and shrinks dynamically, with elements scattered across memory? This is the core idea behind a linked list.

A linked list is a chain of nodes. Each node is a small object that contains two pieces of information:

1. The actual data value (e.g., an integer).
2. A reference (or "pointer") to the very next node in the chain.

The list is accessed through a single entry point called the head, which is a reference to the first node. The last node in the chain points to null, signaling the end of the list.

To get a clear conceptual overview of how linked lists compare to arrays and why they are useful, the following video provides an excellent introduction.

2. Building the Linked List in Java

Let's translate this concept into Java code. A linked list implementation typically involves two classes: the LinkedList class itself, and an inner Node class that defines the structure of each element in the chain.

The Node and LinkedList Classes

We'll start by creating our LinkedList class and defining a private inner Node class within it. This encapsulation is good practice, as the Node is an implementation detail that code outside our LinkedList class doesn't need to know about.

public class LinkedList {

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

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

    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;
        }
    }
}

Here's what each part does:

• Node class: Represents one link in our chain. It holds an integer value and a reference next to the subsequent Node.
• LinkedList class: This is the main class that manages the entire structure.
  • head: A Node reference that always points to the first node in the list. Initially null.
  • tail: A Node reference that always points to the last node. This is an optimization that allows for O(1) insertion at the end. Initially null.
  • size: An integer to keep track of the number of nodes in the list.

Kunal Kushwaha's video provides a clear walkthrough of creating this initial structure.

3. Core Operations: Traversal, Insertion, and Deletion

Now that we have the skeleton, let's implement the core functionalities.

Traversal: Displaying the List

To see the contents of our list, we need to traverse it from head to tail. The logic is simple:

1. Create a temporary Node reference, let's call it temp, and point it to head.
2. Use a while loop that continues as long as temp is not null.
3. Inside the loop, print temp.value.
4. Move to the next node by setting temp = temp.next.

It is crucial to use a temporary variable for traversal. If you were to move the actual head pointer, you would lose the entry point to your list, effectively breaking the data structure.

Insertion

We'll cover three types of insertion: at the beginning, at the end, and at a specific position.

1. Inserting at the Head (O(1))

This is the most efficient insertion.

1. Create a new Node with the given value.
2. Set the next pointer of this new node to the current head.
3. Update the head to point to the new node.
4. Handle the edge case: If the list was empty, the tail must also point to this new node.

2. Inserting at the Tail (O(1) with tail pointer)

Thanks to our tail pointer, this is also an O(1) operation.

1. If the list is empty, simply call the insertAtHead method.
2. Otherwise, create a new Node.
3. Set the next pointer of the current tail to point to this new node.
4. Update the tail to be the new node.

If we didn't maintain a tail pointer, we would have to traverse the entire list to find the last node, making the operation O(n). This highlights a key design choice in data structures.

3. Inserting at a Specific Position (O(n))

To insert a node at a position k, we must traverse.

1. Handle edge cases: If k=1, it's an insertion at the head. If k equals the length of the list + 1, it's an insertion at the tail.
2. Traverse the list to find the node at position k-1 (the node before our target position). Let's call it prev.
3. Create the new node.
4. Set the new node's next to point to prev.next.
5. Set prev.next to point to the new node.

Deletion

Similar to insertion, we'll look at deleting from the beginning, end, and a specific position.

1. Deleting the Head (O(1))

This is straightforward.

1. Handle the edge case of an empty list.
2. Move the head pointer to head.next.
3. If the list is now empty (was a single-node list), update tail to null.

2. Deleting the Tail (O(n))

In a singly linked list, this is an O(n) operation because we must find the second-to-last node.

1. Handle edge cases (empty or single-node list).
2. Traverse the list until you reach the node whose next.next is null. This is the second-to-last node.
3. Set this node's next pointer to null.
4. Update the tail to point to this node.

3. Deleting at a Specific Position (O(n))

This is analogous to insertion at a position.

1. Handle edge cases (deleting the head or tail).
2. Traverse to the node at position k-1 (the node before the one to be deleted). Let's call it prev.
3. Update prev.next to point to prev.next.next, effectively "skipping" the node at position k.

4. The Complete Implementation

You've now seen the theory and logic for each operation. The final step is to see them all together in a single, cohesive LinkedList class.

Conclusion

In this lesson, you've built a fundamental data structure from scratch. You now understand not just what a linked list is, but how it works under the hood.

Key Takeaways:

• Structure: A linked list is a chain of Node objects, each containing data and a next pointer. It is accessed via a head pointer.
• vs. Arrays: Linked lists offer dynamic sizing and efficient insertions/deletions at the ends, but suffer from O(n) time for access and search. Arrays offer O(1) access but have costly insertions/deletions in the middle.
• Traversal: Always use a temporary variable to traverse the list to avoid losing the head reference.
• Operations & Complexity:
  • Insertion/Deletion at Head: O(1)
  • Insertion at Tail: O(1) if you maintain a tail pointer, O(n) otherwise.
  • Deletion at Tail: O(n) in a singly linked list.
  • Access/Search/Insertion/Deletion in Middle: O(n) due to traversal.

We have focused on a singly linked list, where traversal is only possible in one direction. In our next lesson, we will explore the doubly linked list, where each node also contains a pointer to the previous node. This small change has significant implications for certain operations, such as deleting the tail.