これまで、符号化テストを解く際に使用したことのない接続リスト.そのせいか、熟練していないし怖い.今日は接続リストを整理して、それを砕きましょう!!🔥

接続リストは、データ領域とリンク領域のノードが接続されてデータを格納するデータ構造である.Data 영역:保存値Link 영역:他のノードへの役割

特長

探索詩O(n)必要
データを検索するには、HEADノードから値が正しいかどうかを確認し、次のノードにジャンプするため、線形時間が必要です.

追加・削除時O(1)必要

ノードがメモリに分散している.

配列とは異なり、接続リストのノードはメモリに分散しており、ポインタで各領域を表示できます.

種類

Singly Linked List

各ノードには、データと次のノードへのポインタが含まれます.

Doubly Linked List

各ノードには、前のノードと次のノードを指すデータとポインタが含まれます.

Circular Linked List

[単純リンクリスト](Simple Links List)で、最後のノードを最初のノードに接続し、円形構造にします.

👀 コード別に表示

Singly Linked List

class Node { 
	constructor(value) {
		this.value = value; // 값
		this.next = null; // 포인터
	}
}

class SinglyLinkedList {
	constructor() {
		this.head = null; // head 포인터
		this.tail = null; // tail 포인터
	}

作成者の立場から見てみましょう.
ノードクラスには値とポインタしかありません.針は今何も指していない.
SingleyLindListクラスのコンストラクション関数はheadとtailポインタからなり,それら自体にノードがないと判断できる.

find(value) {
	let curNode = this.head; // 헤드 요소를 담음
  // curNode는 값을 찾을 때까지 다음 요소로 넘어감.
	while (curNode.value !== value) {
		curNode = curNode.next;
	}
	return curNode; // 값을 찾으면 해당 노드 반환.
}

// 끝 부분에 추가
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メソッドは、パラメータが受信した値を使用して新しいノードを作成します.
headがnullの場合、headとtailポインタはnewNodeを指し、接続リストが空であることを示します.
headに値がある場合、tailのnextポインタはnewNodeを指し、tailのポインタはnewNodeを指す.

// 노드 중간에 추가
insert(node, newValue) {
	const newNode = new Node(newValue);
	newNode.next = node.next;
	node.next = newNode;
}

パラメータとして受け取ったnodeは、newValueの新しいノードの関数を挿入します.
まずnewValueを新しいノードに入れ,新しいノードのnextポインタを入力ノードのnextに向ける.つまり、元のノードが指していたポインタから、自分を次の方に向けさせます.
入力ノードのnextが新しいノードを指すようにすると、nodeはnewNodeを指し、newNodeは元のノードの次を指し、誰もが喜ぶ

// 값을 탐색 후 삭제 = O(n)
remove(value) {
	let preNode = this.head;
	while (preNode.next.value !== value) {
		preNode = preNode.next;
	}

	if (preNode.next !== null) {
		preNode.next = preNode.next.next;
	}
}

prenode変数を作成して、削除するノードの前のノードを検索します.
前のノードが見つかった場合、前のノードの次のノードはnextです.nextを指すように変更します.この場合、中間ノードはどのノードにも接続されないため、ゴミ収集器によって自然に削除されます.

二重リンクリストの実施予定-

Circular Linked Listを実施する-

単一チェーンテーブルを実現するsizeメソッド

size() {
	let curNode = this.head;
	let count = 0;
	while(curNode !== null) {
		count++;
		curNode = curNode.next;
	}
	return count;
}

curnodeにheadを入れた後、curnodeがnullになる前にcountを増やします.countが増加したらcurnodeを次のノードに設定します!最終的にcountに戻ります.

例外の処理

-導入予定-

コメントサイト

データ構造接続リスト
二重接続リスト（Double Linked List）、二重円形接続リストの例