Introduction to Linked Lists in TypeScript

Hello there! Today, our journey leads us into the world of linked lists, a fundamental data structure in computer programming. Have you ever thought about how a scavenger hunt works? You have a clue at the beginning, which leads you to the next one. Each clue points you to the next one until you find your treasure. Similarly, a linked list employs this concept — a sequence where each node points to the next one, just like clues in a scavenger hunt.

Though they store data sequentially, linked lists and arrays have fundamental differences. In an array, elements are stored in contiguous memory, while in a linked list, elements (or nodes) can be scattered throughout memory, connected by pointers. The dynamic structure of linked lists enables efficient insertions and deletions at any position, benefiting applications like a photo gallery, where we frequently add, update, and delete photos.

Let's begin to understand, implement, and manipulate linked lists in TypeScript!

A node in a linked list holds two types of information — data, which houses the actual value, and next, a reference to the subsequent node in the sequence. We use TypeScript's class with type annotations and generics to construct these nodes.

The TypeScript code below creates a ListNode class, providing a blueprint for every node:

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

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

T is a generic type parameter that allows the ListNode class to store any data type, enhancing flexibility. The constructor initializes the data and the next property, which defaults to null, indicating the absence of a subsequent node.

We start by defining the LinkedList<T> class storing the first node, called head:

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

    constructor() {
        this.head = null;
    }

Now, let's move to its methods!

The append method adds a new node at the end of the linked list. It accepts a data parameter of type T:

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

Initially, it checks if the head is null (indicating an empty list). If so, the new node becomes the head. Otherwise, it traverses from the head to the last node, setting the next property of the last node to newNode.