JavaScript Data Structures: Doubly Linked List: Set / Update a specific node

Intro

Last time, we learned how to get a specific node by its index from our Doubly Linked List.

Today, we'll learn how to set / update a specific node.


Starter Code

We start with code that has the push and the get method. To update a node, we first have to add data. To find a node, we can use our get method.

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;
  }

  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;
  }

  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;
    }
  }
}

Thoughts

First, we should think about the constraints and possibilities:

Because we can use our created get method, this is really simple.

  • find the desired node
  • if we can find the node: update its value and return the node
  • if we can't find the node: return null

Implementation (Short)

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;
  }

  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;
  }

  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) {
    // find the desired node
    const currentNode = this.get(index);

    // if we can find the node
    if (currentNode) {
      // update its value
      currentNode.value = value;
      // return the updated node
      return currentNode;
    } else {
      // if we can't find the node: return null
      return null;
    }
  }
}

Result

Let's have a look how to use the Doubly Linked List's set method and its results.

const newDLL = new DoublyLinkedList();
newDLL.push("A");

// should have one node
console.log(newDLL);
// DoublyLinkedList {
//   length: 1,
//   head: Node { value: 'A', prev: null, next: null },
//   tail: Node { value: 'A', prev: null, next: null }
// }

// index too low
console.log(newDLL.set(-1, "too low"));
// null

// should display the updated node
console.log(newDLL.set(0, "updated A"));
// Node { value: 'updated A', prev: null, next: null }

// index too high
console.log(newDLL.set(1, "too high"));
// null

// should have one node with the update value
console.log(newDLL);
// DoublyLinkedList {
//   length: 1,
//   head: Node { value: 'updated A', prev: null, next: null },
//   tail: Node { value: 'updated A', prev: null, next: null }
// }

Next Part

We will implement our next method for the Doubly Linked List: insert / add a new node at a specific index.

If you want to get notified, subscribe!