Welcome to our tutorial focusing on Linked List Operations using TypeScript. Singly-Linked Lists (or just Linked Lists) are one of the most fundamental data structures used in computer science. They provide an efficient way to store and access data that is not necessarily contiguous in memory. This distinctive feature sets linked lists apart from arrays, making them an essential tool in a programmer's toolkit.

To work with linked lists, we first need to define a ListNode class, which represents a node within the linked list, utilizing TypeScript's type annotations for clarity and type safety.

TypeScript
Copy to clipboard
1class ListNode {
2    value: number;
3    next: ListNode | null;
4
5    constructor(value: number = 0, next: ListNode | null = null) {
6        this.value = value;  // Holds the value or data of the node
7        this.next = next;  // Points to the next node in the linked list; default is null
8    }
9}
10
11// Initialization of a linked list
12let head: ListNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

In the ListNode class:

• value holds the data of the node.
• next is a reference to the next node in the linked list. It defaults to null, indicating that the node does not link to any other node when freshly created.

Understand that a linked list is a linear data structure where each element is a separate object called a node. A node comprises data and a reference (link) to the next node in the sequence.

The provided code creates a linked list where each node points to another as follows: 1 -> 2 -> 3 -> 4 -> 5, and the last node points to null.

A common operation to practice with linked lists is reversing them, which is frequently encountered in interviews and industry tasks. To reverse a linked list, we need to sequentially rearrange the next link of each node to point back to its previous node.

Here's how the code might look using TypeScript. Note that this code uses $O(1)$ of additional memory:

TypeScript
Copy to clipboard
1class ListNode {
2    val: number;
3    next: ListNode | null;
4
5    constructor(val: number, next: ListNode | null = null) {
6        this.val = val;
7        this.next = next;
8    }
9}
10
11function reverseLinkedList(head: ListNode | null): ListNode | null {
12    let prev: ListNode | null = null;
13    let next: ListNode | null = null;
14    while (head) {
15        next = head.next;
16        head.next = prev;
17        prev = head;
18        head = next;
19    }
20    return prev;
21}
22
23let head: ListNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
24for (let node: ListNode | null = reverseLinkedList(head); node; node = node.next) {
25    console.log(node.val);  // Output: 5 4 3 2 1
26}

I encourage you to observe, analyze, and understand the problem and its solution. This practice will facilitate a well-rounded understanding of linked list operations and their applications. By the end of the tutorial, you should feel more comfortable tackling linked list problems, enabling you to handle similar tasks in technical interviews. Let's proceed with practical exercises!