Linked Lists

Understanding Linked Lists

Today we're diving into linked lists - one of those fundamental data structures that keeps showing up in interviews and real-world programming scenarios. I've been working with them lately and wanted to share my implementation and insights.

What's a Linked List, Anyway?

Think of a linked list as a chain of nodes, where each node holds two things:

• A piece of data (the value)

• A pointer to the next node in the sequence

The beauty of linked lists lies in their flexibility. Unlike arrays, they don't need contiguous memory allocation, making insertions and deletions much more efficient in many scenarios.

Basic Linked List Implementation

Let me walk you through my Java implementation of a singly linked list:

// This is our basic Node class
class Node {
    int value;
    Node next;

    public Node() {}

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

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

Each node stores an integer value and references the next node in the list. Simple enough, right?

Now for the main linked list class:

public class LL {
    private Node head;
    private Node tail;
    private int size;

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

    // Methods will go here...
}

I'm keeping track of both the head (first node) and tail (last node) pointers, plus the size. This gives us O(1) access to both ends of the list and makes certain operations more efficient.

Basic Operations

Insertion at the Beginning

void insertAtFirst(int value){
    if (head == null) {
        Node node = new Node(value);
        head = node;
        tail = node;
        size++;
    }

    Node node = new Node(value);
    node.next = head;
    head = node;

    size++;
}

When I insert at the beginning, I need to handle two cases:

1. If the list is empty, the new node becomes both head and tail

2. Otherwise, I point the new node to the current head and update the head reference

Insertion at the End

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

Similar logic here - if there's no tail (empty list), I delegate to insertAtFirst(). Otherwise, I add the new node after the current tail and update the tail pointer.

Displaying the List

void display(){
    Node temp = head;
    for (int i = 0; i < size - 1; i++) {
        System.out.print(temp.value + " -> ");
        temp = temp.next;
    }
    System.out.print("Null");
    System.out.println();
}

This method walks through the list, printing each value followed by an arrow, and finally shows "Null" to represent the end of the list.

Recursive Insertion

void insertRec(int value, int index){
    try {
        if (index < size) {
            Node temp = head;
            int recCount = 0;
            helperInsertRec(value, index, temp, recCount);
        }
        else {
            throw new IndexOutOfBoundsException(index + " is out of bounds as size of the Linked list is " + size);
        }
    }
    catch(IndexOutOfBoundsException e){
        System.out.println("Exception: " + e.getMessage());
    }
}

private void helperInsertRec(int value, int index, Node temp, int recCount) {
    if (recCount == index-1){
        Node node = new Node(value);
        node.next = temp.next;
        temp.next = node;
        size++;
        return;
    }
    helperInsertRec(value,index,temp.next,recCount+1);
}

This is a recursive approach to insert a node at a specific index. The helper method keeps track of its position in the list and stops when it reaches the insertion point. I find recursion makes the code more elegant, though admittedly it's not the most efficient approach for very long lists due to stack overhead.

Solving Common Linked List Problems

Removing Duplicates

public Node deleteDuplicates(Node node) {
    if (node == null){
        return node;
    }
    Node head = node;
    while(node.next != null){
        if (node.value == node.next.value){
            node = node.next;
        }
        else {
            node.next = node.next.next;
        }
    }
    return head;
}

This method removes consecutive duplicate values from a sorted linked list - a common problem you'll encounter on platforms like LeetCode.

Merging Two Sorted Lists

public LL mergeTwoLists(LL list1, LL list2) {
    Node h1 = list1.head;
    Node h2 = list2.head;

    LL listAns = new LL();

    while (h1 != null && h2 != null){
        if (h1.value < h2.value){
            listAns.insertLast(h1.value);
            h1 = h1.next;
        }
        else {
            listAns.insertLast(h2.value);
            h2 = h2.next;
        }
    }

    while (h1 != null){
        listAns.insertLast(h1.value);
        h1=h1.next;
    }
    while (h2 != null){
        listAns.insertLast(h2.value);
        h2=h2.next;
    }
    return listAns;
}

This solution merges two sorted linked lists into a single sorted list - another classic problem. We compare the heads of both lists, take the smaller value, and advance that list's pointer until we've processed all nodes.

Beyond Singly Linked Lists

Doubly Linked Lists

A doubly linked list extends our basic implementation by adding a previous pointer, allowing for bidirectional traversal:

class DoublyNode {
    int value;
    DoublyNode next;
    DoublyNode prev;

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

With this addition, we can move both forward and backward through our list. This makes operations like "delete the previous node" much more efficient, but comes at the cost of additional memory usage for the extra pointer.

In my implementation, I would need to modify insertion and deletion methods to update both the next and prev references. For example, when inserting a new node between existing nodes A and B:

1. Set new node's next to B

2. Set new node's prev to A

3. Set A's next to the new node

4. Set B's prev to the new node

Circular Linked Lists

A circular linked list connects the tail back to the head, creating an endless loop:

// After creating the entire linked list
tail.next = head;

This simple change creates a structure where you can keep traversing indefinitely. Circular lists are great for scenarios like round-robin scheduling or any situation where you need to cycle through elements repeatedly.

For a circular doubly linked list, we would also set:

head.prev = tail;

LeetCode Problems

If you want to master linked lists, try these LeetCode problems which I solved:

(Click the link for my solutions)

1. Reverse Linked List (#206) - Can you reverse a linked list in-place?

2. Merge Two Sorted Lists (#21) - Similar to our implementation above

3. Reverse Nodes in k-Group (#25) - Example of Leetcode HARD's ease!

4. Linked List Cycle (#141) - Can you detect if a linked list has a cycle?

5. Palindrome Linked List (#234) - Is your linked list a palindrome?

My advice: solve these without looking at solutions first. Then compare your approach with others to learn optimization techniques.

When to Use Linked Lists

Linked lists shine when:

• You need frequent insertions/deletions in the middle of the list

• You don't know how many items will be in your list

• You don't need random access to elements

• Memory is tight and you want to avoid over-allocation

They're less ideal when:

• You need constant-time access to random elements

• Memory overhead matters (each node requires extra space for pointers)

Conclusion

Linked lists might seem simple at first glance, but mastering them opens the door to understanding more complex data structures like trees and graphs. The key insight? It's all about managing references between nodes.

My implementation here covers the basics, but there's always room for improvement.

GitHub Repo

I've pushed my complete implementations, including tests and additional functionality, to my GitHub repo:
Click here.

Feel free to fork it, suggest improvements, or ask questions. Happy coding!