js数据结构链接列表

每个人都在js中使用了数组. 该数组实际上是线性表的顺序存储结构. 它的特点是它使用一组连续的地址存储单元顺序存储数据元素. 而且它的缺点也是由它的特性引起的. 例如，当您删除或插入数组时，可能需要移动大量元素.

这是数组插入操作的粗略模拟:

    function insert(arr, index, data) {
      for (let i = arr.length; i >index; i--) {
        arr[i] = arr[i - 1];
      }
      arr[index] = data;
    }

从上面的代码可以看出，数组的插入和删除可以是O（n）操作. 这导致数据结构，例如链表. 链表不需要逻辑上相邻的元素在物理上相邻，因此它不具有顺序存储结构的缺点. 当然，它也失去了连续空间中数组的随机性. 访问的优点.

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

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

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

在这里解释一下，我展示了一个静态方法来创建节点，而不是直接将其封装到插入操作中，因为我觉得这种逻辑会更正确. 从创建链表->创建节点->将节点插入链表. 您可能会遇到一些介绍如何使用数据作为参数直接调用插入操作并在插入内容内创建创建节点的方法的文章.

插入操作仅需要调整节点的指针，两种情况:

头有一个尖头节点

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

这里有三种情况:

要删除的节点是最后一个节点

删除列表中间的节点

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

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

这里是一个小总结. 有些人在阅读时可能不理解. 我的建议是首先了解上述单链表. 实际上，只要您了解了链表的基本概念，就有一个头，然后有很多节点（Node），然后使用指针将它们串在一起，至于内部的插入操作，或删除，实际上所有人都在调整节点中的指针.

跟进可能是数据结构，可能是二进制堆链表的结构，或者可能转向程序中某些队列和堆栈思想的应用. 欢迎大家指出文章中的错误，如果您有任何写作建议，也可以提出. 我将继续写一些有关前端的技术文章，如果您喜欢它链表的结构，可以关注它

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-238792-1.html