JavaScriptデータ構造



定義
リンクリストは、我々がノードを呼ぶ要素のコレクションを表す線形データ構造です.そして、各々のノードが次の1つまたは前のものに指し示すとき、リンクリストの最初のノードは頭です、そして、最後は尾です

リンクリストでは、各ノードは以下のプロパティを持たなければなりません.

  • Value :ノードの値

  • next :リンクされたリストの次のノードへのポインタ.
  • リンクリストの主なプロパティは以下の通りです.
  • size :リンクリストのノード数
  • ヘッド:最初のノード
  • tail :最後のノード
  • そして、リンクリストデータ構造の主な操作は以下の通りです.
  • Insertat :特定のインデックスにノードを挿入します.
  • RemoveAt :特定のインデックスのノードを削除します.
  • GetAt :特定のインデックスの要素を取得します.
  • クリア:リンクリストを空にする
  • 反転(この場合):リンクリスト内のノードの順序を反転させる

  • 実装
    class LinkedList {
        constructor() {
            this.nodes = [];
        }
    
        get size() {
            return this.nodes.length;
        }
    
        get head() {
            return this.size ? this.nodes[0] : null;
        }
        get tail() {
            return this.size ? this.nodes[this.size - 1] : null;
        }
        insertAt(index, value) {
            const previousNode = this.nodes[index - 1] || null;
            const nextNode = this.nodes[index] || null;
            const node = { value, next: nextNode };
            if (previousNode) previousNode.next = node;
            // console.log(previousNode);
            this.nodes.splice(index, 0, node);
        }
        insertFirst(value) {
            this.insertAt(0, value);
        }
        insertLast(value) {
            this.insertAt(this.size, value);
        }
        getAt(index) {
            return this.nodes[index];
        }
        removeAt(index) {
            const previousNode = this.nodes[index - 1];
            const nextNode = this.nodes[index + 1] || null;
            if (previousNode) previousNode.next = nextNode;
    
            return this.nodes.splice(index, 1);
        }
        removeFirst() {
            this.removeAt(0)
        }
        removeLast() {
            this.removeAt(this.size - 1)
        }
    
        clear() {
            this.nodes = [];
        }
        reverse() {
            this.nodes = this.nodes.reduce((acc, {value}) => [{value, next: acc[0]}], [])
        }
        *[Symbol.iterator]() {
            yield* this.nodes;
        }
    }
    
  • 各インスタンスの空の配列、ノードを初期化するコンストラクターでクラスを作成します.
  • 配列を使用して返すサイズゲッターを定義します.プロトタイプ.length配列の要素の要素数を返します.
  • 空の場合、ノード配列の最初のノードを返します.
  • ノードの最後の要素を返すテールゲッターを定義します.
  • arrayを使用するinsert ()メソッドを定義します.プロトタイプ.splice ()は、ノード配列に新しいオブジェクトを追加します.
  • InsertFirst ()メソッドを使用して、2つの便利なメソッド、InsertFirst ()およびInsertList ()を定義します.
  • 指定したインデックス内の要素を取得するget ()メソッドを定義します.
  • arrayを使用するremoveAtom ()メソッドを定義します.プロトタイプ.splice ()は、ノード配列のオブジェクトを削除するには、前の要素の次のキーを更新します.
  • clear ()メソッドを定義します.
  • array ()を使用してreverse ()メソッドを定義します.プロトタイプ.reduce ()およびノード配列の順序を逆にするには、各要素の次のキーを適切に更新します.
  • シンボルのジェネレータメソッドを定義します.反復子は、yield *構文を使用してノード配列のイテレータに委任します.
  • 
    const list = new LinkedList();
    
    list.insertFirst(1);
    list.insertFirst(2);
    list.insertFirst(3);
    list.insertLast(4);
    list.insertAt(3, 5);
    
    list.size;                      // 5
    list.head.value;                // 3
    list.head.next.value;           // 2
    list.tail.value;                // 4
    [...list.map(e => e.value)];    // [3, 2, 1, 5, 4]
    
    list.removeAt(1);               // 2
    list.getAt(1).value;            // 1
    list.head.next.value;           // 1
    [...list.map(e => e.value)];    // [3, 1, 5, 4]
    
    list.reverse();
    [...list.map(e => e.value)];    // [4, 5, 1, 3]
    
    list.clear();
    list.size;                      // 0