Introduction
LinkedLists
are a common data structure used in computer science. They are made up of one or more nodes, which consist of a data element and an address that references the next node in the list. The last node in the list contains a null reference to indicate the end of the list.
In this article, we implement a LinkedList
in JavaScript using two classes, Node
and LinkedList
. The Node
class is used to create a new node in the list, while the LinkedList
class manages the list as a whole.
Let's implement it based on this template:
function Node(data) {
// Implementation
}
function LinkedList() {
// Implementation
}
Implementation
The Node
constructor takes a single argument, data
, which is the value to be stored in the node. The constructor also initializes the next
property to null
, which will be set to the next node in the list if one exists.
function Node(data) {
this.data = data;
this.next = null;
}
The LinkedList constructor initializes three properties: head
, tail
, and length
. head
and tail
are both initialized to null, indicating an empty list.
function LinkedList() {
this.head = null;
this.tail = null;
this.length = 0;
}
The add
method adds a new node to the end of the list by creating a new Node
object and updating the tail
property to point to the new node.
LinkedList.prototype.add = function(item) {
const node = new Node(item);
if(!this.head) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.length++;
}
The toString
method creates a string representation of the list by iterating through each node and concatenating its value to the result string.
LinkedList.prototype.toString = function() {
let current = this.head;
let result = "";
while(current) {
result += current.data.toString() + ' ';
current = current.next;
}
return result.trim();
}
The getByIndex
method retrieves the value of the node at a given index by iterating through the list and stopping at the node with the corresponding index.
LinkedList.prototype.getByIndex = function(index) {
if(index > this.length - 1) {
throw Error('List index out of bounds');
}
let result = this.head;
for(let i = 0; i < index; i++) {
result = result.next;
}
return result.data;
}
The remove
method removes a node from the list by iterating through the list and updating the next
property of the previous node to point to the next node in the list.
LinkedList.prototype.remove = function(data) {
let current = this.head;
if(!current) {
return false;
}
if(current.data === data) {
this.head = current.next;
this.length--;
return true;
}
while(current.next) {
if(current.next.data === data) {
current.next = current.next.next;
this.length--;
return true;
}
current = current.next;
}
return false;
}
Finally, we implement the insertAfter
method, which inserts a new node into the list after a given node. This method finds the node with the given value and updates its next
property to point to the new node, while the next
property of the new node is set to the next
property of the original node.
LinkedList.prototype.insertAfter = function(afterData, data) {
const node = new Node(data);
let current = this.head;
while(current) {
if(current.data === afterData) {
node.next = current.next;
current.next = node;
this.length++;
return true;
}
current = current.next;
}
return false;
}
Summary
In conclusion, linked lists are a fundamental data structure in computer science, and this implementation in JavaScript can serve as a useful tool for managing data in web applications. By understanding the principles behind linked lists and implementing them in code, developers can gain a deeper understanding of data structures and algorithms.
Top comments (0)