JavaScript単一接続リスト

JavaScriptを使用して接続リストを実装します.
頻繁にデータ(ノード)を追加および削除する場合は、配列を使用するよりも接続リストを使用するほうがよい.接続リストの特徴はheadとtailポインタであり,各ノードには次のノードへのポインタがある.

単一接続リスト

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

 クラスを使用してノードを作成し、コンストラクション関数のパラメータとしてvalueを受け入れます.このオプションを使用して、生成ノードの値を指定します.次のノードへのポインタがnullを生成します.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

 単一の接続クラスを作成します.生成時にheadとtailポインタをnullに初期化します.
次の関数は、単一の接続クラスの内部にある関数です.

find(targetvalue)

  
  // 특정 값을 사용해서 원하는 노드를 찾는다.
  // 탐색하고자 하는 노드가 마지막에 있을 경우 선형 시간 복잡도를 갖는다.
  find (targetValue) {
    let currNode = this.head;
    let findNode = null;
    
    while (currNode !== null) {
      if (currNode.value === targetValue) {
        findNode = currNode;
      }
      currNode = currNode.next;
    }
    return findNode;
  }
    
    

 findNodeは、接続リストに存在しない場合にnullを返すために値(targetValue)を追加しました.currNodeがnullでないまでwhile文を使用してナビゲートし、見つかった場合はノードを返し、見つからない場合はnullを返します.
値が重複している場合、最初に参照した値を返すという問題があります.

append(newValue)

append(newValue) {
 const newNode = new Node(newValue); 
  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
   	this.tail.next = newNode;
    this.tail = newNode;
  }
}

 append関数はnewValue値を使用して新しいノードを作成し、最後のノードに追加します.現在のheadポインタがnullでリストが空である場合、最初のノードとして追加されます.したがって、リストのheadとtailは新しいノードを指します.

insert(targetValue, newValue)

insert (targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert fail...");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    targetNode.next = newNode;
  }
}

 Insert関数は、ターゲット値リストのノードの後に新しいノードを作成し、追加します.まず、特定の値がリストにあるかどうかをナビゲートし、ない場合はinsert faillに通知し、関数が終了します.
ターゲットノードの値がリストに存在する場合は、新しいノードを作成し、ターゲット値の次のノードを新しいノードの次のノードで接続し、ターゲットノードの次のノードを新しいノードに接続します.

remove(targetValue)

remove(targetValue) {
  if (this.find(targetValue) === null) {
    console.log("remove fail...");
  } else {
    let currNode = this.head;
    if (currNode.value === targetValue) {
      this.head = currNode.next;
    } else {
      while (currNode.next.value !== targetValue) {
        currNode = currNode.next;
      }
      if(currNode.next !== null) {
        currNode.next = currNode.next.next;
      }
    }
  }
}

 remove関数もデフォルトでfind関数を使用してtargetValueを持つノードをナビゲートします.ノードが存在する場合は、最初のノードの削除と残りのノードの削除の2つに分けられます.CurrNodeは現在のノードを表し、最初のノードを削除する場合は、接続リストのヘッダポインタを簡単に次のノードに向けるだけでよい.
 最初のノードでない場合は、targetValueを持つノードの前のノードを見つける必要があります.削除するノードの次のノードを前のノードの次のノードとして作成する必要があるため、targetValueを持つノード以外のノードの前のノードを検索します.文を実行すると、現在のノードは削除するノードの前のノードになります.次に、現在のノードの次のノードを削除する次のノードに接続します.

size()

size() {
  let currNode = this.head;
  let sizeCount = 0;
  
  while (currNode !== null) {
   	sizeCount += 1;
    currNode = currNode.next;
  }
  console.log(sizeCount);
}

 size関数は、接続リストを巡回しながらsizeCount値を増やして計算します.
sizeを求めるたびに探求する...
したがって、ノードの追加または削除時にカウントするように変更する必要があります.

リビジョンとバージョン

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkdedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }

  find(targetValue) {
    let currNode = this.head;
    let findNode = null;
    while (currNode !== null) {
      if (currNode.value === targetValue) {
        findNode = currNode;
      }
      currNode = currNode.next;
    }
    // 값이 중복일 경우??? 일단 중복은 없다고 생각함...
    return findNode;
  }

  append(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.count += 1;
  }

  insert(targetValue, newValue) {
    const targetNode = this.find(targetValue);
    if (targetNode === null) {
      console.log("insert fail...");
    } else {
      const newNode = new Node(newValue);
      newNode.next = targetNode.next;
      targetNode.next = newNode;
      this.count += 1;
    }
  }

  remove(targetValue) {
    // 값을 기준으로 리스트를 순회.
    // 리스트의 마지막 노드일 경우 -> 선택 노드의 앞 노드의 next를 null로 변경
    // 리스트의 처음 노드일 경우 -> 헤드 포인터 변경
    // 리스트의 중간 노드일 경우 -> 선택 노드의 앞 노드의 next를 선택 노드의 next로 변경
    // 리스트에 없는 값을 삭제하려고 할 경우. -> find함수 사용 find 함수의 시간복잡도를 생각하면 그리 좋은 방법은 아님...

    if (this.find(targetValue) === null) {
      console.log("remove fail...");
    } else {
      let currNode = this.head;
      if (currNode.value === targetValue) {
        this.head = currNode.next;
        this.count -= 1;
      } else {
        while (currNode.next.value !== targetValue) {
          currNode = currNode.next;
        }
        if (currNode.next !== null) {
          currNode.next = currNode.next.next;
          this.count -= 1;
        }
      }
    }
  }

  display() {
    let currNode = this.head;
    let displyString = "[";
    while (currNode !== null) {
      let addString = `${currNode.value}`;
      if (currNode.next !== null) {
        addString += `, `;
      }
      displyString += addString;
      currNode = currNode.next;
    }
    displyString += "]";
    console.log(displyString);
  }

  size() {
    console.log(this.count);
  }
}

接続リストが多くなったら?
原型を使いましょう!

プロトタイプを使用した結果

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
}

SinglyLinkedList.prototype.find = function (targetValue) {
  let currNode = this.head;
  let findNode = null;
  while (currNode !== null) {
    if (currNode.value === targetValue) {
      findNode = currNode;
    }
    currNode = currNode.next;
  }
  // 값이 중복일 경우??? 일단 중복은 없다고 생각함...
  return findNode;
};

SinglyLinkedList.prototype.append = function (newValue) {
  const newNode = new Node(newValue);
  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.count += 1;
};

SinglyLinkedList.prototype.insert = function (targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert fail...");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    targetNode.next = newNode;
    this.count += 1;
  }
};

SinglyLinkedList.prototype.remove = function (targetValue) {
  // 값을 기준으로 리스트를 순회.
  // 리스트의 마지막 노드일 경우 -> 선택 노드의 앞 노드의 next를 null로 변경
  // 리스트의 처음 노드일 경우 -> 헤드 포인터 변경
  // 리스트의 중간 노드일 경우 -> 선택 노드의 앞 노드의 next를 선택 노드의 next로 변경
  // 리스트에 없는 값을 삭제하려고 할 경우. -> find함수 사용 find 함수의 시간복잡도를 생각하면 그리 좋은 방법은 아님...

  if (this.find(targetValue) === null) {
    console.log("remove fail...");
  } else {
    let currNode = this.head;
    if (currNode.value === targetValue) {
      this.head = currNode.next;
      this.count -= 1;
    } else {
      while (currNode.next.value !== targetValue) {
        currNode = currNode.next;
      }
      if (currNode.next !== null) {
        currNode.next = currNode.next.next;
        this.count -= 1;
      }
    }
  }
};

SinglyLinkedList.prototype.display = function () {
  let currNode = this.head;
  let displyString = "[";
  while (currNode !== null) {
    let addString = `${currNode.value}`;
    if (currNode.next !== null) {
      addString += `, `;
    }
    displyString += addString;
    currNode = currNode.next;
  }
  displyString += "]";
  console.log(displyString);
};

SinglyLinkedList.prototype.size = function () {
  console.log(this.count);
};

const linkedList = new SinglyLinkedList();
const linkedList2 = new SinglyLinkedList();
const linkedList3 = new SinglyLinkedList();
const linkedList4 = new SinglyLinkedList();

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);

linkedList2.append(1);
linkedList2.append(2);
linkedList2.append(3);
linkedList2.append(4);

linkedList3.append(1);
linkedList3.append(2);
linkedList3.append(3);
linkedList3.append(4);

linkedList4.append(1);
linkedList4.append(2);
linkedList4.append(3);
linkedList4.append(4);

console.log(linkedList, linkedList2, linkedList3, linkedList4);
linkedList.display();
linkedList2.display();
linkedList3.display();
linkedList4.display();

新しく作成した汎用関数ではなく、インスタンスを作成するたびにプロトタイプの関数を使用することで、メモリの使用量を削減できます.