[TIL] linked list

25134 ワード
JavaScript データ構造 テキストリンク

linked list



各ノードには、データと次のノードへのリンクとデータがあります.

配列とチェーンテーブルの違い


Array

  • 固定サイズ
  • 入力と削除が無効
  • ランダムアクセス可能(ex:array[4]このように)
  • メモリの浪費がひどい
  • シーケンスアクセスが早い
  • 理由:各要素のメモリ位置は順に

    • Linked list

  • 大小ダイナミック
  • 効率的な入力と削除
  • データ構造全体を再構築することなく、リンクリストから簡単にノードを削除または追加できる.
  • 無作為アクセス
  • メモリロスなし
  • 順次アクセスが遅い
  • 原因:各要素のメモリ位置が一致しない
  • デメリット
  • 接続されたリストでの検索操作が遅い.配列とは異なり、データ要素へのランダムアクセスは許可されません.ノードは、最初のノードから順にアクセスします.
  • ポインタが格納されているため、アレイよりも多くのメモリが使用されます.

    • チェーンテーブルのタイプ

  • singly linked lists
  • 各ノードには次のノードへのポインタが1つしかない.
  • doubly linked lists
  • 各ノードには2つのポインタがあり、ポインタは次のノードと前のノードを指す.
  • ループリンクリスト(ループリンクリスト)
  • チェーンテーブルの変形.最後のノードは、最初のノードまたは以前の他のノードを指し、loopを作成します.

    • JSで実現


    list node

    class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
    前に示したように、1つのノードには、次のノードへのポインタとデータがあります.

    linked list


    headが通過しない場合、headはnullに初期化されます.
    class LinkedList {
  constructor(head = null) {
    this.head = head;
    this.size = 0;
  }
}

    せつぞく

    let node1 = new ListNode(2);
let node2 = new ListNode(5);
node1.next = node2; // node1의 포인터가 node2를 가리킴
    そして次のようにLinkedListに接続します.
    let list = new LinkedList(node1);
    コンソールで確認します.以下のようにします.
    LinkedList {
    head: ListNode { data: 2, next: ListNode { data: 5, next: null } }
    }

    LinkedListでのメソッド


    上記のようにいちいち接続する必要はなく、付加的な機能を持つメソッドを作成すれば、簡単に作成して接続することができます.
    class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor(head = null) {
    this.head = head;
    this.size = 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.head = null;
  }

  add(data) {
    let node = new ListNode(data);
    let current;

    if (this.head == null) {
      this.head = node;
    } else {
      current = this.head;

      // 마지막 node로 이동
      while (current.next) {
        current = current.next;
      }

      // add node
      current.next = node;
    }
    this.size++;
  }

  getLast() {
    let lastNode = this.head;
    while (lastNode.next) {
      lastNode = lastNode.next;
    }
    return lastNode;
  }

  getfirst() {
    return this.head;
  }

  remove(element) {
    let currentNode = this.head;
    let prevNode;

    if (currentNode.data === element) {
      this.head = currentNode.next;
    } else {
      while (currentNode.data !== element) {
        prevNode = currentNode;
        currentNode = currentNode.next;
      }

      prevNode.next = currentNode.next;
    }
  }

  indexOf(element) {
    let currentNode = this.head;
    let index = -1;

    while (currentNode) {
      index++;
      if (currentNode.data === element) {
        return index;
      }

      currentNode = currentNode.next;
    }

    return -1;
  }

  elementAt(index) {
    let currentNode = this.head;
    let count = 0;
    while (count < index) {
      count++;
      currentNode = currentNode.next;
    }
    return currentNode.data;
  }

  addAt(index, element) {
    let node = new ListNode(element);

    let currentNode = this.head;
    let previousNode;
    let currentIndex = 0;

    if (index > this.size) {
      return false;
    }

    if (index === 0) {
      node.next = currentNode;
      this.head = node;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      node.next = currentNode;
      previousNode.next = node;
    }
    this.size++;
  }

  removeAt(index) {
    let currentNode = this.head;
    let previousNode;
    let currentIndex = 0;
    if (index < 0 || index >= this.size) {
      return null;
    }
    if (index === 0) {
      head = currentNode.next;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      // currentIndex === 삭제할 index 일 때:
      previousNode.next = currentNode.next;
    }
    this.size--;
    // 삭제한 데이터
    return currentNode.data;
  }
}

let list = new LinkedList();
list.add(7);
list.add(8);
list.add(13);
list.remove(8);
list.add(14);
list.add(18);
list.addAt(0, 1);
console.log(list);
console.log(list.removeAt(1));
console.log(list);
    備考リンク：プレエンコード合宿室
    注2:geeks ForGeeks
    JetPackのViewModel原理学習
    永遠に機能する-メソッドから関数へ