Detailed introduction to linked lists in JavaScript

This article brings you a detailed introduction to linked lists in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Linked list and array

Everyone has used arrays in js. Arrays are actually a sequential storage structure of linear tables. Its characteristic is that it uses a set of addresses. Consecutive memory cells store data elements one after another. Its shortcomings are also caused by its characteristics. For example, when deleting or inserting an array, a large number of elements may need to be moved.

Here is a rough simulation of the insertion operation of the array:

    insert(arr, index, data){
        for(let i = index + 1; i <p>It can be seen from the above code that the insertion and deletion of the array may be an O(n) operation. This leads to the data structure of the linked list. The linked list does not require logically adjacent elements to be adjacent in physical locations, so it does not have the shortcomings of the sequential storage structure. Of course, it also loses the randomness of the array in a continuous space. Advantages of access. </p><h3>One-way linked list</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="Detailed introduction to linked lists in JavaScript"></span></p><h4>Characteristics of one-way linked list:</h4>

• Use one Arrange any memory space to store data elements (the memory space here can be continuous or discontinuous)

• Each node (node) consists of the data itself and a Pointers to subsequent nodes are composed of

• . Access to the entire linked list must start from the head pointer, which points to the first node

• The last node The pointer points to null (NULL)

Several main operations in the linked list

• Creating nodes

• Insert node

• Search/Traverse node

• Delete node

• Merge

Initialize node

• Pointer points to null

• Storage data

    class Node {
        constructor(key) {
            this.next = null;
            this.key = key;
        }
    }

Initialize one-way linked list

• Each linked list has a head pointer, pointing to the first node, if there is no node, it points to NULL

    class List {
        constructor() {
            this.head = null;
        }
    }

Create Node

    static createNode(key) {
        return new createNode(key);
    }

Let me explain here, I exposed a static method to create the node, rather than directly encapsulating it into the insertion operation, because I feel that such logic will be more Be more correct. Create a linked list from -> Create a node -> Insert the node into the linked list. You may encounter some articles that introduce a way to directly use a piece of data as a parameter to call the insert operation, and create a node inside the insert.

Insert node (after inserting into the head node)

The insertion operation only needs to adjust the pointer of the node. There are two situations:

• Head does not exist Points to any node, indicating that the currently inserted node is the first one

• head points to the new node

• The pointer of the new node points to NULL

• head points to the node

• head points to the new node

• The pointer of the new node points to the node pointed by the original head

    insert(node) {
        // 如果head有指向的节点
        if(this.head){
           node.next = this.head;
        }else {
           node.next = null;
        }
        this.head = node;
    }

Search for the node

• Search from head

• When the key in the node is found to be equal to the key you want to find, return the node

    find(key) {
        let node = this.head;
        while(node !== null && node.key !== key){
            node = node.next;
        }
        return node;
    }

Delete the node

There are three parts here This situation:

• The node to be deleted happens to be the first one, which is the node pointed by head

• Point head to the node you want to delete Delete the next node of the node (node.next)

• The node to be deleted is the last node

• Find Go to the previous node (prevNode) of the node to be deleted

• Point the pointer in prevNode to NULL

• Delete a certain node in the middle of the list Nodes

• Find the previous node (prevNode) of the node to be deleted

• Point the pointer in prevNode to the current node to be deleted The next node of this node

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

The overall code of the one-way linked list

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

Doubly linked list

If you put the above introduction We have already understood the one-way list, so the two-way list introduced here is actually similar.

You can clearly see the difference between a doubly linked list and a singly linked list from the above figure. The doubly linked list has an additional pointer pointing to the previous node.

Initialize node

• Pointer to the previous node

• 指向后一个节点的指针

• 节点数据

    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)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。

The above is the detailed content of Detailed introduction to linked lists in JavaScript. For more information, please follow other related articles on the PHP Chinese website!