[Algorithm] Doubly Linked list construction


// This is an input class. Do not edit.
class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

// Feel free to add new properties and methods to the class.
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  setHead(node) {
    // node is the only node
   if (!this.head) {
     this.head = node
     this.tail = node
   } else {
      this.insertBefore(this.head, node); 
   } 
  }

  setTail(node) {
    if (!this.head) {
      this.setHead(node)
    } else {
      this.insertAfter(this.tail, node)
    }
  }

  insertBefore(node, nodeToInsert) {
    // only one node
    if (nodeToInsert === this.head && nodeToInsert === this.tail) {
      return;
    } 

    this.remove(nodeToInsert);
    nodeToInsert.prev = node.prev;
    nodeToInsert.next = node;

    if (!node.prev) {
      this.head = nodeToInsert
    } else {
      node.prev.next = nodeToInsert
    }
    node.prev = nodeToInsert
  }

  insertAfter(node, nodeToInsert) {
     // only one node
    if (nodeToInsert === this.head && nodeToInsert === this.tail) {
      return;
    }    

   this.remove(nodeToInsert);

    nodeToInsert.prev = node;
    nodeToInsert.next = node.next;

    if (!node.next) {
      this.tail = nodeToInsert
    } else {
      node.next.prev = nodeToInsert
    }
    node.next = nodeToInsert
  }

  insertAtPosition(position, nodeToInsert) {
    // if position = 1
    if (this.position === 1) {
      this.setHead(nodeToInsert)
    } else {
      let current = this.head;
      let currentPosition = 1;
      while (current !== null && currentPosition !== position) {
        current = current.next;
        currentPosition++
      }

      if (current === null) {
        this.setTail(nodeToInsert)
      }
      if (currentPosition === position) {
        this.insertBefore(current, nodeToInsert)
      }
    }
  }

  removeNodesWithValue(value) {
    let current = this.head;
    while(current) {
      // set it earlier
      const nodeToRemove = current;
      current = current.next;
      if (nodeToRemove.value === value) {
        this.remove(nodeToRemove)
      } 
    }
  }

  remove(node) {
    // check head
    if (this.head === node) {
      this.head = this.head.next;
    } 
    if (this.tail === node) {
       // check tail
       this.tail = this.tail.prev;
    } 
    this.removeNodeBindings(node)
  }

  removeNodeBindings(node) {
    const prevNode = node.prev 
    const nextNode = node.next 
    if (prevNode) {
      prevNode.next = nextNode
    }
    if(nextNode) {
      nextNode.prev = prevNode
    }
    node.prev = null;
    node.next = null;
  }

  containsNodeWithValue(value) {
    let current = this.head;
    while(current !== null && current.value !== value) {
      current = current.next;
    }
    return current !== null;
  }
}

// Do not edit the lines below.
exports.Node = Node;
exports.DoublyLinkedList = DoublyLinkedList;

 

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/278814.html

(0)
上一篇 2022年8月4日 04:00
下一篇 2022年8月4日 04:00

相关推荐

发表回复

登录后才能评论