JavaScript의 연결 목록에 대한 자세한 소개
- 不言앞으로
- 2019-01-02 09:58:235862검색
이 글은 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;
}
}
Create node
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!