JavaScriptで双方向リンクリストの任意の位置に要素を挿入する方法

本記事では、JavaScriptで双方向リンクリスト(ダブリーリンクリスト)の指定した位置にデータを挿入するための insert(data, position) 関数の実装方法を詳しく解説します。

挿入処理の基本的な流れ

指定位置への挿入は、次の手順で行います。

• 新しいノードを作成する
• リストが空かどうかを確認する。空の場合は、そのノードを head と tail の両方に設定して処理を終了する
• 空でない場合は、currNode を使って目的の位置までリストを走査する。走査は currNode を currNode.next に置き換えながら進めます

リンク(ポインタ)の付け替え

目的の位置に到達したら、以下の順序でリンクを張り替えます。

• 新しいノードの next を、リスト上の次のノードに向ける
• 次のノードの prev を、新しいノードに向ける
• 新しいノードの prev を、前のノードに向ける
• 前のノードの next を、新しいノードに向ける

最後に、currNode から後続ノードへのリンクを切り離し、新しく作成したノードを指すように変更します。これにより、ノードが指定位置に正しく組み込まれます。処理のイメージは下図の通りです。

実装コード

それでは、実際のコードを見ていきましょう。

insert(data, position = this.length) {
    let node = new this.Node(data);
    this.length++;
    // リストが現在空の場合
    if (this.head === null) {
        this.head = node;
        this.tail = node;
        return this.head;
    }
    // 先頭への挿入
    if (position == 0) {
        node.prev = null;
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
        return this.head;
    }
    let iter = 1;
    let currNode = this.head;
    while (currNode.next != null && iter < position) {
        currNode = currNode.next;
        iter++;
    }
    // 新しいノードのnextを、リスト内の次のノードに向ける
    node.next = currNode.next;
    // 次のノードのprevを、新しいノードに向ける
    if (currNode.next != null) {
        currNode.next.prev = node;
    }
    // 新しいノードのprevを、前のノードに向ける
    node.prev = currNode;
    // 前のノードのnextを、新しいノードに向ける
    currNode.next = node;
    // 挿入位置が末尾だった場合はtailを更新する
    if (this.tail.next != null) {
        this.tail = this.tail.next;
    }
    return node;
}

ポイントは、引数 position のデフォルト値として this.length(リストの長さ)を指定している点です。これにより、position を省略して呼び出した場合は、自動的にリストの末尾へ挿入されるようになっています。

動作確認

以下のコードで実際の動作を確認できます。

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

実行結果

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

実行結果を見ると、すべての要素が意図した通りの順序で並んでいることがわかります。この例では、値「15」を位置2(3番目)に挿入しています。先頭・中間・末尾のどの位置でも、リンクの付け替えを正しく行うことで安全に挿入できるのが双方向リンクリストの強みです。