Created
July 12, 2017 16:58
-
-
Save blrobin2/9c9aba5233855263b8267b40f7647706 to your computer and use it in GitHub Desktop.
A naïve approach at a SinglyLinkedList object in JS
This file contains hidden or 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 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 | |
| } |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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