Let's Visualize Singly Linked Lists

What is a Linked List?

A Linked List is a data structure composed of Nodes. Each Node contains two key components:

• A value (such as a number or string).
• A next property, which serves as a reference or pointer to the next Node in the Linked List.

In this post, we'll focus on Singly Linked Lists, where each Node points to the next one in a single direction.

What's a Node?

A Node is the building block of a Linked List. Here's an example of how a Node works:

Under the hood, a Node looks like this:

{value: 3, next: null}

It can also store other types of data, such as a string:

In TypeScript, here is how we create a Node.

class Node<T> {
	value: T;
	next: Node<T> | null;

	constructor(value: T, next: Node<T> | null = null) {
		this.value = value;
		this.next = next;
	}
}

This class defines a generic Node that accepts a value of type T and a next property, which can either point to another Node or be null (if there is no next Node).

To create a Node:

const myNode = new Node(3, null)

This creates a Node with a value of 3 and no subsequent Node.

Visualizing a Linked List

As you can see, it is simply a chain of Nodes that reference the next, with a tail value that always ends with null.

Let's write the code to create a Linked List.

 class LinkedList<T> {
	private head: Node<T> | null;
	private length: number;

	constructor() {
		this.head = null;
		this.length = 0;
	}

	insertAtHead(data: T): void {
		// Runs in constant time
		const newHeadNode = new Node(data, this.head);
		this.length++;
		this.head = newHeadNode;
	}

Initializing the Linked List

To begin, we specify the type of data that the Linked List will hold. For this example, we'll use numbers as the type for the nodes:

const myList = new LinkedList<number>();

Adding Nodes to the Linked List

To add nodes, we use the insertAtHead method. This method inserts new nodes at the "head," or the first position, of the Linked List. Here's how it works in practice:

myList.insertAtHead(1);
myList.insertAtHead(2);
myList.insertAtHead(3);

console.log(myList.traverse()); // Prints [3, 2, 1]

When you call insertAtHead, you pass in the data for the new node. Internally, the method creates a new Node instance and:

1. Sets the passed data as the value of the new node.
2. Points the next property of the new node to the current head of the Linked List.
3. Updates the Linked List's head to this new node.

If the current head is null (i.e., the list is empty), the new node's next property remains null. Otherwise, it points to the previous head node.

If the current head has a value, then that becomes the next node value. If the current head has a null value, then that also becomes the next node value.

Try Updating the Head of the LL

Retrieving a Node by Index

Let's say we want to get the value of the node at position 1 in the list.

To find the value of a node at a specific position in the list, we use the getByIndex method:

getByIndex(index: number): Node<T> | null {
	if (index < 0 || index >= this.length) return null;

	let current = this.head;
	for (let i = 0; i < index; i++) {
		current = current.next;
	}
	return current;
}

This method works as follows:

1. Checks if the provided index is within the valid range of the list. If not, it returns null.
2. Iterates through the list until it reaches the specified index.
3. Returns the node at that index.

For example:

const theIndexNode = myList.getByIndex(1).value //returns 2

Removing the Head Node

This method:

1. Checks if the head node exists.
2. If it exists, it updates the head to point to the next node.
3. Decreases the length of the list.

removeHead(): void {
	if (!this.head) return;
	this.head = this.head.next;
	this.length--;
}

Removing a Node by Index

To remove a node at any position, we use the removeAtIndex method:

removeAtIndex(index: number) {
	if (index === 0) return this.removeHead();

	const prevIndex = this.getByIndex(index - 1);
	if (prevIndex === null) return null;

	prevIndex.next = prevIndex.next.next;
	this.length--;
}

This method:

1. Handles the special case where the index is 0 by calling removeHead.
2. Retrieves the previous node (the node before the one to be removed).
3. Updates the next property of the previous node to skip over the node being removed.
4. Decreases the length of the list.

Visualizing Node Removal

Pass in the index position of the node you'd like to delete from the Linked List. As you see, if you pass in a viable index position, that node will disappear from the list.

Conclusion

We've covered the basics of Linked List operations, including adding nodes, retrieving nodes by index, and removing nodes. These methods form the foundation of working with Linked Lists. In the next post, we'll explore Doubly Linked Lists, a variation that allows traversal in both directions.

For the source code, visit my GitHub!