JavaScript数据结构链表知识详解

什么是链表

链表是一种线性结构，相比于数组，它不需要一块连续的内存空间，而是通过指针将一组零散的内存块串联起来使用。链表只保持一个指向链表中第一个节点的引用，每个节点则有指向下一个节点的指针。

链表的实现

链表的实现方式有很多种，下面介绍一种简单的单向链表实现方式，其中每个节点包含一个value属性和一个next属性，next属性指向下一个节点（没有则为null）。

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  append(value) {
    const node = new ListNode(value);
    if (this.head === null) {
      // 链表为空，添加第一个节点
      this.head = node;
    } else {
      // 链表不为空，遍历到最后一个节点，添加新的节点
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }

  insert(value, position) {
    if (position < 0 || position > this.length) {
      // 如果指定的位置小于0或大于链表长度，不能插入
      return false;
    }
    const node = new ListNode(value);
    if (position === 0) {
      // 添加到链表头部
      node.next = this.head;
      this.head = node;
    } else {
      // 找到要插入位置的前一个节点，插入节点
      let index = 0;
      let current = this.head;
      let previous = null;
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      node.next = current;
      previous.next = node;
    }
    this.length++;
    return true;
  }

  remove(position) {
    if (position < 0 || position >= this.length) {
      // 如果指定的位置小于0或大于等于链表长度，不能删除
      return false;
    }
    if (position === 0) {
      // 删除链表头部节点
      this.head = this.head.next;
    } else {
      // 找到要删除位置的前一个节点，删除节点
      let index = 0;
      let current = this.head;
      let previous = null;
      while (index < position) {
        previous = current;
        current = current.next;
        index++;
      }
      previous.next = current.next;
    }
    this.length--;
    return true;
  }

  indexOf(value) {
    let index = 0;
    let current = this.head;
    while (current !== null) {
      if (value === current.value) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

  toString() {
    let listString = '';
    let current = this.head;
    while (current !== null) {
      listString += current.value + ' ';
      current = current.next;
    }
    return listString;
  }
}

链表的应用

链表可以用来解决很多问题，比如：

1. 链表可以用来实现栈和队列：栈和队列都是顺序访问的数据结构，用数组实现时需要考虑数组的大小问题，而用链表实现则没有这个问题。
2. 链表可以用来实现哈希表：哈希表需要快速插入、删除和查找元素，使用链表可以实现这个目标。
3. 链表可以用来实现LRU缓存算法：LRU缓存算法需要快速插入、删除和查找元素，使用链表实现可以达到O(1)的时间复杂度。

下面举两个链表的应用示例：

示例1：用链表实现栈

栈是一种后进先出（LIFO）的数据结构，可以用链表来实现。栈的基本操作包括push、pop和peek。

class Stack {
  constructor() {
    this.list = new LinkedList();
  }

  push(value) {
    this.list.append(value);
  }

  pop() {
    if (this.list.length === 0) {
      return null;
    }
    const index = this.list.length - 1;
    const value = this.list.get(index);
    this.list.remove(index);
    return value;
  }

  peek() {
    if (this.list.length === 0) {
      return null;
    }
    const index = this.list.length - 1;
    return this.list.get(index);
  }

  toString() {
    return this.list.toString();
  }
}

示例2：用链表实现LRU缓存算法

LRU缓存算法（Least Recently Used）是一种常用的缓存淘汰算法，它基于这样一个假设：如果数据最近被访问过，那么将来被访问的几率也很高。根据这个原理，LRU缓存算法将最近最少使用（Least Recently Used）的数据淘汰掉。

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.list = new LinkedList();
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) {
      return null;
    }
    const node = this.map.get(key);
    // 移动到链表头部
    this.list.removeNode(node);
    this.list.addNodeToFront(node);
    return node.value.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      // 如果已存在，更新值，并移动到链表头部
      const node = this.map.get(key);
      node.value.value = value;
      this.list.removeNode(node);
      this.list.addNodeToFront(node);
    } else {
      // 如果不存在，添加到链表头部
      const node = new ListNode({ key, value });
      this.list.addNodeToFront(node);
      this.map.set(key, node);
      // 检查容量是否超出限制
      if (this.map.size > this.capacity) {
        // 如果超出限制，删除链表尾部节点和map中的对应项
        const nodeToDelete = this.list.tail;
        this.list.removeNode(nodeToDelete);
        this.map.delete(nodeToDelete.value.key);
      }
    }
  }

  toString() {
    return this.list.toString();
  }
}