Skip to content

Instantly share code, notes, and snippets.

@mohitsharma93
Created May 8, 2021 12:24
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mohitsharma93/3bb37a55f24a2aa14e13d1e9231c0d44 to your computer and use it in GitHub Desktop.
single linked list in JavaScript
/**
* 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