In the vast expanse of data structures available to developers, the LinkedList holds a unique place. Known for its efficiency in insertion and deletion operations, it’s a staple in algorithm design and application development. This post explores how to implement a LinkedList in TypeScript, bringing together the efficiency of this data structure with the strong typing and object-oriented features of TypeScript.
Understanding LinkedLists
Before diving into the code, let’s grasp the basics of a LinkedList. At its core, a LinkedList is a collection of nodes, where each node contains data and a reference (or a pointer) to the next node in the sequence. This structure allows for efficient additions and deletions as it avoids the necessity of reindexing elements, a common performance bottleneck in array manipulations.
Implementing Nodes in TypeScript
The foundation of our LinkedList is the node. Each node will store a value and a pointer to the next node. Here’s how we define it in TypeScript:
class Node {
val: number;
next: Node | null;
constructor(val: number) {
this.val = val; // The value stored in the node
this.next = null; // Pointer to the next node, initially null
}
}
This Node class is straightforward: it initializes with a value and sets the pointer to the next node as null.
The MyLinkedList Class
With our nodes defined, we next construct the LinkedList class, MyLinkedList. This class will manage our nodes and provide methods to interact with the list.
Constructor and Properties
class MyLinkedList {
head: Node | null;
tail: Node | null;
size: number;
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
Our LinkedList starts empty, signified by a null head and tail, with a size of 0.
Adding Elements
We provide three methods to add elements to our list: at the head, at the tail, and at a specific index.
- addAtHead(val: number): Inserts a new node with the provided value at the beginning of the list.
- addAtTail(val: number): Appends a new node with the provided value at the end of the list.
- addAtIndex(index: number, val: number): Inserts a new node at the specified index.
Each method updates the head, tail, and size properties accordingly to maintain the integrity of the list.
Retrieving and Deleting Elements
- get(index: number): Returns the value of the node at the specified index.
- deleteAtIndex(index: number): Removes the node at the specified index.
These methods ensure our LinkedList is dynamic, allowing retrieval and modification post-initialization.
Conclusion
Implementing a LinkedList in TypeScript is a rewarding exercise that deepens our understanding of both TypeScript and fundamental data structures. This guide has walked you through creating a flexible, type-safe LinkedList, suitable for various applications requiring efficient insertions and deletions. Whether you’re building a complex application or brushing up on data structures, the combination of TypeScript and LinkedLists is a powerful tool in your development arsenal.
Next Steps
Now that you’ve implemented a basic LinkedList, consider extending its functionality. Try adding methods to reverse the list, detect cycles, or merge two sorted lists. Each addition will not only improve your understanding of LinkedLists but also enhance your problem-solving skills in TypeScript.
Full Code
class Node {
val: number;
next: Node | null;
constructor(val: number) {
this.val = val; // The value stored in the node
this.next = null; // Pointer to the next node, initially null
}
}
class MyLinkedList {
head: Node | null;
tail: Node | null; // Pointer to the last node
size: number; // The number of nodes in the list
constructor() {
this.head = null; // Initialize the head to null for an empty list
this.tail = null; // Likewise for the tail
this.size = 0; // Start with a list size of 0
}
// Adds a node at the front of the list
addAtHead(val: number): void {
const newNode = new Node(val);
newNode.next = this.head;
this.head = newNode;
if (this.size === 0) {
this.tail = newNode; // If the list was empty, this new node is also the tail
}
this.size++;
}
// Adds a node at the end of the list
addAtTail(val: number): void {
const newNode = new Node(val);
if (this.size === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
// Adds a node at the specified index
addAtIndex(index: number, val: number): void {
if (index < 0 || index > this.size) return; // Check for valid index
if (index === 0) {
this.addAtHead(val);
return;
}
if (index === this.size) {
this.addAtTail(val);
return;
}
const newNode = new Node(val);
let current = this.head;
for (let i = 0; i < index - 1; i++) { // Iterate to the node before the desired index
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
this.size++;
}
// Gets the value of the node at the specified index
get(index: number): number {
if (index < 0 || index >= this.size) return -1; // Check for valid index
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
}
return current.val;
}
// Deletes the node at the specified index
deleteAtIndex(index: number): void {
if (index < 0 || index >= this.size) return; // Check for valid index
if (index === 0) {
this.head = this.head.next;
if (index === this.size - 1) { // If there was only one node, update tail to null
this.tail = null;
}
} else {
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
current.next = current.next.next;
if (index === this.size - 1) { // If deleting the last node, update tail
this.tail = current;
}
}
this.size--;
}
}
Also this one can let you pass the Leetcode question: 707. Design Linked List
这个博客讲的就是TypeScript的单链表的实现方法啦，可以看看 抄抄，这个能让你直接通过Leetcode的第707题