Linked lists are a fundamental data structure used in computer science and software development. They consist of a sequence of nodes, where each node contains a value and a reference (or “pointer”) to the next node in the sequence. Unlike arrays, linked lists do not store their elements in contiguous memory locations. Instead, each node can be located at any location in memory, and is linked to its adjacent nodes through its pointers. In this post we will discuss how you should be creating a linked list in javascript with code examples.
Creating a Node Class
The first step in creating a linked list in JavaScript is to define a Node class. The Node class represents each individual node in the linked list, and contains two properties: a data property that stores the node’s value, and a next property that points to the next node in the sequence.
Here’s an example implementation of a Node class in JavaScript:
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
In this implementation, the Node class takes a data parameter in its constructor, which is used to set the data property of the node. We also set the next property of the node to null by default. Because at the time of creation, the node does not yet have a reference to the next node in sequence.
Creating a LinkedList Class
The next step in creating a linked list in JavaScript is to define a LinkedList class. The LinkedList class manages the nodes in the list, and provides methods for adding, removing, and traversing the list.
Here’s an example implementation of a LinkedList class in JavaScript:
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}
add(data) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
} else {
let currentNode = this.head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
this.length++;
}
traverse() {
let currentNode = this.head;
while (currentNode !== null) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
}
remove(data) {
let currentNode = this.head;
let previousNode = null;
while (currentNode !== null) {
if (currentNode.data === data) {
if (previousNode === null) {
this.head = currentNode.next;
} else {
previousNode.next = currentNode.next;
}
this.length--;
return;
}
previousNode = currentNode;
currentNode = currentNode.next;
}
}
}
In this implementation, the LinkedList class takes no parameters in its constructor. Instead, it initializes two properties. The head property, which is initially set to null, and the length property, which is initially set to 0.
Adding Nodes to the LinkedList
The first method we will add to the LinkedList class is the add method, which adds a new node to the end of the list. To do this, we create a new Node object with the specified data, and then traverse the list until we find the last node. We then set the next property of the last node to the new node.
Here’s an example implementation of an add method for the LinkedList class:
class LinkedList {
// constructor omitted for brevity
add(data) {
const newNode = new Node(data);
if (this.head === null) {
this.head = newNode;
} else {
let currentNode = this.head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
} currentNode.next = newNode;
}
this.length++;
}
}In this implementation, we first create a new Node object using the data parameter passed to the add method. We then check if the list is empty by checking if this.head is null. If the list is empty, we set the head property to the new node. Otherwise, we traverse the list by setting currentNode to the head of the list. We then follow the next pointers until we reach the last node in the list. After that we set the next property of the last node to the new node, effectively adding the new node to the end of the list.
Traversing the LinkedList
The next method we will add to the LinkedList class is the traverse method. This method simply traverses the list and prints the value of each node. To do this, we start at the head of the list, and follow the next pointers until we reach the end of the list.
Here’s an example implementation of a traverse method for the LinkedList class:
class LinkedList {
// constructor and add method omitted for brevity
traverse() {
let currentNode = this.head;
while (currentNode !== null) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
}
}In this implementation, we first set currentNode to the head of the list. We then enter a while loop that continues as long as currentNode is not null. Inside the loop, we print the value of currentNode, and then set currentNode to the next node in the list.
Removing Nodes from the LinkedList
The final method we will add to the LinkedList class is the remove method, which removes a node with the specified value from the list. To do this, we traverse the list until we find the node with the specified value, and then update the next property of the previous node to skip over the node to be removed.
Here’s an example implementation of a remove method for the LinkedList class:
class LinkedList {
// constructor and add method omitted for brevity
remove(data) {
let currentNode = this.head;
let previousNode = null;
while (currentNode !== null) {
if (currentNode.data === data) {
if (previousNode === null) {
this.head = currentNode.next;
} else {
previousNode.next = currentNode.next;
}
this.length--;
return;
}
previousNode = currentNode;
currentNode = currentNode.next;
}
}
}In this implementation, we first set currentNode to the head of the list, and previousNode to null. We then enter a while loop that continues as long as currentNode is not null. Inside the loop, we check if currentNode’s data property is equal to the data parameter passed to the remove method. If so, we check if previousNode is null, indicating that the node to be removed is the head of the list. If previousNode is null, we simply set the head property to the next node in the list. Otherwise, we update the next property of previousNode to skip over the node to be removed. We then decrement the length property and return from the method. If we do not find the node to be removed, we simply update previousNode to currentNode, and currentNode to the next node in the list, and continue the loop.
Wrap Up
In this blog post, we have discussed concepts of linked lists and how to create a linked list in JavaScript. We have defined a Node class to represent individual nodes in the list. Also a LinkedList class to manage the nodes and provide methods for adding, removing, and traversing the list. We have also provided code examples for each of these methods. While this is a basic implementation of a linked list, it can be extended and modified in many ways.
For example, one common extension to the basic linked list is to create a doubly linked list, where each node has both a next and a previous pointer, allowing for traversal of the list in both directions. Another common modification is to implement a circular linked list, where the last node in the list has a next pointer that points back to the head of the list, creating a loop. This can be useful in certain applications where we want to continuously cycle through a set of elements.
In addition, linked lists can be used as the underlying data structure for a variety of more complex data structures, such as stacks, queues, and hash tables. For example, a stack can be implemented using a linked list where the top of the stack is represented by the head of the list, and elements are added and removed from the head of the list. Similarly, a queue can be implemented using a linked list where elements are added to the tail of the list and removed from the head of the list.
Conclusion
In conclusion, linked lists are a fundamental data structure in computer science, and understanding their implementation in JavaScript is important for any programmer. We have provided a basic overview of linked lists and shown how you should be creating a linked list. No only that, but we have covered the basic concepts of nodes, pointers, and traversal. We also provided code examples for adding, removing, and traversing nodes in the list. While this implementation is basic, it can be extended and modified in many ways.
If you enjoyed this article, check out our latest post on the easiest language to learn data structures and algorithms. As always, if you have any questions or comments feel free to contact us.
Pingback: Avoiding CSS Cross Browser Compatibility Issues - Tips & Tricks