Alright, fellow coders, it’s time to talk about a fundamental data structure that’s as classic as the ‘Hello, World!’ of programming: the linked list. In JavaScript, we don’t have linked lists baked into the language like arrays or objects, but that doesn’t mean we can’t roll up our sleeves and whip up our own. So, let’s get our hands dirty and craft a linked list from scratch.
What’s a Linked List Anyway?
Before we jump into the code, let’s make sure we’re all on the same page. A linked list is a linear collection of elements, called nodes, where each node points to the next node in the sequence. This structure allows for efficient insertion and deletion of elements at any position in the list. Unlike arrays, linked lists don’t have indices, and you access elements by walking through the list, one node at a time.
Crafting a Node in JavaScript
Our linked list adventure begins with the humble node, the building block of our list. Here’s a simple Node class to get us started:
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
This Node class is straightforward – it has a data property to store the value and a next property, which will point to the following node in the list (or null if it’s the tail node).
Assembling the LinkedList Class
With our Node class ready, we can now define our LinkedList class. This class will manage our nodes and provide methods to operate on the list.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// Add a node to the front of the list
prepend(data) {
const newNode = new Node(data, this.head);
this.head = newNode;
this.size++;
}
// Add a node to the end of the list
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
this.size++;
}
// Insert a node at a specific index (zero-based)
insertAt(data, index) {
if (index < 0 || index > this.size) {
throw new Error('Index out of bounds');
}
if (index === 0) {
this.prepend(data);
return;
}
const newNode = new Node(data);
let current = this.head;
let previous;
let count = 0;
while (count < index) {
previous = current;
current = current.next;
count++;
}
newNode.next = current;
previous.next = newNode;
this.size++;
}
// ... More methods to come
}
In this LinkedList class, we’ve got a constructor that initializes the head to null and the size to 0. We’ve also added three methods:
prepend(data): Adds a new node with the provideddatato the start of the list.append(data): Adds a new node with the provideddatato the end of the list.insertAt(data, index): Inserts a new node with the provideddataat the specifiedindex.
These methods are the bread and butter of interacting with our linked list, allowing us to add data with ease.
Visualizing the LinkedList Operations
To really understand what’s happening, let’s visualize the operations:
- Prepending: Adds a new node at the head of the list.
- Appending: Traverses the list and adds a new node at the tail.
- Inserting: Walks to the desired index and weaves in a new node.
Testing Our LinkedList
It’s time to put our LinkedList class through its paces with a few examples:
const myList = new LinkedList();
myList.prepend(10);
myList.append(20);
myList.insertAt(15, 1);
console.log(myList);
Running this code, we’d expect our linked list to have three nodes with the values 10, 15, and 20 in that order.
Next Steps
We’ve laid the groundwork for our JavaScript linked list, but there’s more to explore. Up next, we’ll dive into methods for removing nodes, searching for data, and traversing the list to print out its contents.
Stay tuned, because once we’ve got those pieces in place, we’ll be able to use our linked list for all sorts of algorithms and applications. And remember, while there are libraries out there like linked-list that provide linked list implementations, understanding the nuts and bolts of how they work is crucial for any serious JavaScript developer.
So, keep your coding gloves on, and let’s get ready to continue building our linked list expertise.
Removing Nodes from Our LinkedList
A linked list wouldn’t be complete without the ability to remove nodes. Let’s implement a couple of methods to remove nodes both by their value and by their index.
class LinkedList {
// ... Previous methods
// Remove a node by its value
removeData(data) {
let current = this.head;
let previous = null;
while (current !== null && current.data !== data) {
previous = current;
current = current.next;
}
if (current === null) {
return null;
}
if (previous === null) {
this.head = current.next;
} else {
previous.next = current.next;
}
this.size--;
return current.data;
}
// Remove a node by its index
removeAt(index) {
if (index < 0 || index >= this.size) {
throw new Error('Index out of bounds');
}
let current = this.head;
let previous = null;
let count = 0;
if (index === 0) {
this.head = current.next;
} else {
while (count < index) {
previous = current;
current = current.next;
count++;
}
previous.next = current.next;
}
this.size--;
return current.data;
}
// ... More methods to come
}
With removeData(data) and removeAt(index), we can now remove nodes by searching for a specific value or by specifying the index at which the node is located.
Finding Data in the LinkedList
Sometimes, you need to check if a value exists within your list. Here’s how you can implement a contains method:
class LinkedList {
// ... Previous methods
// Check if the list contains a value
contains(data) {
let current = this.head;
while (current !== null) {
if (current.data === data) {
return true;
}
current = current.next;
}
return false;
}
}
Traversing and Printing the LinkedList
To visualize our list, we’ll need a way to traverse it and print out the values. Here’s a printList method that does just that:
class LinkedList {
// ... Previous methods
// Print out the list's elements
printList() {
let current = this.head;
let result = '';
while (current) {
result += `${current.data} -> `;
current = current.next;
}
result += 'null';
console.log(result);
}
}
Putting It All Together
Now that we’ve got a robust LinkedList class, let’s see it in action:
const myList = new LinkedList();
myList.append(5);
myList.append(10);
myList.prepend(1);
myList.insertAt(7, 2);
console.log('List after adding elements:');
myList.printList();
console.log('Does the list contain 10? ', myList.contains(10));
myList.removeData(5);
console.log('List after removing the value 5:');
myList.printList();
myList.removeAt(1);
console.log('List after removing the element at index 1:');
myList.printList();
When we run this code, we’ll see the list grow and shrink as we add and remove elements, and we’ll verify whether certain values are in the list.
Conclusion
Congratulations! You’ve just built a fully functional linked list in JavaScript. While JavaScript engines don’t provide a native linked list, we’ve seen that they’re not too tricky to implement. Understanding these fundamental data structures can significantly improve your problem-solving skills and give you a deeper understanding of how higher-level abstractions work under the hood.
Remember, practice makes perfect. So, go ahead and extend this linked list with more features, like reversing the list or detecting cycles. The more you play with it, the better you’ll understand it.
Happy coding, and never stop learning!