A linked list is a linear data structure in computer science that consists of a sequence of nodes, where each node contains a data element and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not have a fixed size and can be dynamically resized during runtime. Linked lists are commonly used in computer science for implementing various data structures such as stacks, queues, and hash tables. The main advantage of linked lists is their ability to efficiently insert and delete elements from the list, as well as their flexibility in terms of size and structure. Keep reading below to learn how to use a Linked List in TypeScript.
Looking to get a head start on your next software interview? Pickup a copy of the best book to prepare: Cracking The Coding Interview!
How to use a Linked List in TypeScript with example code
A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence. In TypeScript, we can implement a linked list using classes and interfaces.
To create a linked list, we first define a Node interface that describes the structure of a node:
interface Node<T> {
value: T;
next: Node<T> | null;
}
This interface defines a generic type parameter T that represents the type of the value stored in each node. The interface also has two properties: value, which stores the value of the node, and next, which is a reference to the next node in the sequence.
Next, we define a LinkedList class that implements the linked list:
class LinkedList<T> {
private head: Node<T> | null = null;
private tail: Node<T> | null = null;
public append(value: T): void {
const node: Node<T> = { value, next: null };
if (this.tail === null) {
this.head = this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
}
public prepend(value: T): void {
const node: Node<T> = { value, next: this.head };
if (this.head === null) {
this.head = this.tail = node;
} else {
this.head = node;
}
}
public delete(value: T): void {
if (this.head === null) {
return;
}
if (this.head.value === value) {
this.head = this.head.next;
if (this.head === null) {
this.tail = null;
}
return;
}
let node: Node<T> = this.head;
while (node.next !== null) {
if (node.next.value === value) {
node.next = node.next.next;
if (node.next === null) {
this.tail = node;
}
return;
}
node = node.next;
}
}
public toArray(): T[] {
const result: T[] = [];
let node: Node<T> | null = this.head;
while (node !== null) {
result.push(node.value);
node = node.next;
}
return result;
}
}
This class has three methods: append, prepend, and delete. The append method adds a new node to the end of the linked list, the prepend method adds a new node to the beginning of the linked list, and the delete method removes a node with a given value from the linked list. The toArray method returns an array of values in the linked list.
Here’s an example of how to use the LinkedList class:
const list = new LinkedList<number>();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.delete(2);
console.log(list.toArray()); // [0, 1, 3]
In this example, we create a new linked list, add four nodes to it, remove one node, and then print the values of the remaining nodes.
What is a Linked List in TypeScript?
In conclusion, a Linked List in TypeScript is a powerful data structure that allows for efficient storage and manipulation of data. It is a collection of nodes that are linked together through pointers, with each node containing a value and a reference to the next node in the list. Linked Lists are particularly useful when dealing with large amounts of data that need to be accessed and modified frequently. They are also highly customizable, allowing developers to create their own implementations to suit their specific needs. With its many benefits and versatility, a Linked List is a valuable tool for any TypeScript developer to have in their arsenal.
Elevate your software skills
Ergonomic Mouse |
Custom Keyboard |
SW Architecture |
Clean Code |
