Skip to content

Instantly share code, notes, and snippets.

@jasterix
Created August 16, 2020 17:12
Show Gist options
  • Save jasterix/ad15c0745749bc1b15f3c641def50596 to your computer and use it in GitHub Desktop.
Save jasterix/ad15c0745749bc1b15f3c641def50596 to your computer and use it in GitHub Desktop.
Creating and working with Doubly Linked Lists
class Node{
constructor(val){
this.val = val;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
push(val){
var newNode = new Node(val);
if(this.length === 0){
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length++;
return this;
}
pop(){
if(!this.head) return undefined;
var poppedNode = this.tail;
if(this.length === 1){
this.head = null;
this.tail = null;
} else {
this.tail = poppedNode.prev;
this.tail.next = null;
poppedNode.prev = null;
}
this.length--;
return poppedNode;
}
shift(){
if(this.length === 0) return undefined;
var oldHead = this.head;
if(this.length === 1){
this.head = null;
this.tail = null;
}else{
this.head = oldHead.next;
this.head.prev = null;
oldHead.next = null;
}
this.length--;
return oldHead;
}
unshift(val){
var newNode = new Node(val);
if(this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.length++;
return this;
}
get(index){
if(index < 0 || index >= this.length) return null;
var count, current;
if(index <= this.length/2){
count = 0;
current = this.head;
while(count !== index){
current = current.next;
count++;
}
} else {
count = this.length - 1;
current = this.tail;
while(count !== index){
current = current.prev;
count--;
}
}
return current;
}
set(index, val){
var foundNode = this.get(index);
if(foundNode != null){
foundNode.val = val;
return true;
}
return false;
}
insert(index, val){
if(index < 0 || index > this.length) return false;
if(index === 0) return !!this.unshift(val);
if(index === this.length) return !!this.push(val);
var newNode = new Node(val);
var beforeNode = this.get(index-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode, newNode.prev = beforeNode;
newNode.next = afterNode, afterNode.prev = newNode;
this.length++;
return true;
}
}
var list = new DoublyLinkedList()
list.push("Harry")
list.push("Ron")
list.push("Hermione")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment