JavaScriptで双方向連結リストの要素を削除する方法

双方向連結リストから要素を削除する仕組み

連結リストからの要素削除は非常にシンプルです。やるべきことは「削除したいノードへの参照を失わせる」こと、つまり対象ノードをリンクのチェーンから切り離すだけです。ただし、削除する位置によって処理が異なるため、次の3つのケースを考慮する必要があります。

• 先頭（head）の要素を削除する： head = head.next と代入するだけで、先頭ノードへの参照は失われ、headは2番目の要素を指すようになります。このとき、新しいheadのprevをnullに設定し、前方向のリンクも忘れずに切っておきます。
• 末尾（tail）の要素を削除する： 後ろから2番目のノードのnextをnullにすれば、最後の要素はリストから取り除かれます。あわせてtailポインタも更新し、新しい末尾ノードを指すようにします。
• 中間の要素を削除する： このケースが最も注意が必要です。削除対象ノードの「1つ前のノード」が「1つ後ろのノード」を直接参照するようにします。具体的には prevNode.next = node.next と node.next.prev = prevNode の2つの操作で実現できます。

以下の図は、中間ノードを削除する際のリンクの付け替えを示したものです。

removeメソッドの実装例

実際のコードでは、削除位置（position）を引数として受け取り、0以下なら先頭、リスト長以上なら末尾、それ以外なら中間として処理を分岐させます。

remove(data, position = 0) {
    if (this.length === 0) {
        console.log("List is already empty");
        return;
    }
    this.length--;
    let currNode = this.head;
    if (position <= 0) {
        // 先頭の要素を削除
        this.head = this.head.next;
        this.head.prev = null;
    }
    else if (position >= this.length - 1) {
        // 末尾の要素を削除
        this.tail = this.tail.prev;
        this.tail.next = null;
    }
    else {
        // 中間の要素を削除
        let iter = 0;
        while (iter < position) {
            currNode = currNode.next;
            iter++;
        }
        currNode.next = currNode.next.next;
        currNode.next.prev = currNode;
    }
    return currNode;
}

動作確認

次のようなコードで動作をテストできます。

let list = new LinkedList();
list.insert(10);
list.insert(20);
list.insert(30);
list.remove(1);
list.display();
list.insert(15, 2);
list.remove();
list.display();

出力結果

上記のコードを実行すると、以下のような出力が得られます。

20 <->
30 <->
30 <->
15 <->