Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class DoublyLinkedListNode {
constructor(value) {
this.value = value;
this.head = null;
this.tail = null;
}
valueOf() {
return this.value;
}
}
class DoublyLinkedList {
constructor(values = []) {
this.head = null;
this.tail = null;
this.length = 0;
for (const value of values) {
this.push(value);
}
}
unshift(value) {
const node = new DoublyLinkedListNode(value);
if (!this.head) {
this.head = node;
this.tail = node;
return;
}
const currentHead = this.head;
currentHead.head = node;
node.tail = currentHead;
this.head = node;
this.length++;
}
shift() {
const currentHead = this.head;
const value = currentHead ? currentHead.value : null;
const newHead = currentHead.tail;
newHead.head = null;
this.head = newHead;
this.length--;
return value;
}
push(value) {
const node = new DoublyLinkedListNode(value);
if (!this.tail) {
this.head = node;
this.tail = node;
this.length++;
return;
}
const currentTail = this.tail;
currentTail.tail = node;
node.head = currentTail;
this.tail = node;
this.length++;
}
pop() {
if (!this.tail) {
return null;
}
const currentTail = this.tail;
const value = currentTail.value;
const previousNode = currentTail.head;
previousNode.tail = null;
this.tail = previousNode;
this.length--;
return value;
}
*[Symbol.iterator]() {
let currentNode = this.head;
if (!currentNode) {
return;
}
while (currentNode) {
yield currentNode.value;
currentNode = currentNode.tail;
}
}
}
const list = new DoublyLinkedList();
list.push(1);
list.push(2);
list.push(3);
list.pop();
for (let v of list) {
console.log(v);
}
console.log(list);
@sebinsua
Copy link
Author

sebinsua commented Aug 11, 2022

Can we efficiently access nodes from the middle of the list? Can we efficiently insert, delete or update nodes in the middle of the list?

class DoublyLinkedListNode {
  constructor(value) {
    this.value = value;
    this.head = null;
    this.tail = null;
  }

  valueOf() {
    return this.value;
  }

  get left() {
    return this.head;
  }

  get right() {
    return this.tail;
  }
}

class DoublyLinkedList {
  constructor(values = []) {
    this.head = null;
    this.tail = null;
    this.length = 0;

    for (const value of values) {
      this.push(value);
    }
  }

  get size() {
    return this.length;
  }

  get isEmpty() {
    return this.length === 0;
  }

  toString() {
    const values = Array.from(this);
    return `${this.constructor.name}: ${values.join(" <-> ")}`;
  }

  unshift(value) {
    const node = new DoublyLinkedListNode(value);

    if (!this.head) {
      this.head = node;
      this.tail = node;
      return;
    }

    const currentHead = this.head;
    currentHead.head = node;
    node.tail = currentHead;
    this.head = node;

    this.length++;
  }

  shift() {
    const currentHead = this.head;
    const value = currentHead ? currentHead.value : null;

    const newHead = currentHead.tail;
    newHead.head = null;
    this.head = newHead;

    this.length--;

    return value;
  }

  push(value) {
    const node = new DoublyLinkedListNode(value);

    if (!this.tail) {
      this.head = node;
      this.tail = node;

      this.length++;

      return;
    }

    const currentTail = this.tail;
    currentTail.tail = node;
    node.head = currentTail;
    this.tail = node;

    this.length++;
  }

  pop() {
    if (!this.tail) {
      return null;
    }

    const currentTail = this.tail;
    const value = currentTail.value;

    const previousNode = currentTail.head;
    previousNode.tail = null;
    this.tail = previousNode;

    this.length--;

    return value;
  }

  findNode(fn) {
    if (typeof fn !== "function") {
      throw new Error(
        "`DoublyLinkedList#findNode` expects a function as its predicate"
      );
    }

    let currentNode = this.head;
    while (currentNode) {
      if (fn(currentNode) ?? false) {
        return currentNode;
      }

      currentNode = currentNode.tail;
    }

    return undefined;
  }

  find(fn) {
    if (typeof fn !== "function") {
      throw new Error(
        "`DoublyLinkedList#find` expects a function as its predicate"
      );
    }

    const matchedNode = this.findNode((node) => fn(node.value));
    if (!matchedNode) {
      return;
    }

    return matchedNode.value;
  }

  has(value) {
    const matchedNode = this.findNode((node) => node.value === value);
    if (!matchedNode) {
      return false;
    }

    return true;
  }

  delete(node) {
    if (!(node instanceof DoublyLinkedListNode)) {
      return;
    }

    const left = node.left;
    const right = node.right;

    if (left) {
      left.tail = right;
    } else {
      this.head = right;
    }

    if (right) {
      right.head = left;
    } else {
      this.tail = left;
    }

    this.length--;
  }

  set(node, value) {
    if (!(node instanceof DoublyLinkedListNode)) {
      return;
    }

    const left = node.left;
    const right = node.right;

    const newNode = new DoublyLinkedListNode(value);
    newNode.head = left;
    newNode.tail = right;

    if (left) {
      left.tail = newNode;
    }
    if (right) {
      right.head = newNode;
    }
  }

  insertBefore(beforeNode, insertValue) {
    if (!(beforeNode instanceof DoublyLinkedListNode)) {
      return;
    }

    const left = beforeNode.left;

    const newNode = new DoublyLinkedListNode(insertValue);
    if (left) {
      newNode.head = left;
      newNode.tail = beforeNode;
      beforeNode.head = newNode;
      left.tail = newNode;
    } else {
      newNode.tail = beforeNode;
      beforeNode.head = newNode;
      this.head = newNode;
    }
  }

  insertAfter(afterNode, insertValue) {
    if (!(afterNode instanceof DoublyLinkedListNode)) {
      return;
    }

    const right = afterNode.right;

    const newNode = new DoublyLinkedListNode(insertValue);
    if (right) {
      newNode.tail = right;
      newNode.head = afterNode;
      afterNode.tail = newNode;
      right.head = newNode;
    } else {
      newNode.head = afterNode;
      afterNode.tail = newNode;
      this.tail = newNode;
    }
  }

  clear() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  *[Symbol.iterator]() {
    yield* this.values();
  }

  *keys() {
    let currentNode = this.head;
    if (!currentNode) {
      return;
    }

    while (currentNode) {
      yield currentNode;
      currentNode = currentNode.tail;
    }
  }

  *values() {
    let currentNode = this.head;
    if (!currentNode) {
      return;
    }

    while (currentNode) {
      yield currentNode.value;
      currentNode = currentNode.tail;
    }
  }

  *entries() {
    let currentNode = this.head;
    if (!currentNode) {
      return;
    }

    while (currentNode) {
      yield [currentNode, currentNode.value];
      currentNode = currentNode.tail;
    }
  }
}

const list = new DoublyLinkedList();
list.push(1);
list.push(2);
list.push(3);
list.pop();

console.log("printing list");
console.log(list.toString());

list.push(19);
list.push(234);
list.push(73);
list.push(89);
list.push(672);
list.push(53);
list.push(112);
list.push(1);
list.push(3409);
list.push(3410);

console.log("printing list");
console.log(list.toString());

const atNode = list.findNode((node) => node.value === 112);
console.log("deleting", atNode);
list.delete(atNode);

console.log("printing list");
console.log(list.toString());

const firstNode = list.findNode((node) => node.value === 1);
console.log("deleting", firstNode);
list.delete(firstNode);

console.log("printing list");
console.log(list.toString());

const updateNode = list.findNode((node) => node.value === 1);
console.log("updating", updateNode);
list.set(updateNode, 9999);

console.log("printing list");
console.log(list.toString());

const insertAtNode = list.findNode((node) => node.value === 9999);
console.log("insert before", insertAtNode);
list.insertBefore(insertAtNode, 5000);
console.log("insert after", insertAtNode);
list.insertAfter(insertAtNode, 5001);

console.log("printing list");
console.log(list.toString());

See: https://codesandbox.io/s/admiring-chandrasekhar-xggjxi?file=%2Fsrc%2Findex.js%3A0-6223

@sebinsua
Copy link
Author

sebinsua commented Aug 11, 2022

Can this be made faster at seeking/peeking at a node when given a key/value by adding a Map to this? What about duplicates? Do we key by value or create an additional key?

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