Skip to content

Instantly share code, notes, and snippets.

@sebinsua
Last active August 14, 2022 19:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sebinsua/b4504593fcf721fd40054e1fc261bc5d to your computer and use it in GitHub Desktop.
Save sebinsua/b4504593fcf721fd40054e1fc261bc5d to your computer and use it in GitHub Desktop.
class SinglyLinkedListNode {
constructor(value) {
this.value = value;
this.tail = null;
}
valueOf() {
return this.value;
}
}
class SinglyLinkedList {
constructor(values = []) {
this.head = null;
this.length = 0;
for (const value of values) {
this.push(value);
}
}
unshift(value) {
const node = new SinglyLinkedListNode(value);
const currentHead = this.head;
node.tail = currentHead;
this.head = node;
this.length++;
}
shift() {
const currentHead = this.head;
const value = currentHead ? currentHead.value : null;
this.head = currentHead.tail;
this.length--;
return value;
}
push(value) {
const node = new SinglyLinkedListNode(value);
if (!this.head) {
this.head = node;
this.length++;
return;
}
let currentNode = this.head;
while (currentNode.tail) {
currentNode = currentNode.tail;
}
currentNode.tail = node;
this.length++;
}
pop() {
if (!this.head) {
return null;
}
let currentNode = this.head;
while (currentNode.tail) {
if (currentNode.tail && !currentNode.tail.tail) {
const value = currentNode.tail.value;
currentNode.tail = null;
this.length--;
return value;
}
currentNode = currentNode.tail;
}
}
*[Symbol.iterator]() {
let currentNode = this.head;
if (!currentNode) {
return;
}
while (currentNode) {
yield currentNode.value;
currentNode = currentNode.tail;
}
}
}
const list = new SinglyLinkedList([-2, -1, 0]);
list.push(1);
list.push(2);
list.push(3);
list.pop();
list.push(3);
for (let v of list) {
console.log(v);
}
console.log(list);
@sebinsua
Copy link
Author

@sebinsua
Copy link
Author

sebinsua commented Aug 13, 2022

See reverse: https://codesandbox.io/s/distracted-banach-t7ds8z?file=%2Fsrc%2Findex.js%3A0-2149

Note: this actually consumes the list right now, which you might not want tbh.

function reverse(ll) {
  let currentNode = ll.tail;
  if (!currentNode) {
    return;
  }

  let previousNode = null;
  while (currentNode) {
    [currentNode.tail, previousNode, currentNode] = [
      previousNode,
      currentNode,
      currentNode.tail
    ];
  }

  const rll = new SinglyLinkedList();
  rll.tail = previousNode;

  return rll;
}

See also, my attempt to use less variables.

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