Demystifying Data Structures: A Deep Dive into Linked Lists in TypeScript

Introduction

Hey there, fellow coder! Let's embark on an intriguing journey through the realms of data structures. Today, we're honing in on Linked Lists, a fundamental yet fascinating concept, especially when explored in the context of TypeScript. Whether you're a novice dipping your toes into the programming world or a seasoned developer looking to brush up your skills, this guide aims to enlighten, engage, and elevate your understanding of Linked Lists. So, buckle up and get ready for an insightful expedition!

Understanding Linked Lists

The Basics: What is a Linked List?

Imagine you're on a treasure hunt. You find a clue, and that clue leads you to the next, and so on. A linked list operates on a similar principle. It's a linear collection of elements, termed as nodes, where each node points to the next one in the sequence. This structure allows for efficient insertion and removal of elements without the need for reorganization.

Singly vs Doubly Linked Lists

Singly Linked Lists: Here, each node has a value and a pointer to the next node. Think of it as a one-way street.
Doubly Linked Lists: These nodes are like two-way streets. They have pointers to both the next and the previous node, offering more flexibility.

Why Linked Lists?

Dynamic Size: Unlike arrays, they can expand and contract as needed.
Ease of Insertion/Deletion: Adding or removing elements doesn't require shifting other elements, as in the case of arrays.

Implementing a Linked List in TypeScript

Setting the Stage

Before we dive in, let's set up our TypeScript environment. Ensure you have TypeScript installed and ready to roll.

Crafting the Node Class

The building block of our linked list is the node. Let's craft it:


export class Node {
	value
	next: null | Node
	constructor(value: any) {
		this.value = value
		this.next = null
	}
}

Assembling the Linked List Class

Now, let's piece together our linked list:


export class LinkedList {
	head: null | Node
	size: number
	
	constructor() {
		this.head = null
		this.size = 0
	}

    // Methods will go here
}

Required Utilitiy methods

isEmpty() and getSize().


isEmpty() {
	return this.size === 0
}

getSize() {
	return this.size
}

Methods of Engagement

Adding Elements


// Add to beginning of list
prepend(value: any) {
	const node = new Node(value)
	if (!this.isEmpty()) {
		node.next = this.head
	}
	this.head = node
	this.size++
}

// Add to the end of the list
append(value: any) {
	const node = new Node(value)
	if (this.isEmpty()) {
		this.head = node
	} else {
		let previous = this.head

		while (previous?.next) {
			previous = previous.next
		}

		previous!.next = node
	}
	this.size++
}

// Insert
insert(value: any, index: number) {
	if (index < 0 || index > this.size) {
		return
	}

	if (index === 0) {
		this.prepend(value)
	} else {
		const node = new Node(value)
		let prev = this.head

		for (let i = 0; i < index - 1; i++) {
			prev = prev!.next
		}

		node.next = prev!.next
		prev!.next = node
		this.size++
	}
}

Removing Elements


// Remove from specific index
removeFrom(index: number) {
    if (index < 0 || index > this.size) {
		return null
	}

	let removedNode = null

	if (index === 0) {
		removedNode = this.head
		this.head = this.head!.next
	} else {
    	let prev = this.head
		for (let i = 0; i < index - 1; i++) {
			prev = prev!.next
		}
		removedNode = prev!.next
		prev!.next = removedNode!.next
	}

	this.size--
	return removedNode?.value
}

// remove a value
removeValue(value: any) {
	if (this.isEmpty()) {
		return null
	}

	if (this.head?.value === value) {
		this.head = this.head!.next
		this.size--
		return value
	} else {
		let prev = this.head
		while (prev!.next && prev!.next.value !== value) {
			prev = prev!.next
		}

		if (prev?.next) {
			let removedNode = prev!.next
			prev!.next = removedNode!.next
			this.size--
			return value
		}
		return null
	}
}

Other Utility Classes

Here we will just add the ability to search, and print so we can see what is in the list. And reverse the list.


    searchValue(value: any) {
		if (this.isEmpty()) {
			return -1
		} else {
			let i = 0
			let current = this.head

			while (current) {
				if (current.value === value) {
					return i
				}
				current = current.next
				i++
			}
		}
	}

	reverse() {
		let prev = null
		let current = this.head

		while (current) {
			let next = current.next
			current.next = prev
			prev = current
			current = next
		}

		this.head = prev
	}

	print() {
		if (this.isEmpty()) {
			console.log("List is empty")
			return
		} else {
			let current = this.head
			let output = ""
			while (current) {
				output += current.value
				output += current.next ? " -> " : ""
				current = current.next
			}

			console.log("linked list: ", output)
		}
	}

Putting It Into Action

Let's create a linked list and play around with it:


let myList = new LinkedList<number>();
myList.append(10);
myList.append(20);

Best Practices and Tips

Type Safety: TypeScript's strong typing helps in preventing many common errors. Use it to your advantage. Testing: Always test your data structures. Edge cases, like an empty list, are crucial to consider. Optimization: Think about time and space complexity. Linked lists are great, but they might not always be the optimal solution.

Conclusion

And there you have it! We've navigated through the ins and outs of Linked Lists in TypeScript. From the conceptual groundwork to practical implementation, we've covered substantial terrain. Remember, the world of data structures is vast and rich. Keep exploring, keep learning, and most importantly, keep coding!

Data Structures: Linked List in TypeScript