JavaScript의 연결 목록에 대한 자세한 소개-JS 튜토리얼-php.cn

JS에서는 누구나 배열을 사용해 왔습니다. 배열은 실제로 선형 테이블의 순차적 저장 구조입니다. 그 특징은 연속된 주소를 가진 저장 단위 집합을 사용하여 데이터 요소를 순차적으로 저장하는 것입니다. 단점은 배열을 삭제하거나 삽입할 때 많은 수의 요소를 이동해야 하는 등의 특성 때문이기도 합니다.

다음은 배열 삽입 작업의 대략적인 시뮬레이션입니다.

    insert(arr, index, data){
        for(let i = index + 1; i <p> 위 코드에서 배열의 삽입 및 삭제가 O(n) 작업일 수 있음을 알 수 있습니다. 이는 연결리스트의 데이터 구조로 이어집니다. 연결리스트는 논리적으로 인접한 요소가 물리적 위치에서 인접할 필요가 없으므로 순차 저장 구조의 단점도 없습니다. 연속적인 공간에 배열되는 장점. </p><h3 id="단방향-연결-목록">단방향 연결 목록</h3><p><span class="img-wrap"><img src="/static/imghw/default1.png" data-src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" class="lazy" title="1546394138978971.png" alt="JavaScript의 연결 목록에 대한 자세한 소개"></span></p><h4 id="단방향-연결-목록의-특징"> 단방향 연결 목록의 특징: </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 &amp;&amp; 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 &amp;&amp; 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--;
  }
}

로그인 후 복사

이중 연결리스트

위에 소개한 단방향 목록을 이해하셨다면, 그러면 여기에 소개된 양방향 목록은 실제로 거의 동일합니다.

JavaScript의 연결 목록에 대한 자세한 소개

위 그림을 보면 이중 연결 리스트와 단일 연결 리스트의 차이를 확실히 알 수 있습니다. 이중 연결 리스트에는 이전 노드를 가리키는 추가 포인터가 있습니다.

노드 초기화

이전 노드에 대한 포인터
指向后一个节点的指针
节点数据

    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 &amp;&amp; node.key !== key) {
      node = node.next;
    }
    return node;
  }

로그인 후 복사

删除节点

和之前单向链表一样，分三种情况去看：

删除的是第一个节点

head指向所要删除节点的下一个节点
下一个节点的prev指针指向所要删除节点的上一个节点

删除的是中间的某个节点

所要删除的前一个节点的next指向所要删除的下一个节点
所要删除的下一个节点的prev指向所要删除的前一个节点

删除的是最后一个节点

要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址）

JavaScript의 연결 목록에 대한 자세한 소개

    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 &amp;&amp; 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;
    }
  }
}

로그인 후 복사