Linked List

13381 ワード
接続リスト datastructure データ構造 linkedlist テキストリンク
Data Structureを学習する際に知っている内容を整理します.各データ構造の実装にはJavaScriptが使用されます.

Linked List


接続リストは、ノードの接続からなる動的なデータ構造です.

リンクリストのインポート、追加、削除


任意の場所でデータを追加および削除する場合、接続リストはO(1)の時間的複雑さを有する.これは,操作を追加および削除するO(n)時間の複雑さとは異なる.
ただし、接続リストの各ノードにはインデックスがありません.したがって,特定のデータを検索する際には,リスト全体を最初から巡回しなければならず,O(n)の時間的複雑さをもたらす.
その他の削除O(n)O(1)O(1)のインポート

リンクリストのタイプ


単一接続リストと二重接続リスト.
  • 単一接続リストには、各ノードが次のノードを参照するリンク(一方向)が含まれます.
    • 「
  • デュアル接続」リストの各ノードには、前のノードと次のノードへのリンク(双方向)があります.

    • リンクリストの実装💻


    このインプリメンテーションでは、接続リストが実装されます.

    実装方法

  • addToTail(value)-接続リストの最後に指定した値を追加します.
  • remove(value)-指定された値を検索し、
    • を切断(削除)します.
  • getNodeAt(index)-指定したインデックスのノードを検索して返します.値ではなくノードを返さなければならないことに注意してください.インデックスにノードがない場合はundefinedを返します.
  • contains(value)-接続リストに指定した値を持つノードが存在するかどうかを返します.
  • indexOf(value)-指定した値のインデックスを返します.ない場合は-1を返します.

    • Pesuedo Code


  • addToTail(value) - this.headが存在するなら、this.tail.nextでvalueを値とするノードを接続します.this.headが存在しない場合は、headとtailにノードを同時に追加します.

  • remove(value)-接続リストから削除すると、接続が切断されます.headから値の調査を開始し、nextの調査を継続します.一致値が見つかった場合は、前のノードのnextを一致ノードの次のノードに接続します.検索するノードがheadの場合は、次のノードをheadに変更し、検索するノードが最後のノードの場合は、前のノードをtailに変更します.

  • getNodeAt(index)-countを宣言します.同様にheadからcountを調査して増加し、indexに等しい値であればノードを返します.

  • contains(value)-headをnextにチェックし、ノードの値が伝達パラメータと一致する場合はtrueを返し、一致しない場合はfalseを返します.

  • indexOf(value)-indexを宣言し、index+1に一致するまでheadから調査を開始します.一致する場合はインデックスを返しtailをチェックし、一致しない場合は-1を返します.
    • class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  addToTail(value) {
    let node = new Node(value);
    if(this.head){
      this.tail.next = node;
      this.tail = node;
      this._size++;
    } else{
      this.head = node;
      this.tail = node;
      this._size++;
    }

    return node;
   
  }

  remove(value) {
    let curNode = this.head; 
    let prevNode;

    while(curNode){
      if(curNode.value === value){
        if(!prevNode) this.head = curNode.next;
        else if(curNode === this.tail){
          prevNode.next = null;
          this.tail = prevNode;
        } else {
          prevNode.next = curNode.next;
        }
        this._size--;
      }
      prevNode = curNode;
      curNode = curNode.next;
    }
  }

  getNodeAt(index) {
    let count = 0;
    let currentnode = this.head;

    while(currentnode) {
      if(count === index) {
        return currentnode;
      }
      currentnode = currentnode.next;
      count++;
    }
    return undefined;
    
  }

  contains(value) {
    let curNode = this.head;
    while(curNode){
      if(curNode.value === value) return true;
      curNode = curNode.next
    }
    return false;
  }

  indexOf(value) {
    let index = 0;
    let curNode = this.head;

    while(curNode){
      if(curNode.value === value) return index;
      curNode = curNode.next;
      index++;
    }

    return -1;
  }

  size() {
    return this._size;
  }
}
    ノードJSアプリケーションを実行するにはDockerを使用する方法
    linuxはgolang/git/nodeをインストールします.js/postgresql