Created
May 19, 2018 08:51
-
-
Save mikkqu/8d79f2e4e351c3d11fd1384b69e4dfd6 to your computer and use it in GitHub Desktop.
Doubly 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
class DListNode { | |
constructor(val, next = null, prev = null) { | |
this.val = val | |
this.next = next | |
this.prev = prev | |
} | |
} | |
/* | |
Interface: | |
insertAtHead(val) | |
insertAtTail(val) | |
removeAtHead(val) | |
removeAtTail(val) | |
insertAtIndex(index, val) | |
removeAtIndex(index) | |
insertAfterKey(key, val) | |
insertBeforeKey(key, val) | |
getIndexByValue(val) | |
getValueAtIndex(index) | |
getNodeAtIndex(index) | |
doForEach(fn) | |
stringify() | |
*/ | |
class DLinkedList { | |
constructor(head = null, tail = null) { | |
this.head = head | |
this.tail = tail | |
} | |
insertAtHead(val) { | |
if (!this.head) { | |
this.head = new DListNode(val, null, null) | |
this.tail = this.head | |
} else { | |
this.head = new DListNode(val, this.head, null) | |
this.head.next.prev = this.head | |
} | |
} | |
insertAtTail(val) { | |
if (!this.head) { | |
this.insertAtHead(val) | |
} else { | |
this.tail.next = new DListNode(val, null, this.tail) | |
this.tail = this.tail.next | |
} | |
} | |
removeAtHead() { | |
if (this.head && this.head.next) { | |
this.head = this.head.next | |
this.head.prev = null | |
} else { | |
this.head = null | |
this.tail = null | |
} | |
} | |
removeAtTail() { | |
if (this.tail && this.tail.prev) { | |
this.tail = this.tail.prev | |
this.tail.next = null | |
} else { | |
this.head = null | |
this.tail = null | |
} | |
} | |
insertAtIndex(index, val) { | |
if (index === 0) { | |
return this.insertAtHead(val) | |
} | |
let node = this.getNodeAtIndex(index - 1) | |
if (!node) { | |
return | |
} | |
if (node.next) { | |
let tmp = new DListNode(val, node.next, node) | |
node.next.prev = tmp | |
node.next = tmp | |
} else { | |
let tmp = new DListNode(val, null, node) | |
node.next = tmp | |
this.tail = tmp | |
} | |
} | |
removeAtIndex(index) { | |
let curr = this.getNodeAtIndex(index) | |
if (!curr) { | |
return | |
} | |
if (index === 0) { | |
return this.removeAtHead() | |
} | |
if (curr.next) { | |
curr.next.prev = curr.prev | |
curr.prev.next = curr.next | |
} else { | |
curr.prev.next = null | |
this.tail = curr.prev | |
} | |
} | |
insertAfterKey(key, value) { | |
let index = this.getIndexByValue(key) | |
if (index < 0) { | |
return | |
} | |
this.insertAtIndex(index + 1, value) | |
} | |
insertBeforeKey(key, value) { | |
let index = this.getIndexByValue(key) | |
if (index < 0) { | |
return | |
} | |
this.insertAtIndex(index, value) | |
} | |
getNodeAtIndex(index) { | |
let curr = this.head | |
while (curr && index--) { | |
curr = curr.next | |
} | |
return curr | |
} | |
getValueAtIndex(index) { | |
let curr = this.head | |
while (curr && index--) { | |
curr = curr.next | |
} | |
if (curr) { | |
return curr.data | |
} else { | |
return null | |
} | |
} | |
getIndexByValue(value) { | |
let curr = this.head | |
let index = 0 | |
while (curr) { | |
if (curr.val === value) { | |
return index | |
} | |
curr = curr.next | |
index++ | |
} | |
return -1 | |
} | |
doForEach(fn) { | |
let curr = this.head | |
while (curr) { | |
fn(curr) | |
curr = curr.next | |
} | |
} | |
stringify() { | |
let out = [] | |
let curr = this.head | |
while (curr) { | |
out.push(curr.val) | |
curr = curr.next | |
} | |
return out.join(' -> ') | |
} | |
} | |
let list = new DLinkedList() | |
list.insertAtTail(5) | |
list.insertAtTail(6) | |
list.insertAtHead(4) | |
list.removeAtIndex(0) | |
list.insertBeforeKey(5, 9) | |
let arr = list.stringify() | |
console.log(arr) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment