이 글은 JavaScript의 링크드 리스트에 대한 자세한 소개를 담고 있습니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.
링크된 목록과 배열
JS에서는 누구나 배열을 사용해 왔습니다. 배열은 실제로 선형 테이블의 순차적 저장 구조입니다. 그 특징은 연속된 주소를 가진 저장 단위 집합을 사용하여 데이터 요소를 순차적으로 저장하는 것입니다. 단점은 배열을 삭제하거나 삽입할 때 많은 수의 요소를 이동해야 하는 등의 특성 때문이기도 합니다.
다음은 배열 삽입 작업의 대략적인 시뮬레이션입니다.
insert(arr, index, data){
for(let i = index + 1; i <p> 위 코드에서 배열의 삽입 및 삭제가 O(n) 작업일 수 있음을 알 수 있습니다. 이는 연결리스트의 데이터 구조로 이어집니다. 연결리스트는 논리적으로 인접한 요소가 물리적 위치에서 인접할 필요가 없으므로 순차 저장 구조의 단점도 없습니다. 연속적인 공간에 배열되는 장점. </p><h3>단방향 연결 목록</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="JavaScript의 연결 목록에 대한 자세한 소개"></span></p><h4> 단방향 연결 목록의 특징: </h4>임의의 메모리 공간 집합을 사용하여 데이터 요소를 저장합니다(여기서 메모리 공간은 연속적이거나 불연속적일 수 있음)
각 노드(노드)는 데이터 자체와 후속 노드에 대한 포인터로 구성됩니다.
전체 연결 목록에 대한 액세스는 헤드 포인터에서 시작해야 하며, 헤드 포인터는 첫 번째 노드를 가리킵니다.
마지막 노드 포인터가 null(NULL)을 가리킴
노드 만들기
노드 삽입
노드 검색/트래버스
노드 삭제
Merge
포인터가 null을 가리킵니다
저장 데이터
class Node {
constructor(key) {
this.next = null;
this.key = key;
}
}각 연결 목록 다음을 가리키는 헤드 포인터가 있습니다. 첫 번째 노드, 노드가 없으면 NULL을 가리킵니다
class List {
constructor() {
this.head = null;
}
} static createNode(key) {
return new createNode(key);
}여기서 설명하겠습니다. 삽입 작업에 노드를 직접 캡슐화하는 대신 노드를 생성하는 정적 메서드를 노출했습니다. 그러한 논리가 더 정확해질 것입니다. -> 노드 생성 -> 연결 리스트에 노드를 삽입합니다. 데이터 조각을 매개 변수로 직접 사용하여 삽입 작업을 호출하고 삽입 내부에 노드를 만드는 방법을 소개하는 기사를 접할 수 있습니다.
삽입 작업에서는 노드의 포인터만 조정하면 됩니다. 두 가지 상황이 있습니다.
헤드가 어떤 노드도 가리키지 않아 현재 삽입된 노드를 나타냅니다. 첫 번째
head는 새 노드를 가리킵니다
새 노드의 포인터는 NULL
head는 노드를 가리킵니다.
head는 새 노드를 가리킵니다
새 노드의 포인터는 노드를 가리키는 원래 헤드를 가리킵니다.
insert(node) {
// 如果head有指向的节点
if(this.head){
node.next = this.head;
}else {
node.next = null;
}
this.head = node;
}헤드에서 검색 시작
노드의 키가 키와 동일한 것으로 확인되면 찾고 싶은 노드를 반환합니다
find(key) {
let node = this.head;
while(node !== null && node.key !== key){
node = node.next;
}
return node;
}여기 세 부분이 있습니다. 상황:
삭제할 노드가 첫 번째 노드인데, 이는 head가 가리키는 노드입니다
삭제할 노드의 다음 노드(node.next)를 가리킨다
삭제할 노드가 마지막 노드입니다
삭제할 노드의 이전 노드(prevNode)를 찾습니다. 삭제
prevNode의 포인터를 NULL
목록 중간에 있는 노드를 삭제합니다
삭제할 노드의 이전 노드(prevNode)를 찾습니다
지점 prevNode에서 현재 삭제하려는 노드의 다음 노드를 가리키는 포인터
delete(node) {
// 第一种情况
if(node === this.head){
this.head = node.next;
return;
}
// 查找所要删除节点的上一个节点
let prevNode = this.head;
while (prevNode.next !== node) {
prevNode = prevNode.next;
}
// 第二种情况
if(node.next === null) {
prevNode.next = null;
}
// 第三种情况
if(node.next) {
prevNode.next = node.next;
}
}class ListNode {
constructor(key) {
this.next = null;
this.key = key;
}
}
class List {
constructor() {
this.head = null;
this.length = 0;
}
static createNode(key) {
return new ListNode(key);
}
// 往头部插入数据
insert(node) {
// 如果head后面有指向的节点
if (this.head) {
node.next = this.head;
} else {
node.next = null;
}
this.head = node;
this.length++;
}
find(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}
delete(node) {
if (this.length === 0) {
throw 'node is undefined';
}
if (node === this.head) {
this.head = node.next;
this.length--;
return;
}
let prevNode = this.head;
while (prevNode.next !== node) {
prevNode = prevNode.next;
}
if (node.next === null) {
prevNode.next = null;
}
if (node.next) {
prevNode.next = node.next;
}
this.length--;
}
}위에 소개한 단방향 목록을 이해하셨다면, 그러면 여기에 소개된 양방향 목록은 실제로 거의 동일합니다.
위 그림을 보면 이중 연결 리스트와 단일 연결 리스트의 차이를 확실히 알 수 있습니다. 이중 연결 리스트에는 이전 노드를 가리키는 추가 포인터가 있습니다.
이전 노드에 대한 포인터
指向后一个节点的指针
节点数据
class ListNode {
this.prev = null;
this.next = null;
this.key = key;
}头指针指向NULL
class List {
constructor(){
this.head = null;
}
} static createNode(key){
return new ListNode(key);
}看上图中head后面的第一个节点可以知道，该节点的prev指向NULL
节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点
如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)
最后将head指向新的节点
insert(node) {
node.prev = null;
node.next = this.head;
if(this.head){
this.head.prev = node;
}
this.head = node;
}这里和单向节点一样，就直接贴代码了
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}和之前单向链表一样，分三种情况去看：
删除的是第一个节点
head指向所要删除节点的下一个节点
下一个节点的prev指针指向所要删除节点的上一个节点
删除的是中间的某个节点
所要删除的前一个节点的next指向所要删除的下一个节点
所要删除的下一个节点的prev指向所要删除的前一个节点
删除的是最后一个节点
要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址）
delete(node) {
const {prev,next} = node;
delete node.prev;
delete node.next;
if(node === this.head){
this.head = next;
}
if(next){
next.prev = prev;
}
if(prev){
prev.next = next;
}
} class ListNode {
constructor(key) {
// 指向前一个节点
this.prev = null;
// 指向后一个节点
this.next = null;
// 节点的数据(或者用于查找的键)
this.key = key;
}
}
/**
* 双向链表
*/
class List {
constructor() {
this.head = null;
}
static createNode(key) {
return new ListNode(key);
}
insert(node) {
node.prev = null;
node.next = this.head;
if (this.head) {
this.head.prev = node;
}
this.head = node;
}
search(key) {
let node = this.head;
while (node !== null && node.key !== key) {
node = node.next;
}
return node;
}
delete(node) {
const { prev, next } = node;
delete node.prev;
delete node.next;
if (node === this.head) {
this.head = next;
}
if (prev) {
prev.next = next;
}
if (next) {
next.prev = prev;
}
}
}这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。
위 내용은 JavaScript의 연결 목록에 대한 자세한 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
