JavaScriptのデータ構造:2重連結リスト

イントロ
新しいノードを特定のインデックスに挿入する方法を学びました.
今日、特定のインデックスでノードを削除する方法を学びます.

始動コード
私たちは、push , shift , pop and get 方法
なぜなら、それらを再利用できるからです.

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

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

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

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

思考
まず、制約と可能性について考えるべきです.
インデックスが無効な場合(リストが空で、インデックスが0未満の場合、リストの長さ以上)

返り値

最初のノードを削除したい場合(インデックスは0となります):

使用するshift データの追加方法

最後のノードを削除する場合(インデックスは1からlengthに1 )になります:

使用するpop データの追加方法

残りの症例

削除したいノード、その前のノードとそれ以降のノードを保存します

ノードからの接続を削除して他のノードに削除する

ノードの前のノードからの接続を削除する

ノードの後のノードからの接続を削除する

長さを1減らす

戻りノード

例

// current list:
A <===> B <===> C
// desired list:
A <===> C

手順:

// current list:
A <===> B <===> C

// remove the connections from the node to remove to other nodes
A   ==> B <==   C

// update the connections from the node before the node to remove
A   ==> C // A.next to C instead of B
B <==   C // C.prev to B, still

// update the connections from the node after the node to remove
A <===> C // finally, C.prev to A instead of B

// desired list:
A <===> C

最後のステップの後のリスト

実装

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

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

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

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

  remove(index) {
    // if the index is invalid, return null
    if (!this.length || index < 0 || index >= this.length) {
      return null;
    } else if (index === 0) {
      // if we want to remove the first node
      return this.shift();
    } else if (index === this.length - 1) {
      // if we want to remove the last node
      return this.pop();
    } else {
      // store the node we want to remove, the node before it and the node after it
      const nodeToRemove = this.get(index);
      const prevNodeToRemove = nodeToRemove.prev;
      const nextNodeToRemove = nodeToRemove.next;

      // remove the connections from the node to remove to other nodes
      nodeToRemove.prev = null;
      nodeToRemove.next = null;

      // update the connections from the node before the node to remove
      prevNodeToRemove.next = nextNodeToRemove;

      // update the connections from the node after the node to remove
      nextNodeToRemove.prev = prevNodeToRemove;

      // decrease length by 1
      this.length -= 1;

      // return node
      return nodeToRemove;
    }
  }
}

結果
二重リンクリストの使い方を見てみましょうremove 方法とその結果

const newDLL = new DoublyLinkedList();
newDLL.push("new 0");
newDLL.push("new 1");
newDLL.push("new 2");

// should be a list with 3 nodes
console.log(newDLL);
// DoublyLinkedList {
//   length: 3,
//   head: <ref *1> Node {
//     value: 'new 0',
//     prev: null,
//     next: Node { value: 'new 1', prev: [Circular *1], next: [Node] }
//   },
//   tail: <ref *2> Node {
//     value: 'new 2',
//     prev: Node { value: 'new 1', prev: [Node], next: [Circular *2] },
//     next: null
//   }
// }

// index invalid
console.log(newDLL.remove(-1));
// null

// index invalid
console.log(newDLL.remove(5));
// null

// should be new 0
console.log(newDLL.remove(0));
// Node { value: 'new 0', prev: null, next: null }

// should be new 2 (we deleted new 0)
console.log(newDLL.remove(1));
// Node { value: 'new 2', prev: null, next: null }

// should be a list with 1 node (we deleted 2 nodes from the initial 3 node list)
console.log(newDLL);
// DoublyLinkedList {
//   length: 1,
//   head: Node { value: 'new 1', prev: null, next: null },
//   tail: Node { value: 'new 1', prev: null, next: null }
// }

次部分
我々は、二重リンクリストの小さな要約を行います.
通知したい場合はsubscribe !