Table of contents
Linked List in JavaScript is a very important topic in Javascript frontend interview or machine coding rounds. Linked List is also one of the real world used data structures. So it is very important to learn how to code a LinkedList in JavaScript.
In this article I will explain each code block.
Create A LinkedList In JS
Lets first create a Node class. This is a separate indivitual node. Generaly node contains data and a next pointer which points to the next element. This is a individual node so the next will be null.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
LinkedList Class
After that create a LinkedList class. This is representing the LinkedList. So a linkedList contains a head. But at first the head is empty.
class LinkedList{
constructor(data) {
this.head = null;
}
}
Add First of the LinkedList
At first create a new Node by the Node class. Next point the newNode's next with the current head node. After that make the new node head of the linkedList.
class LinkedList{
constructor(data) {
this.head = null;
}
addFirst(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
}
Add Last of the LinkedList
At first create a new node. After that check if this linkedList is empty or node. Of this is empty it will be the same code as addFirst().
Otherwise you have to take a current with this.head. Next loop the current till the current's next is null.
Now make the current's next is new node. }
addLast(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
Size of The LinkedList
For calculating the size take count variable whose initial value is 0. Loop the nodes of the LinkedList and increase the count one by one.
size() {
let count = 0;
let current = this.head;
while (current.next) {
current = current.next;
count++;
}
return count;
}
Add At any Index of the LinkedList
At first check if the index is less than 0 or greater than size. If it is then it will be an invalid index.
If the index is 0 then the same addFirst code will be there.
Otherwise traverse the nodes till the previous node of the indexed node. Now the current node is the previous node of the index node. So now the newNode's next will be the current node's next which is the index node. And make the current nodes next the newNode.
addAt(index, data) {
if (index < 0 || index > this.size()) {
console.log("invalid index");
}
const newNode = new Node(data);
if (index === 0) {
newNode.next = this.head;
this.head = newNode;
return;
}
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
Remove Top Node in LinkedList
Just make the LinkedList head to heads next node.
removeTop() {
if (!this.head) {
console.log("LinkedList is empty");
}
this.head = this.head.next;
}
Remove Last Node of the LinkedList
Traverse Till the previous node of the last node of the LinkedList. Now the current node is the previous node of the last node of the linkedList. Its next pointing to the last node. If you want to delete the last node simply point it to null.
removeLast() {
if (!this.head) {
console.log("LinkedList is empty");
}
let current = this.head;
while (current.next.next) {
current = current.next;
}
current.next = null;
}
Remove Node of Index
Traverse to the previous node of the index. Now point the nodes next to the next nodes next node.
removeAt(index) {
if (index < 0 || index > this.size()) {
console.log("invalid index");
}
if (index === 0) {
this.head = this.head.next;
}
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
}
Print LinkedList
Traverse the nodes and print the data of the LinkedList.
print() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
The Full LinkedList Code In JavaScript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
addFirst(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
}
addLast(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
size() {
let count = 0;
let current = this.head;
while (current.next) {
current = current.next;
count++;
}
return count;
}
addAt(index, data) {
if (index < 0 || index > this.size()) {
console.log("invalid index");
}
const newNode = new Node(data);
if (index === 0) {
newNode.next = this.head;
this.head = newNode;
return;
}
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
removeTop() {
if (!this.head) {
console.log("LinkedList is empty");
}
this.head = this.head.next;
}
removeLast() {
if (!this.head) {
console.log("LinkedList is empty");
}
let current = this.head;
while (current.next.next) {
current = current.next;
}
current.next = null;
}
removeAt(index) {
if (index < 0 || index > this.size()) {
console.log("invalid index");
}
if (index === 0) {
this.head = this.head.next;
}
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
}
print() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
}
const linkedList = new LinkedList();
linkedList.addFirst(5);
linkedList.addFirst(6);
linkedList.addFirst(12);
linkedList.addLast(7);
linkedList.print();
linkedList.removeTop();
linkedList.print();