Linked List in JavaScript
What is Linked List?
Before diving into the details about Linked List, let’s quickly understand what Data Structure is.
In Computer Science, a data structure is a data organization, management and storage format that enables efficient access and modification of the data. A majority of data structures are inspired by real life scenarios. For example, we all place our clothes (data) in a wardrobe in a way so that the next time we need to choose something, we can easily find it.
Data structures store objects and allow their manipulation on the basis of two different types:
Now that we know about Data Structure, let’s learn what Linked List really is:
A Linked List is a linear collection of data elements. Elements are not stored in a particular memory location or index. Rather each element is a separate object that contains a pointer or reference to the next object in that list. It is a data structure consisting of a collection of nodes which together represent a sequence.
The entry point to a linked list is called the head. The head has a reference to the first node in the linked list. The last node in the list should point to null. If a list is empty, the head should have a null reference.
Implementing a List Node in JavaScript:
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}In the above code, we define a class Node having two properties: element and next. Element holds the data of a node and next holds a pointer to the next node, which is initialized to the null value.
Now, we can implement a Linked List class:
// linkedlist class
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//functions to implement: //Insert the first node
//insertFirst(data) {} //Inset last node
//insertLast(data) {} //Insert at a specific index
//insertAt(data, index) {} //Get value from a specific index
//getAt(index) {} // Remove at index
//removeAt(index) {} //Clear list
//clearList() {} //print list Data
//printListData() {}}
The above example demonstrates a Linked List class with a constructor and a list of methods to be implemented. Linked List class has two properties: i.e. head and size, where the head stores the first node of a List, and size indicates the number of nodes in a list.
We can now implement those functions one by one:
- insertFirst(data): This function adds an element/node at the beginning of the list
insertFirst(data) {
this.head = new Node(data, this.head);
this.size++;
}2. insertLast(data): It adds an element at the end of the list
insertLast(data) {
let node = new Node(data);
let current; //if the list is empty, add this node and make it head
if(!this.head) {
this.head = node;
} else {
current = this.head; //iterate to the end of the list
while (current.next) {
current = current.next;
}
//add the new node
current.next = node;
}
//increase the size of the list
this.size++;
}
Consider the following points while adding a node at the end of the list:
a) If the list is empty, add the new node and make the head have a reference to it.
b)If the list is not empty, iterate to the end of the list, and add the new element at the end.
3. insertAt(data, index): It adds a new node at a specific index given:
insertAt(data, index) {
//if index is out of range, return
if(index > 0 && index > this.size) {
return;
} //insert in first index
if(index === 0){
this.head = new Node(data, this.head);
return;
} //make a new node
const node = new Node(data);
let current, previous; // set current to the head
current = this.head;
let count = 0; //iterate the list to find the position to add
while(count < index) {
previous = current; //Node before index
count++;
current = current.next; //Node after the index
}
//add the new element
node.next = current;
previous.next = node;
this.size++;
}
Consider the following points while adding a new node at a specific location:
a) If the list is empty, add it at the beginning of the list, and make the head have a reference to it.
b) If the given index is out of range, return from the function.
c) Else, iterate over the list to find the specific index to insert the node at.
4. getAt(index): It gets a value from a specific index:
getAt(index) {
let current = this.head;
let count = 0; while(current) {
if(count == index) {
console.log(`value at ${index}: ${current.data}`);
}
count++;
current = current.next;
}
}
5. removeAt(index): It removes a value from a specific index
removeAt(index) {//if the index is out of range, return
if(index > 0 && index > this.size) {
return;
}let current = this.head;
let previous;
let count = 0;//if the index is the first one
if(index == 0) {
this.head = current.next;
} else {
while(count < index){
count++;
previous = current;
current = current.next;
}
previous.next = current.next
}
this.size--;
}
While removing a node from a given index, consider the following points:
a) If the index is out of range of the list, we should simply return.
b) If the given index is the first element, just make the head have a reference to the next node.
c) Otherwise, iterate to find the specific index, and remove it by making the following change:
previous.next = current.next
6.clearList(): It removes all the nodes
clearList() {
this.head = null;
this.size = 0;
}The above method simply sets the head to point to null.
7.printListData(): It prints all the values in the linked list through iterating over the list:
printListData() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next
}
}Now that we got the functions for the LinkedList class, we can create an object of the class and invoke those functions:
const ll = new LinkedList();
ll.insertFirst(100);
ll.insertFirst(200);
ll.insertFirst(300);
ll.insertLast(400);
// ll.insertAt(500,2);
ll.clearList();
console.log(ll);
// ll.removeAt(0);
ll.printListData();
// ll.getAt(2);In conclusion, Linked lists are a data structure made of nodes. A node is simply a structure composed of some data and a pointer. A pointer is just a reference to another node. So now instead of an indexed collection of data (an array), we have a bunch of data where each item has a link to the next one. We refer to the first item of a linked list as the head.
You can also refer to the following resources:
https://www.geeksforgeeks.org/implementation-linkedlist-javascript/
https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/
