Typescript Data Structures: Linked List

TypeScript's linked lists offer an alternative to traditional arrays, building data structures by connecting nodes instead of relying on indexed positions.

Understanding the Node

A linked list node consists of two key components:

  1. Data: This holds the actual information stored in the list, like numbers, strings, or even objects.
  2. Next pointer: This reference points to the next node in the list, creating a chain of data elements.

Basic Linked List Structure

A basic linked list consists of nodes, each containing data and a reference to the next node. The last node typically points to null, indicating the end of the list.

namespace LinkedListModule { export class Node<T> { data: T; next: Node<T> null; constructor(data: T) { this.data = data; this.next = null; } } export class LinkedList<T> { head: Node<T> null; constructor() { this.head = null; } append(data: T): void { const newNode = new Node(data); if (!this.head) { this.head = newNode; return; } let current = this.head; while (current.next) { current = current.next; } current.next = newNode; } print(): void { let current = this.head; while (current) { console.log(current.data); current = current.next; } } } } // Example usage: const myList = new LinkedListModule.LinkedList<number>(); myList.append(1); myList.append(2); myList.append(3); myList.print();

In this example, the Node class represents a node in the linked list, and the LinkedList class includes basic operations like appending a node and printing the contents.

Insertion and Deletion

Linked lists allow for efficient insertion and deletion of elements, as only the affected nodes need to be modified.

class LinkedList<T> { // ... (previous code) insertAt(index: number, data: T): void { const newNode = new Node(data); if (index === 0) { newNode.next = this.head; this.head = newNode; return; } let current = this.head; for (let i = 0; i < index - 1 && current; i++) { current = current.next; } if (!current) { return; // Index out of bounds } newNode.next = current.next; current.next = newNode; } deleteAt(index: number): void { if (index === 0) { if (this.head) { this.head = this.head.next; } return; } let current = this.head; for (let i = 0; i < index - 1 && current; i++) { current = current.next; } if (!current !current.next) { return; // Index out of bounds } current.next = current.next.next; } } // Example usage: myList.insertAt(1, 5); myList.deleteAt(2); myList.print(); // Outputs: 1, 5, 3

In this extension, the insertAt method inserts a new node at a specific index, and the deleteAt method removes a node at a given index.

Benefits and Drawbacks of Linked Lists

  1. Flexibility: Adding and removing nodes can be done efficiently at any point in the list without shifting other elements, unlike arrays.
  2. Dynamic memory allocation: Linked lists grow on demand and don't need pre-defined sizes, making them memory-efficient for some cases.
  3. Random access is slow: Accessing specific elements by index requires traversing the list from the beginning, making random access slower than in arrays.
  4. More complex implementation: Understanding and working with pointers and node manipulation requires more effort compared to arrays.

Doubly Linked List

A doubly linked list has nodes with references to both the next and previous nodes, allowing for easier traversal in both directions.

class DoublyNode<T> { data: T; next: DoublyNode<T> null; prev: DoublyNode<T> null; constructor(data: T) { this.data = data; this.next = null; this.prev = null; } } class DoublyLinkedList<T> { head: DoublyNode<T> null; constructor() { this.head = null; } append(data: T): void { const newNode = new DoublyNode(data); if (!this.head) { this.head = newNode; return; } let current = this.head; while (current.next) { current = current.next; } current.next = newNode; newNode.prev = current; } // Other methods can be added similarly }

The DoublyLinkedList class extends the linked list to support doubly linked nodes, allowing for backward traversal.

Practical Applications

  1. Undo/redo functionality: Implementing a stack-like behavior for storing previous states in a linked list allows easy undo/redo actions.
  2. Music playlists: Linked lists are ideal for representing playlists where adding, removing, and rearranging songs efficiently is crucial.
  3. Efficient document editing: Maintaining changes in large documents becomes efficient with linked lists, as only affected parts require manipulation.

Points to Remember

  1. Choosing linked lists over arrays depends on the specific needs of your program. Consider factors like dynamic growth, efficient insertion/deletion, and random access requirements.
  2. Utilize libraries or existing implementations of linked lists if building them from scratch seems complex.
  3. Master pointer manipulation and understand the dynamic nature of linked lists to unlock their full potential in your code.

Conclusion

Linked lists in TypeScript provide a flexible and dynamic alternative to arrays, particularly when frequent insertion and deletion operations are required. Choosing between singly and doubly linked lists depends on the specific requirements of the application.






Related Topics
  1. TypeScript Stack
  2. TypeScript Queues
  3. TypeScript Set
  4. TypeScript Map
  1. Typescript Tree