DoublyLinkedList.md

Prompt

Create a Doubly Linked List (each node has reference to both the previous and next nodes) with the following methods:

• addToHead(value): this should add a node to the beginning of our list
• addToTail(value): this should add a node to the end of our list
• remove(value): this should remove the first node where the value is equal to our given value (from head to tail)
• contains(value): this should return true if our list has a given value, false if not

---

---

---

---

Examples

Try and come up with your own! What does each method need exactly to make sure we don't mess up our linked list?

---

---

---

Hint

Don't forget that in a doubly linked list we need to change our reference for both previous and next nodes if we ever tamper with our list!

---

Framework (also a hint)

Here is a mach framework if you're having trouble getting started:

class LinkedList {
  constructor(head, tail) {
    this.head = head || null;
    this.tail = tail || null;
  }

  addToHead(value) {
    // insert code here
  }

  addToTail(value) {
    // insert code here
  }

  remove(value) {
    // insert code here
  }

  contains(value) {
    // insert code here
  }
}

class ListNode {
  constructor(value, next, prev) {
    this.value = value;
    this.next = next || null;
    this.prev = prev || null;
  }
}

---

Possible Solution

Here's one way to implement a doubly linked list:

class LinkedList {
  constructor(head, tail) {
    this.head = head || null;
    this.tail = tail || null;
  }

  addToHead(value) {
    let newNode = new ListNode(value);
    let oldHead = this.head;
    if (!oldHead) { // first node being added
      this.head = newNode;
      this.tail = newNode;
    }
    else {
      newNode.next = oldHead;
      oldHead.prev = newNode;
      this.head = newNode;
    }
    return this; // for chaining purposes
  }

  addToTail(value) {
    let newNode = new ListNode(value);
    let oldTail = this.tail;
    if (!oldTail) {
      this.head = newNode;
      this.tail = newNode;
    }
    else {
      newNode.prev = oldTail;
      oldTail.next = newNode;
      this.tail = newNode;
    }
    return this;
  }

  remove(value) {
    let pointer = this.head;
    while (pointer) {
      if (pointer.value === value) {
        let prevNode = pointer.prev;
        let nextNode = pointer.next;
        
        if (!prevNode) {
          this.removeFromHead();
        }
        else if (!nextNode) {
          this.removeFromTail();
        }
        
        if (prevNode) {
          prevNode.next = nextNode;
        }
        if (nextNode) {
          nextNode.prev = prevNode;
        }

        pointer = null;
        return this;
      }
      else {
        pointer = pointer.next;
      }
    }
    return this;
  }

  removeFromTail() {
    let oldTail = this.tail;
    if(!oldTail) return; // List is already empty
    if (!oldTail.prev) { // List only has one node left
      this.head = this.tail = null;
    }
    else {
      this.tail = oldTail.prev;
      this.tail.next = null;
    }
  }

  removeFromHead() {
    let oldHead = this.head;
    if(!oldHead) return; // List is already empty
    if (!oldHead.next) {
      this.head = this.tail = null;
    }
    else {
      this.head = oldHead.next;
      this.head.prev = null;
    }
  }

  contains(value) {
    let pointer = this.head;
    while (pointer) {
      if (pointer.value === value) return true;
      else {
        pointer = pointer.next;
      }
    }
    return false;
  }

  logAllNodes() {
    let pointer = this.head;
    while (pointer) {
      console.log(pointer);
      console.log("\n");
      pointer = pointer.next
    }
  }
}

class ListNode {
  constructor(value, next, prev) {
    this.value = value;
    this.next = next || null;
    this.prev = prev || null;
  }
}

Do note that the prompt only asks for 4 Linked List methods: addToHead, addToTail, remove, and contains. The two removeFromTail and removeFromHead methods are made for clarity and as "helper functions" for remove. These functions will also work perfectly fine on their own, and it's good practice to implement them in your future Linked Lists! One more note, logAllNodes() is a method to check to see how the current list looks, and is useful when viewing the code in a repl. Check out how each method works in https://repl.it/@cchoi34/DoublyLinkedList

Sometimes its easy to forget that when removing nodes, we have to check a few things:

Are we removing the last node?

• If so, we have to make sure our Linked List head and tail pointers are also set to null.

Are we removing a tail or a head node?

• If so, we have to make sure to reassign the respective head or tail pointer.

Are we removing a middle node?

• If so, we have to make sure to reassign BOTH the previous pointer of our next node, and the next pointer of our previous node. Wow confusing!