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:

TypeScript
Copy to clipboard
1class ListNode<T> {
2    data: T;
3    next: ListNode<T> | null;
4
5    constructor(data: T, next: ListNode<T> | null = null) {
6        this.data = data;
7        this.next = next;
8    }
9}

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:

TypeScript
Copy to clipboard
1class LinkedList<T> {
2    head: ListNode<T> | null;
3
4    constructor() {
5        this.head = null;
6    }

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:

TypeScript
Copy to clipboard
1append(data: T): void {
2    const newNode = new ListNode(data);
3    if (!this.head) {
4        this.head = newNode;
5    } else {
6        let currentNode: ListNode<T> = this.head;
7        while (currentNode.next) {
8            currentNode = currentNode.next;
9        }
10        currentNode.next = newNode;
11    }
12}

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.

The addFirst method inserts a new node at the beginning of the linked list, making it the new head of the list.

TypeScript
Copy to clipboard
1addFirst(data: T): void {
2    const newNode = new ListNode(data);
3    newNode.next = this.head;
4    this.head = newNode;
5}

This method accepts a data parameter, forms a new node, assigns its next to the current head, and sets newNode as the new head. With its constant time complexity, O(1), this method efficiently adds nodes at the start without traversal, ideal for scenarios like implementing a stack with frequent additions to the beginning.

The delete method removes the first node with a specific data value from the linked list.

TypeScript
Copy to clipboard
1delete(data: T): void {
2    if (!this.head) {
3        return;
4    }
5
6    if (this.head.data === data) {
7        this.head = this.head.next;
8        return;
9    }
10
11    let current: ListNode<T> = this.head;
12    while (current.next) {
13        if (current.next.data === data) {
14            current.next = current.next.next;
15            return;
16        }
17        current = current.next;
18    }
19}

This method handles two scenarios: If the head node's data matches the input data, the head is set to the next node. Otherwise, it traverses the list, adjusting pointers to bypass and remove the target node. The while loop checks each node’s next property for the target, updating current.next to bypass the target if found, ensuring its removal. If the node isn't found, no list alterations occur.

In a linked list, operations take different amounts of time, depending on their nature. Complexity analysis helps us understand both this time factor and memory usage.

For instance, accessing an element in a linked list has a time complexity of $O(n)$ because, in the worst-case scenario, we might traverse through the entire list. Alternatively, adding or removing a node at the beginning only requires $O(1)$ time, whereas it's $O(n)$ for other locations.

Congratulations on reaching this point! You've mastered implementing, manipulating, and traversing linked lists in TypeScript, along with complexity analysis and utility functions.

Next, we'll take this newly acquired knowledge for a spin in the upcoming hands-on sessions! This practice will clarify your understanding of linked lists as if polishing a diamond. Brace yourself!