Created
May 8, 2021 12:24
Star
You must be signed in to star a gist
single linked list in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* linked list is a linear data structure similar to an array. However, unlike arrays, | |
* elements are not stored in a particular memory location or index. Rather each element is a separate | |
* object that contains a pointer or a link to the next object in that list. | |
* for ex: head--> [D, reference to next] [D, reference to next] [D, null] --> tail | |
* D belongs to data. | |
* The head is a reference to the first node in the linked list. | |
* The last node on the list points to null. If a list is empty, the head is a null reference | |
*/ | |
/** | |
* singly linked list | |
*/ | |
class Node { | |
constructor(data, next=null){ | |
this.data = data; | |
this.next = next; | |
} | |
} | |
class LinkedList { | |
constructor() { | |
this.head = null; | |
} | |
} | |
/** | |
* single linked list work | |
* 1. insert node at before the head. | |
* 2. insert node after tail. | |
* 3. insert node in the middle of list. | |
* | |
* we use prototype of object to add method in LinkedList class. | |
*/ | |
/** | |
* insert node at the beginning of the singly linked list | |
* @param data any | |
*/ | |
LinkedList.prototype.insertAtBeginning = function (data) { | |
let newNode = new Node(data); // create new node. | |
/** we assign current head to new node next, so our newNode point to next node */ | |
newNode.next = this.head; | |
/** | |
* we already know that head is always start of list so, | |
* assign head to newNode. | |
*/ | |
this.head = newNode; | |
return this.head; // return updated list | |
} | |
/** | |
* insert node at the end of the singly linked list | |
* @param data any | |
*/ | |
LinkedList.prototype.insertAtEnd = function (data) { | |
let newNode = new Node(data); // create new node. | |
// head is null means empty list. | |
if (this.head === null) { | |
this.head = newNode; | |
} else { | |
let tail = this.head // a full single linked list. | |
/** | |
* traverse to list until tail.next !== null. | |
* because end of single linked list allways point to null. | |
*/ | |
while(tail.next !== null) { | |
tail = tail.next // reassign tail to next node next pointer. | |
} | |
// we are here it's mean tail has end of list which point to null. | |
tail.next = newNode; | |
} | |
return this.head; | |
} | |
/** | |
* return node by index. | |
* @param index number | |
* */ | |
LinkedList.prototype.getAt = function (index) { | |
let currentIndex = 0; | |
let node = this.head; | |
// traverse to linked list. | |
while(node) { | |
if (currentIndex === index) { | |
return node; | |
} | |
// incurease index; | |
currentIndex++; | |
// again assign to node variable with next value of node (which point to next node). | |
node = node.next; | |
} | |
return null; | |
} | |
/** | |
* insert at passed index. | |
* @param data any | |
* @param index number | |
*/ | |
LinkedList.prototype.insertAt = function (data, index) { | |
// if list is empty. | |
if (this.head === null) { | |
this.head = new Node(data); | |
return this.head; | |
} | |
// if new node needs to be inserted at the front of the list (before the head) | |
if (index === 0) { | |
this.head = new Node(data, this.head) | |
} | |
/** | |
* 1. get previous node by using getAt function @param index | |
* 2. create new node. | |
* 3. assign recently created new node next to previous node next. | |
* 4. assign previous node next to new node. | |
*/ | |
let prevNode = this.getAt(index - 1); | |
let newNode = new Node(data); | |
newNode.next = prevNode.next; | |
prevNode.next = newNode; | |
return this.head; | |
} | |
/** | |
* Deleting operation on single linked list. | |
* There can be three cases for the delete operation. | |
* 1. Delete first node. | |
* 2. Delete node last node. | |
* 3. Delete node from random position of list (by given index) | |
*/ | |
/** | |
* Delete first node. | |
*/ | |
LinkedList.prototype.deleteFirstNode = function() { | |
if (!this.head) { | |
return; | |
} | |
// assign current head to a next of current head(so first one is remove); | |
this.head = this.head.next; | |
return this.head; | |
} | |
/** | |
* Delete last node. | |
* in previous variable we store, previous node of tail node. | |
* for ex: if we have linked list: in form [data, reference to next node]. | |
* [1, next] [2, next] [3, next] [4, next] | |
* we hold previous value in each loop to previous variable. | |
* and again and again assign next of tail to tail until we reach null | |
*/ | |
LinkedList.prototype.deleteLastNode = function() { | |
if (!this.head) { | |
return null; | |
} | |
if (this.head.next == null) { | |
this.head = null; | |
return; | |
} | |
let previous = this.head; | |
let tail = this.head.next; | |
while (tail.next !== null) { | |
previous = tail; | |
tail = tail.next; | |
} | |
previous.next = null; | |
return this.head; | |
} | |
/** | |
* Delete node from middle of list (by given index) | |
* we will first have to traverse the list to find the desired node to | |
* be deleted and at the same time maintain an extra pointer to point | |
* at the node before the desired node. | |
*/ | |
LinkedList.prototype.deleteAt = function(index) { | |
if (!this.head) { | |
return; | |
} | |
if (index === 0) { | |
this.head = null; | |
return; | |
} | |
let previous = this.getAt(index - 1); | |
if (!previous || !previous.next) { | |
return; | |
} | |
previous.next = previous.next.next; | |
return this.head; | |
} | |
/** | |
* Delete Linked List. | |
*/ | |
LinkedList.prototype.deleteList = function(){ | |
this.head = null; | |
} | |
// let list = new LinkedList(); | |
// console.log(list); | |
// console.log(list.insertAtBeginning(5)); | |
// console.log(list.insertAt({at: 'Middle'}, 1)); | |
// console.log(list.insertAtEnd({at: 'end'})); | |
// console.log(list.insertAtBeginning({at: 'beginning'})); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment