[TIL][データ構造]リンクリストJSの実装

Data Structureでは、Java Scriptを使用してリンクリストを実装しています.
リンクリストは、大きく分けて、単一リンクリストと二重リンクリストに分けられます.

単一リンクリストの場合:

図に示すように、リスト内のノードは、そのノードの値と次のノードのアドレスを含む.
含むしかし、前のノードに関する情報がないため、次のノードに移動するしかなく、通常の方法では前のノードに移動するのは難しい.したがって

Double Linked Listを実現する方法があります。

リスト内のノードには、そのノードの値、次のノードのアドレス、および
自分の以前のノードのアドレスもあります.これにより、自分の次のノードと前のノードに移動しやすくなり、単一のリンクリストを巡回するのに要する時間の複雑さよりも小さくなり、または各ノードに必要なアドレスが1つ増加するため、空間の複雑さが少し増加します.
通常Linked ListとはSingle Linked Listであり、将来的にはLinked Listも使用される
SingleLinked Listです

Head & Tail

リンクリストを構成するノードでは、headで最初のノードを示し、他のノードが最初の位置に再入るとheadの位置が継承されます.
Tailも最後のノードを指し、リストに新しいノードを追加すると、
通常、Tailにノードが追加されるため、Tailではリストの長さが変更されると変更が続行されます.

リンクリストの実装

新しいリスト自体とリストに入れるノードを生成するクラスと方法を実現した.完全なコードとコアと考えられる方法の説明を作成しました.

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 === null) {
      this.head = node;
      this.tail = node;
      this._size ++;
    }
    else if(this.head !== null) {
      this.tail.next = node;
      this.tail = node;
      this._size ++;
    }
  }

  remove(value) {
    let preNode = this.head;
    let loopCount = this._size;
    while(loopCount > 0) {
      if(this.head.value === value) {
        this.head = this.head.next;
        this._size -= 1;
        break;
      }
      else if(preNode.next.value === value) {
        preNode.next.next = null;
        preNode.next = preNode.next.next;
        this._size -= 1;
        break;
      }
      else {
        loopCount -= 1;
        preNode = preNode.next;
      }
    }
  }

  getNodeAt(index) {
    if((index + 1) > this._size) {
      return undefined;
    }
    let head = this.head;
    for(let i = 0; i < index; i ++) {
      head = head.next;
    }
      return head;
  }

  contains(value) {
    if(this.head.value === value) {
      return true;
    }
    let node = this.head.next;
    for(let i = 1; i < this._size; i ++) {
      if(node.value === value) {
        return true;
      }
      else {
        node = node.next;
      }
    }
    return false;
  }

  indexOf(value) {
    if(this.head.value === value) {
      return 0;
    }
    let node = this.head.next;
    let index = 1;
    for(let i = 1; i < this._size; i ++) {
      if(node.value === value) {
        return index;
      }
      else {
        node = node.next;
        index += 1;
      }
    }
    return -1;
  }

  size() {
    return this._size;
  }
}

指定した値を持つノードをリストの末尾に追加する方法

addToTail(value) {
    // 새 노드 생성
    let node = new Node(value);
    // 리스트가 비었을 경우 / 리스트에 기존 노드가 있을경우
    if(this.head === null) {
      this.head = node;
      this.tail = node;
      this._size ++;
    }
    else if(this.head !== null) {
      this.tail.next = node;
      this.tail = node;
      this._size ++;
    }
  }

ジェネレータを使用して、値(パラメータ)を含む新しいノードを作成します.
場合によっては、リストのhead、tail、size、または前のノードのnextプロパティなどを変更できます.

指定した値を持つノードをリストから削除する方法

remove(value) {
    let preNode = this.head;
    let loopCount = this._size;
    while(loopCount > 0) {
      if(this.head.value === value) {
        this.head = this.head.next;
        this._size -= 1;
        break;
      }
      else if(preNode.next.value === value) {
        preNode.next.next = null;
        preNode.next = preNode.next.next;
        this._size -= 1;
        break;
      }
      else {
        loopCount -= 1;
        preNode = preNode.next;
      }
    }
  }

クエリー・リストを最初からループして、その値を含むノードを検索して削除します.
ノードの前のノードのnextプロパティを削除することで、削除者との接続を次のノードに変更します.

指定された値を持つノードをクエリーし、Booleanを返す方法

 remove(value) {
    let preNode = this.head;
    let loopCount = this._size;
    while(loopCount > 0) {
      if(this.head.value === value) {
        this.head = this.head.next;
        this._size -= 1;
        break;
      }
      else if(preNode.next.value === value) {
        preNode.next.next = null;
        preNode.next = preNode.next.next;
        this._size -= 1;
        break;
      }
      else {
        loopCount -= 1;
        preNode = preNode.next;
      }
    }
  }

削除と同様に、循環クエリーで真と偽を返します.

リンクリストを実装...

リンクリストの全体的な概念はチェーン式で、ノードとノードを接続するnext属性です.
とても重要だと感じます.挿入、削除などの操作を行うたびに、そのノードと前のノード、後のノードとの接続を変更するだけで、その削除したターゲットノードはリストを終了し、削除したターゲットノードを参照できなくなるため、ゴミ処理されます.
Linked Listのコンセプトは今では悪くないと考えられています.それもこれからもっと勉强しておけばよかった!