Introduction to Linked List Manipulation in TypeScript

Welcome to our hands-on exploration of linked lists! Like a necklace of interconnected links, a linked list is a collection of elements, each pointing to the next. Today, we're moving from theory to practice, and you'll learn to reverse a linked list using a stack and determine the length of a linked list through our practical examples. These skills will give you a deeper understanding of how these structures work.

In this lesson, we will use the following LinkedList implementation for both considered problems:

class ListNode<T> {
    value: T;
    next: ListNode<T> | null;

    constructor(value: T, next: ListNode<T> | null = null) {
        this.value = value;
        this.next = next;
    }
}

class LinkedList<T> {
    head: ListNode<T> | null;

    constructor() {
        this.head = null;
    }

    append(data: T): void {
        const newNode = new ListNode(data);
        if (!this.head) {
            this.head = newNode;
        } else {
            let currentNode = this.head;
            while (currentNode.next) {
                currentNode = currentNode.next;
            }
            currentNode.next = newNode;
        }
    }
}

It is the same as we had in the previous lesson.

Consider a to-do list on sticky notes, where each task points to the next by stacking on top. You'd want first to reverse this stack to focus on the most recent tasks. Similarly, to reverse the order of a linked list, we'll use a stack data structure.

Imagine an application feature displaying user activities, with the most recent ones appearing first. This requires reversing the list of events to display the latest entries.

A stack's Last-In-First-Out (LIFO) property can be leveraged here to reverse the list succinctly. Pushing the list nodes' values onto the stack and then popping them out naturally reverses their order.

We can now build a function that takes the list and returns a reversed array:

function printReverse<T>(list: LinkedList<T>): void {
    let stack: T[] = []; // Initialize the stack
    let currentNode: ListNode<T> | null = list.head; // Start from the head

    while (currentNode !== null) {
        stack.push(currentNode.value); // Push the value onto the stack
        currentNode = currentNode.next; // Move to the next node
    }

    // Pop values from the stack to print the values in reverse
    while (stack.length > 0) {
        console.log(stack.pop() as T);
    }
}

let list = new LinkedList<number>();
list.append(1);
list.append(7);
list.append(3);
printReverse(list);  // 3 7 1

Every push adds an element to the stack, and every pop removes the last added element, resulting in a reversed order.