miku86

Intro

Last time, we added the last method.

I hope you learned something about the concept of a Doubly Linked List and tried your best to implement it on your own.

Most of the time it deepens my knowledge if I go over it again. And again.

Thoughts about the Doubly Linked List

This time we implemented the Linked List first, so that we have the knowledge to think about the Big O.

The fundamental difference to the Singly Linked List is the fact, that every node has a connection to its previous node and its next node, not only its next node.

That means if we want to do something near the end of the list, we can start from the tail of the Doubly Linked List and go to the previous nodes, instead of always starting from the head like in your Singly Linked List. If we can go backwards from the tail, we can half our average time to find a node.

On the other hand, a Doubly Linked List needs more memory, because every node has the additional prev property for the pointer to the previous node.

• Access: O(N)
• Search: O(N)
• Insert: O(1)
• Remove: O(1)

Final Implementation (Short version)

Our Doubly Linked List has these methods:

• get, to get a specific node
• set, to update a specific node
• push, to add a node to the end
• pop, to remove a node from the end
• unshift, to add a node to the beginning
• shift, to remove a node from the beginning
• insert, to add a node at a specific index
• remove, to remove a node at a specific index

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  get(index) {
    if (!this.length || index < 0 || index >= this.length) {
      return null;
    } else {
      let currentNode;

      if (index < this.length / 2) {
        let counter = 0;
        currentNode = this.head;

        while (counter < index) {
          currentNode = currentNode.next;
          counter += 1;
        }
      } else {
        let counter = this.length - 1;

        currentNode = this.tail;

        while (counter > index) {
          currentNode = currentNode.prev;
          counter -= 1;
        }
      }

      return currentNode;
    }
  }

  set(index, value) {
    const currentNode = this.get(index);

    if (currentNode) {
      currentNode.value = value;
      return currentNode;
    } else {
      return null;
    }
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }

    this.length += 1;

    return newNode;
  }

  pop() {
    if (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.tail;

      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.tail = this.tail.prev;
        this.tail.next = null;
        nodeToRemove.prev = null;
      }

      this.length -= 1;

      return nodeToRemove;
    }
  }

  unshift(value) {
    const newNode = new Node(value);

    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.length += 1;

    return newNode;
  }

  shift() {
    if (!this.length) {
      return null;
    }

    const nodeToRemove = this.head;

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = nodeToRemove.next;
      this.head.prev = null;
      nodeToRemove.next = null;
    }

    this.length -= 1;

    return nodeToRemove;
  }

  insert(index, value) {
    if (index < 0 || index > this.length) {
      return null;
    } else if (index === 0) {
      return this.unshift(value);
    } else if (index === this.length) {
      return this.push(value);
    } else {
      const newNode = new Node(value);

      const newPrevNode = this.get(index - 1);
      const newNextNode = newPrevNode.next;

      newNode.prev = newPrevNode;
      newPrevNode.next = newNode;

      newNode.next = newNextNode;
      newNextNode.prev = newNode;

      this.length += 1;

      return newNode;
    }
  }

  remove(index) {
    if (!this.length || index < 0 || index >= this.length) {
      return null;
    } else if (index === 0) {
      return this.shift();
    } else if (index === this.length - 1) {
      return this.pop();
    } else {
      const nodeToRemove = this.get(index);
      const prevNodeToRemove = nodeToRemove.prev;
      const nextNodeToRemove = nodeToRemove.next;

      nodeToRemove.prev = null;
      nodeToRemove.next = null;

      prevNodeToRemove.next = nextNodeToRemove;
      nextNodeToRemove.prev = prevNodeToRemove;

      this.length -= 1;

      return nodeToRemove;
    }
  }
}