Understanding Linked Lists with Tail in TypeScript: A Deep Dive

Introduction

Hey there today will be focusing on the Linked List with Tail in TypeScript. A very useful data structure. Especially if implementing other types of linked lists such as queues and stacks.

What is a Linked List with Tail?

Basic Concept

A Linked List is like a treasure hunt, where each clue leads to the next. In technical terms, it's a collection of nodes, each pointing to the next node in the sequence. The twist? Our Linked List has a tail, a savvy shortcut that points directly to the last node. This little trick can save us a heap of time in certain operations.

Why Use a Linked List with Tail?

Efficiency in Certain Operations: With direct access to the tail, appending elements is a breeze.
Dynamic Size: Unlike arrays, it grows and shrinks gracefully, without the need for resizing.
Memory Savvy: It only uses the memory it needs, no more, no less.

Implementing a Linked List with Tail in TypeScript

There are often multiple ways of building the same thing. That is to say, not every linked list with a tail will be the same, nore the methods. However, the overall structure will be the same. In this case, i'll be implementing some methods to get the point across. But there may be others.

The Building Blocks

Node Structure


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

Linked List Structure


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

  // Methods will be added here
}

Utility Methods

There will be a bunch of useful methods to include here, such as 'isEmpty()', 'getSize()', 'print()':


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

getSize() {
	return this.size
}

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)
	}
}

Core Methods

Adding Elements


prepend(value: any) {
	const node = new Node(value)

	if (this.isEmpty()) {
		this.head = node
		this.tail = node
	} else {
		node.next = this.head
		this.head = node
	}
	this.size++
}

append(value: any) {
	const node = new Node(value)

	if (this.isEmpty()) {
		this.head = node
		this.tail = node
	} else {
		this.tail!.next = node
		this.tail = node
	}

	this.size++
}

Removing Elements


removeFromFront() {
	if (this.isEmpty()) {
		return null
	}

	const value = this.head!.value
	this.head = this.head!.next
	this.size--

	return value
}

removeFromEnd() {
	if (this.isEmpty()) {
		return null
	}

	const value = this.tail!.value

	if (this.size === 1) {
		this.head = null
		this.tail = null
	} else {
		let current = this.head
		while (current!.next !== this.tail) {
			current = current!.next
		}
		current!.next = null
		this.tail = current
	}

	this.size--
}

Searching


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++
		}
	}
}

Practical Tips and Insights

When to Use

Dynamic Collections: Perfect for when you don't know the size beforehand.
Frequent Additions/Deletions: Especially at the ends of the list.

Performance Considerations

Access Time: It's not an ace when it comes to random access. Arrays might be better in such cases.
Memory Overhead: Each node carries a little extra weight (the pointer to the next node).

Common Pitfalls

Circular References: Be careful! It's easy to accidentally create a loop.
Memory Leaks: When removing nodes, ensure you're not leaving any references hanging.

Conclusion

In the realm of data structures, the Linked List with Tail stands out for its elegance and practicality in certain scenarios. By understanding its nuances and implementing it wisely, you can optimize your TypeScript applications for better performance and efficiency.

Remember, the key to mastering any programming concept is practice, curiosity, and a dash of creativity.

Data Structures: Linked List with Tail in TypeScript