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

이 글은 JavaScript의 링크드 리스트에 대한 자세한 소개를 담고 있습니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

링크된 목록과 배열

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 && 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!