Linked List

What is a Linked List?

A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (commonly called a node) contains two parts:

Data: The actual data stored.
Next: A reference (or link) to the next node in the sequence.

Types of Linked Lists

Singly Linked List: Each node has only one link that points to the next node.
Doubly Linked List: Each node has two links, the next link that points to the next node and the previous link that points to the previous node.
Circular Linked List: The last node points back to the first node instead of pointing to null.

Advantages of Linked Lists

Dynamic Size: the size of a linked list can grow or shrink dynamically, unlink arrays which often have a fixed size.
Ease of Insertion/Deletion: Inserting or deleting a node doesn't require shifting elements, as in the case of arrays.

Typescript Implementation

Let's implement a basic singly linked list in Typescript:

class Node<T> {
 data: T;
 next: Node<T> | null;
 
 contructore(data: T) {
   this.data = data;
   this.next = null;
 }
}
 
class LinkedList<T> {
 head: Node<T> | null;
 
 constructor() {
   this.head = null;
 }
 
 append(data: T): void {
   const newNode = new Node(data);
   if (this.head === null) {
     this.head = newNode;
   } else {
     let current = this.head;
     while (current.next !== null) {
       current = current.next;
     }
     current.next = newNode;
   }
 }
}

References