Skip to content

Instantly share code, notes, and snippets.

@blrobin2
Created July 12, 2017 16:58
Show Gist options
  • Select an option

  • Save blrobin2/9c9aba5233855263b8267b40f7647706 to your computer and use it in GitHub Desktop.

Select an option

Save blrobin2/9c9aba5233855263b8267b40f7647706 to your computer and use it in GitHub Desktop.
A naïve approach at a SinglyLinkedList object in JS
class SinglyLinkedList {
constructor(value = []) {
if (Array.isArray(value)) {
value.forEach(val => this.addAtEnd(val))
} else {
this.value = value
this.next = null
}
}
find(target) {
let res = this
while (res) {
if (res.value === target) return res
res = res.next
}
return res
}
findBefore(target) {
let res = this
while (res.next) {
if (res.next.value === target) return res
res = res.next
}
return res
}
addAtBeginning(new_value) {
const new_cell = new this.constructor(new_value)
new_cell.next = this.next
this.next = new_cell
return this
}
addAtEnd(new_value) {
const new_cell = new this.constructor(new_value)
let last = this
while (last.next) {
last = last.next
}
last.next = new_cell
return this
}
insert(new_value) {
const new_cell = new this.constructor(new_value)
new_cell.next = this.next
this.next = new_cell
return this
}
delete(elem) {
this.findBefore(elem.value).next = elem.next
return this
}
[Symbol.iterator]() {
let curr = this
return {
i: curr.value,
next() {
curr = curr.next
if (curr) {
return {
value: curr.value,
done: false
}
}
return {
value: undefined,
done: true
}
}
}
}
}
const list = new SinglyLinkedList([4,5,6,7,3,2,1]);
console.log(list.find(5).value) // 5
console.log(list.findBefore(5).value) // 4
console.log(list.addAtBeginning(8).next.value) // 8
console.log(list.addAtEnd(10).find(10).value) // 10
const elem = list.find(5)
console.log(elem.insert(12).next.value) // 12
console.log(list.delete(elem).find(4).next.value) // 12
for (let cell of list) {
console.log(cell) //8,4,12,6,7,3,2,1,10
}
@blrobin2
Copy link
Author

It should probably be noted that this implementation utilizes a sentinel, so the first value of the list is not set. Makes managing the list way easier

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment