Chapter 8: Linked Lists: Dynamic Connections

Welcome back, future software architect! In our previous chapters, we’ve laid a solid foundation by understanding the core principles of data structures and algorithms, diving deep into complexity analysis, and even exploring the versatility of arrays and strings. Arrays are fantastic for their fast, direct access to elements. But what if you need a data structure that’s more flexible, one that doesn’t require contiguous memory and excels at insertions and deletions without shifting every other element?

That’s where Linked Lists come into play! This chapter will introduce you to a fascinating and fundamental data structure that forms the backbone of many advanced concepts. We’ll uncover what makes linked lists dynamic, how they manage connections between data, and when they shine brighter than arrays. By the end, you’ll not only understand the theory but also have hands-on experience implementing a singly linked list in TypeScript, complete with essential operations and a grasp of their performance characteristics. Get ready to connect the dots!

What is a Linked List?

Imagine you’re on a scavenger hunt, and each clue tells you where to find the next clue. You don’t know the entire path upfront, and the clues aren’t necessarily laid out neatly side-by-side. You just follow one pointer to the next. This is very similar to how a linked list works!

Unlike arrays, which store elements in contiguous (side-by-side) memory locations, a linked list stores elements non-contiguously. Each element, often called a node, contains two main pieces of information:

1. Data (or Value): The actual information you want to store.
2. Next Pointer (or Reference): A link to the next node in the sequence.

The very first node in the list is called the head, and it’s our starting point. The last node’s next pointer usually points to null (or undefined in TypeScript), signifying the end of the list.

Let’s visualize a single node:

• Think of it: A single piece of paper with a fact (Data) and a note saying “There’s nothing after me!” (Next Pointer points to null).

Now, let’s see how multiple nodes connect:

• Think of it: A chain where each link knows only its own content and where the next link is. To get from ‘A’ to ‘C’, you must first go through ‘B’.

This structure gives linked lists their dynamic nature. Adding or removing elements can be very efficient because you only need to update a few pointers, rather than shifting large blocks of memory like with arrays. However, it also means you can’t jump directly to the 5th element; you have to start at the head and traverse through each node until you reach the desired position.

Types of Linked Lists (A Quick Overview)

While we’ll focus on the Singly Linked List (where each node points only to the next), it’s good to know there are other variations:

• Doubly Linked List: Each node has two pointers: next (to the next node) and prev (to the previous node). This allows for traversal in both directions.

• Circular Linked List: The next pointer of the last node points back to the head node, forming a loop. This is useful for things like round-robin scheduling or continuous data streams.

For now, let’s keep our focus on the simpler, but equally powerful, Singly Linked List.

Step-by-Step Implementation: Singly Linked List in TypeScript

We’ll build our LinkedList class from the ground up. Remember our principles: baby steps, explain everything, and no code dumps!

First, ensure you have a TypeScript project set up (if you’re following from previous chapters, you’re good to go). Create a new file, say src/linkedList.ts.

// src/linkedList.ts

// Step 1: Define the Node
// Every element in our linked list will be a 'Node'.
// It holds a 'value' and a 'next' pointer to the subsequent node.
class Node<T> {
    value: T;
    next: Node<T> | null; // The 'next' pointer can be another Node or null if it's the last node.

    constructor(value: T) {
        this.value = value;
        this.next = null; // Initially, a new node doesn't point to anything.
    }
}

Explanation:

• We’re defining a Node class. The <T> makes it a generic class, meaning T can be any data type (number, string, object, etc.). This makes our linked list reusable for various data types.
• value: T; stores the actual data for this node.
• next: Node<T> | null; is the crucial pointer. It will either point to another Node of the same type T or be null if this is the last node in the list.
• The constructor initializes a new Node with a given value and sets its next pointer to null. Simple, right?

Now, let’s define our LinkedList class itself.

// src/linkedList.ts (continued)

// Step 2: Define the LinkedList class
// This class will manage the nodes and provide methods to interact with the list.
class LinkedList<T> {
    head: Node<T> | null; // The first node in the list.
    tail: Node<T> | null; // The last node in the list.
    size: number;          // Keeps track of how many nodes are in the list.

    constructor() {
        this.head = null;  // An empty list has no head.
        this.tail = null;  // An empty list has no tail.
        this.size = 0;     // An empty list has zero elements.
    }
}

Explanation:

• Our LinkedList class is also generic (<T>), allowing it to store any type of data.
• head: A reference to the very first Node in our list. If the list is empty, head will be null.
• tail: A reference to the very last Node in our list. Keeping track of the tail makes adding elements to the end much faster. If the list is empty, tail will also be null.
• size: A simple counter to know how many elements are currently in our list. This is often an optimization; you could always count by traversing, but size gives O(1) access to this information.

At this point, we have the basic structure. An empty list looks like this:

Adding Elements: append (Adding to the End)

One of the most common operations is adding a new element to the end of the list. We’ll call this append.

// src/linkedList.ts (continued)

class LinkedList<T> {
    // ... (previous code for head, tail, size, constructor) ...

    // Step 3: Implement the append method
    // Adds a new node to the end of the list.
    append(value: T): void {
        const newNode = new Node(value); // Create a new node with the given value.

        if (this.size === 0) {
            // Case 1: The list is currently empty.
            // The new node becomes both the head and the tail.
            this.head = newNode;
            this.tail = newNode;
        } else {
            // Case 2: The list is not empty.
            // The current tail's 'next' pointer should point to the new node.
            // Then, the new node becomes the new tail.
            if (this.tail) { // TypeScript might need this check, though logically tail won't be null if size > 0
                this.tail.next = newNode;
            }
            this.tail = newNode;
        }

        this.size++; // Increment the size of the list.
    }
}

Explanation:

1. We create a newNode with the provided value.
2. If the list is empty (this.size === 0): This newNode is the only node, so it becomes both the head and the tail.
3. If the list is not empty: We take the current tail node and update its next pointer to point to our newNode. Then, we update the this.tail reference to be our newNode. This effectively “links” the new node to the end and makes it the new last element.
4. Finally, we increment this.size.

Let’s visualize append (adding ‘D’ to a list with ‘A’, ‘B’, ‘C’):

Time Complexity of append: O(1) - Regardless of how many elements are in the list, we only perform a few constant-time operations (create a node, update 1-2 pointers). This is a huge advantage over arrays, where adding to the end might require reallocating memory and copying all elements (amortized O(1), but worst-case O(N)).

Adding Elements: prepend (Adding to the Beginning)

Adding to the beginning is similarly efficient.

// src/linkedList.ts (continued)

class LinkedList<T> {
    // ... (previous code) ...

    // Step 4: Implement the prepend method
    // Adds a new node to the beginning of the list.
    prepend(value: T): void {
        const newNode = new Node(value); // Create a new node.

        if (this.size === 0) {
            // Case 1: The list is currently empty.
            // Same as append: new node is both head and tail.
            this.head = newNode;
            this.tail = newNode;
        } else {
            // Case 2: The list is not empty.
            // The new node's 'next' pointer should point to the current head.
            // Then, the new node becomes the new head.
            newNode.next = this.head;
            this.head = newNode;
        }

        this.size++; // Increment the size.
    }
}

Explanation:

1. A newNode is created.
2. If the list is empty: Same as append, the new node becomes head and tail.
3. If the list is not empty: The newNode’s next pointer is set to point to the current head. Then, this.head is updated to be the newNode.
4. Increment this.size.

Time Complexity of prepend: O(1) - Again, a constant number of operations. This is a significant advantage over arrays, where inserting at the beginning requires shifting all existing elements, leading to O(N) complexity.

Retrieving Elements: get (By Index)

To retrieve an element at a specific index, we can’t jump directly like with arrays. We have to traverse from the head.

// src/linkedList.ts (continued)

class LinkedList<T> {
    // ... (previous code) ...

    // Step 5: Implement the get method
    // Retrieves the value of the node at a specific index.
    get(index: number): T | undefined {
        // Handle invalid index cases.
        if (index < 0 || index >= this.size) {
            console.error("Index out of bounds.");
            return undefined;
        }

        // Start traversing from the head.
        let currentNode = this.head;
        for (let i = 0; i < index; i++) {
            // Move to the next node until we reach the desired index.
            // We can safely assert currentNode.next exists because of the index check.
            currentNode = currentNode!.next;
        }

        // Return the value of the node at the specified index.
        return currentNode!.value; // currentNode will not be null here due to index check
    }
}

Explanation:

1. First, we perform boundary checks: if index is negative or greater than or equal to size, it’s an invalid request, so we return undefined.
2. We start currentNode at this.head.
3. We loop index times, moving currentNode to currentNode.next in each iteration.
4. After the loop, currentNode will be pointing to the node at the desired index. We return its value.

Time Complexity of get: O(N) - In the worst case (getting the last element), we have to traverse through all N nodes. This is a disadvantage compared to arrays, which offer O(1) random access.

Removing Elements: removeAt (By Index)

Removing an element also requires careful pointer manipulation.

// src/linkedList.ts (continued)

class LinkedList<T> {
    // ... (previous code) ...

    // Step 6: Implement the removeAt method
    // Removes the node at a specific index and returns its value.
    removeAt(index: number): T | undefined {
        // Handle invalid index cases.
        if (index < 0 || index >= this.size) {
            console.error("Index out of bounds for removal.");
            return undefined;
        }

        let removedValue: T | undefined;

        if (index === 0) {
            // Case 1: Removing the head node.
            removedValue = this.head!.value; // Store the value before losing the reference.
            this.head = this.head!.next;     // The new head is the old head's next node.

            if (this.size === 1) {
                // If there was only one node, the list is now empty.
                this.tail = null;
            }
        } else {
            // Case 2: Removing a node from the middle or end.
            let previousNode = this.head;
            for (let i = 0; i < index - 1; i++) {
                // Traverse to the node *before* the one we want to remove.
                previousNode = previousNode!.next;
            }

            const nodeToRemove = previousNode!.next; // This is the node we want to remove.
            removedValue = nodeToRemove!.value;

            // Link the previous node to the node *after* the one being removed.
            previousNode!.next = nodeToRemove!.next;

            if (nodeToRemove === this.tail) {
                // If we removed the tail, the previous node becomes the new tail.
                this.tail = previousNode;
            }
        }

        this.size--; // Decrement the size.
        return removedValue;
    }
}

Explanation:

1. Boundary Checks: Similar to get, we ensure the index is valid.
2. Removing the Head (index === 0):
   • We store the head’s value.
   • The head pointer is simply moved to the head.next node.
   • If the list becomes empty (was size === 1), tail also needs to be set to null.
3. Removing from Middle or End (index > 0):
   • We need to find the previousNode (the node before the one we want to remove). We traverse index - 1 times.
   • nodeToRemove is then previousNode.next.
   • We “skip” nodeToRemove by setting previousNode.next to nodeToRemove.next. This effectively removes nodeToRemove from the chain.
   • If nodeToRemove was the tail, then previousNode becomes the new tail.
4. Decrement this.size and return the removedValue.

Time Complexity of removeAt: O(N) - In the worst case (removing an element near the end), we have to traverse through N nodes to find the previousNode. This is a disadvantage compared to arrays for arbitrary index removal, but for removing the first element, it’s O(1).

Traversing and Printing: printList

It’s helpful to have a way to see the contents of our list.

// src/linkedList.ts (continued)

class LinkedList<T> {
    // ... (previous code) ...

    // Step 7: Implement the printList method
    // Iterates through the list and prints all values.
    printList(): void {
        if (this.size === 0) {
            console.log("List is empty.");
            return;
        }

        let currentNode = this.head;
        let listString = "";
        while (currentNode !== null) {
            listString += `${currentNode.value} -> `;
            currentNode = currentNode.next;
        }
        listString += "null"; // Indicate the end of the list.
        console.log(listString);
    }
}

Explanation:

1. If the list is empty, we print a message.
2. We start currentNode at this.head.
3. We loop while (currentNode !== null), adding each currentNode.value to our listString and then moving currentNode to currentNode.next.
4. Once currentNode becomes null, we’ve reached the end, and we print the full string.

Time Complexity of printList: O(N) - We visit every node once.

Putting it all together and testing

Let’s create an instance of our LinkedList and try out these methods.

// src/linkedList.ts (continued)

// --- Test your LinkedList ---
const myLinkedList = new LinkedList<number>(); // A list of numbers

console.log("Initial list:");
myLinkedList.printList(); // Output: List is empty.

console.log("\nAppending 10, 20, 30:");
myLinkedList.append(10);
myLinkedList.append(20);
myLinkedList.append(30);
myLinkedList.printList(); // Output: 10 -> 20 -> 30 -> null
console.log("Size:", myLinkedList.size); // Output: Size: 3
console.log("Head:", myLinkedList.head?.value); // Output: Head: 10
console.log("Tail:", myLinkedList.tail?.value); // Output: Tail: 30

console.log("\nPrepending 5:");
myLinkedList.prepend(5);
myLinkedList.printList(); // Output: 5 -> 10 -> 20 -> 30 -> null
console.log("Size:", myLinkedList.size); // Output: Size: 4
console.log("Head:", myLinkedList.head?.value); // Output: Head: 5

console.log("\nGetting element at index 2:");
console.log(myLinkedList.get(2)); // Output: 20

console.log("\nRemoving element at index 1 (value 10):");
const removed = myLinkedList.removeAt(1);
console.log("Removed value:", removed); // Output: Removed value: 10
myLinkedList.printList(); // Output: 5 -> 20 -> 30 -> null
console.log("Size:", myLinkedList.size); // Output: Size: 3
console.log("Head:", myLinkedList.head?.value); // Output: Head: 5
console.log("Tail:", myLinkedList.tail?.value); // Output: Tail: 30 (Still 30, correct!)

console.log("\nRemoving element at index 2 (tail, value 30):");
myLinkedList.removeAt(2);
myLinkedList.printList(); // Output: 5 -> 20 -> null
console.log("Size:", myLinkedList.size); // Output: Size: 2
console.log("Tail:", myLinkedList.tail?.value); // Output: Tail: 20 (Updated!)

console.log("\nAttempting to get out of bounds index 10:");
console.log(myLinkedList.get(10)); // Output: Index out of bounds. undefined

console.log("\nAttempting to remove out of bounds index -1:");
console.log(myLinkedList.removeAt(-1)); // Output: Index out of bounds for removal. undefined

To run this code:

1. Save the complete Node and LinkedList classes (and the test code) into src/linkedList.ts.
2. Compile it using tsc src/linkedList.ts.
3. Run the compiled JavaScript: node src/linkedList.js.

Observe the output carefully and verify that each operation behaves as expected. Pay attention to how head, tail, and size update.

Real-world Use Cases for Linked Lists

While raw arrays are often preferred for simple lists due to cache locality and O(1) random access, linked lists form the basis for many other data structures and appear in various scenarios:

• Implementing Stacks and Queues: As we’ll see in upcoming chapters, linked lists are a natural fit for building stacks (LIFO) and queues (FIFO) because insertions/deletions at the ends are O(1).
• Image Viewers/Music Playlists: “Next” and “Previous” functionality maps perfectly to a doubly linked list, allowing efficient traversal.
• Browser History: Navigating back and forth through visited web pages can be modeled with a doubly linked list.
• Undo/Redo Functionality: Similar to browser history, keeping track of states for undo/redo.
• Memory Management: Linked lists can be used to manage free blocks of memory in an operating system.
• Polynomial Representation: Each term in a polynomial (e.g., 3x^2 + 2x - 5) can be a node, with the next node representing the next term.
• File System Allocation: In some older file systems, files were stored in non-contiguous blocks on disk, with each block containing a pointer to the next block, similar to a linked list.

Mini-Challenge: Reversing a Linked List

This is a classic linked list problem that tests your understanding of pointer manipulation.

Challenge: Implement a reverse() method for your LinkedList class. This method should reverse the order of the nodes in the list in-place (meaning, you shouldn’t create a brand new list or new nodes, just change the next pointers).

// Add this method to your LinkedList class
// class LinkedList<T> { ...
//   reverse(): void {
//     // Your implementation here
//   }
// }

Hint: You’ll typically need three pointers:

1. current: The node you are currently processing.
2. previous: The node that current’s next pointer should point to after reversal.
3. nextNode: A temporary pointer to store current.next before you change current.next (otherwise you lose the rest of the list!).

What to observe/learn: This challenge will solidify your understanding of how delicate and powerful pointer manipulation can be. It’s a common interview question for a reason! Take your time, draw it out on paper, and trace the pointers.

Common Pitfalls & Troubleshooting

Working with linked lists is all about pointers, and that’s where most issues arise.

1. Null Pointer Exceptions (or undefined in TS): The most frequent error. Forgetting to check if head or currentNode.next is null before trying to access value or next will lead to runtime errors. Always ask: “Could this pointer be null here?”
   • Troubleshooting: Use optional chaining (?.) or explicit if (node !== null) checks. TypeScript’s strict null checks are a great help here, often forcing you to handle these cases.
2. Off-by-One Errors in Loops: When traversing to a specific index (get, removeAt), it’s easy to go one step too far or too short.
   • Troubleshooting: Carefully trace your loop conditions (i < index vs. i <= index) and how currentNode is updated. Draw the list and the pointers for each iteration.
3. Forgetting to Update head or tail: When adding to an empty list, removing the only element, or removing the last element, ensure head and tail are correctly updated (or set to null).
   • Troubleshooting: After any operation that changes the beginning or end of the list, double-check this.head and this.tail values.
4. Breaking the Chain: Accidentally overwriting a next pointer before saving a reference to the node it pointed to can “lose” the rest of your list. This is particularly common in the reverse() challenge.
   • Troubleshooting: Always store currentNode.next in a temporary variable before you modify currentNode.next.

Debugging linked lists often involves logging currentNode.value and currentNode.next?.value at each step of a loop, or using your debugger to step through and inspect pointer values.

Summary

Phew! You’ve just built a fundamental dynamic data structure from scratch. Let’s recap what we’ve learned in this chapter:

• What is a Linked List? A sequence of interconnected nodes, where each node contains data and a next pointer to the subsequent node.
• Dynamic Nature: Unlike arrays, linked lists don’t require contiguous memory, making insertions and deletions efficient at certain positions.
• Key Components:
  • Node: The basic building block, holding a value and a next reference.
  • Head: The starting point of the list.
  • Tail: The end of the list (often tracked for O(1) append).
  • Size: The number of nodes in the list.
• Core Operations & Complexities:
  • append(value): Adds to the end. O(1).
  • prepend(value): Adds to the beginning. O(1).
  • get(index): Retrieves by index. O(N) (requires traversal).
  • removeAt(index): Removes by index. O(N) (requires traversal to find previous node).
  • printList(): Traverses and displays all elements. O(N).
• Advantages: Efficient insertions and deletions at the ends (O(1)), dynamic size, no pre-allocation needed.
• Disadvantages: No random access (O(N) for get or removeAt in the middle), more memory overhead per node (due to the next pointer).
• Real-world Applications: Underpinning stacks, queues, browser history, image carousels, and more.

You’ve taken a significant step in understanding how data can be organized and manipulated beyond simple arrays. This conceptual clarity and practical implementation skill will be invaluable as we explore more complex data structures.

In the next chapter, we’ll build upon our understanding of linked lists to implement two crucial abstract data types: Stacks and Queues. Get ready to dive into LIFO and FIFO!

References

• Node.js v25.6.1 Documentation
• TypeScript Handbook - Generics
• MDN Web Docs - Data structures
• GeeksforGeeks - Linked List Introduction

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.