js实现链表（单链表、双向链表、跳表）

单链表

// 定义单个节点
class Node {
  constructor(el) {
    this.el = el;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = new Node('head');
  }
  // 用于查找
  find(item) {
    let node = this.head;
    while (node !== null && node.el !== item) {
      node = node.next;
    }
    return node;
  }
  findPrev() {
    let node = this.head;
    while (node.next !== null && node.next.el !== item) {
      node = node.next;    
    }
    return node;  
  }
  // 插入节点
  insert(el, item) {
    const newNode = new Node(el);
    const currentNode = this.find(item);
    newNode.next = currentNode.next;
    currentNode.next = newNode;
  }
  // 删除节点
  remove(item) {
    const prevNode = this.findPrev(item); // 先找到待删除的元素
    if (prevNode.next !== null) {
      // 指向下一个元素，这行代码很关键
      prevNode.next = prevNode.next.next;
    }
  }
}

双向链表

Node

和单链表类似，在原有的 Node 基础上，增加一个 prev 指针。

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

查找

双向链表的查找和单链表是一模一样的

插入

function insert(el, item) {
  const newNode = new Node(el);
  const currentNode = this.find(item);
  // 新节点的下一个值指向当前节点的下一个值
  newNode.next = currentNode.next;
  // 新节点的前一个值指向当前节点
  nextNode.prev = currentNode;
  // 当前节点的下一个值指向新节点
  currentNode.next = newNode;
  // 当前节点的下一个节点的前一个节点指向新的值
  currentNode.next.prev = newNode;
}

删除

function remove(item) {
  const node = this.find(item);
  // 当前节点的前一个值的下一个值指向当前节点的下一个值 (相当于把当前节点略过了)
  node.prev.next = node.next;
  // 当前节点的下一个值的前一个值指向当前节点的前一个值
  node.next.prev = node.prev;
  当前节点的下一个值和前一个值指向null 完成删除
  // node.next = null;
  node.prev = null;
}

跳表

参考

https://101.zoo.team/lian-biao