我将继续完成链表文档中的循环链表部分。

循环链表可以基于单链表或双链表实现，这里我们基于单链表实现一个循环链表：

```javascript
class CircularLinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  // 在链表尾部添加节点
  append(data) {
    const newNode = new Node(data);
    
    // 如果链表为空
    if (!this.head) {
      this.head = newNode;
      newNode.next = this.head; // 指向自身形成环
    } else {
      // 找到最后一个节点
      let current = this.head;
      while (current.next !== this.head) {
        current = current.next;
      }
      
      // 添加新节点并形成环
      current.next = newNode;
      newNode.next = this.head;
    }
    
    this.size++;
  }
  
  // 在链表头部添加节点
  prepend(data) {
    const newNode = new Node(data);
    
    // 如果链表为空
    if (!this.head) {
      this.head = newNode;
      newNode.next = this.head; // 指向自身形成环
    } else {
      // 找到最后一个节点
      let current = this.head;
      while (current.next !== this.head) {
        current = current.next;
      }
      
      // 添加新节点到头部并更新环
      newNode.next = this.head;
      this.head = newNode;
      current.next = this.head; // 最后一个节点指向新的头节点
    }
    
    this.size++;
  }
  
  // 在指定位置插入节点
  insertAt(data, index) {
    // 检查索引是否有效
    if (index < 0 || index > this.size) {
      return false;
    }
    
    // 在头部插入
    if (index === 0) {
      this.prepend(data);
      return true;
    }
    
    // 在其他位置插入
    const newNode = new Node(data);
    let current = this.head;
    let previous = null;
    let count = 0;
    
    // 遍历到指定位置
    while (count < index) {
      previous = current;
      current = current.next;
      count++;
    }
    
    // 插入新节点
    newNode.next = current;
    previous.next = newNode;
    
    this.size++;
    return true;
  }
  
  // 删除指定值的节点
  remove(data) {
    if (!this.head) {
      return null;
    }
    
    let current = this.head;
    let previous = null;
    let removedData = null;
    
    // 如果头节点就是要删除的节点
    if (current.data === data) {
      // 如果链表只有一个节点
      if (this.size === 1) {
        this.head = null;
      } else {
        // 找到最后一个节点
        let last = this.head;
        while (last.next !== this.head) {
          last = last.next;
        }
        
        this.head = current.next;
        last.next = this.head; // 更新环
      }
      
      removedData = current.data;
      this.size--;
      return removedData;
    }
    
    // 查找要删除的节点
    do {
      previous = current;
      current = current.next;
      
      if (current.data === data) {
        previous.next = current.next;
        removedData = current.data;
        this.size--;
        return removedData;
      }
    } while (current !== this.head);
    
    return null;
  }
  
  // 打印链表
  print() {
    if (!this.head) {
      console.log("空链表");
      return;
    }
    
    let current = this.head;
    let result = "";
    
    do {
      result += current.data + " -> ";
      current = current.next;
    } while (current !== this.head);
    
    result += "(回到头部)";
    console.log(result);
  }
  
  // 其他方法（getAt, indexOf, isEmpty, getSize, clear）可以类似实现
}

循环链表使用示例

// 创建循环链表并进行操作
const circularList = new CircularLinkedList();

circularList.append(10);
circularList.append(20);
circularList.append(30);
circularList.print(); // 输出: 10 -> 20 -> 30 -> (回到头部)

circularList.prepend(5);
circularList.print(); // 输出: 5 -> 10 -> 20 -> 30 -> (回到头部)

circularList.insertAt(15, 2);
circularList.print(); // 输出: 5 -> 10 -> 15 -> 20 -> 30 -> (回到头部)

circularList.remove(20);
circularList.print(); // 输出: 5 -> 10 -> 15 -> 30 -> (回到头部)

链表的常见算法问题

1. 检测链表中的环

检测链表中是否存在环是一个经典问题，可以使用快慢指针（Floyd's Cycle-Finding Algorithm）解决：

function hasCycle(head) {
  if (!head || !head.next) {
    return false;
  }
  
  let slow = head;
  let fast = head;
  
  while (fast && fast.next) {
    slow = slow.next;       // 慢指针每次移动一步
    fast = fast.next.next;  // 快指针每次移动两步
    
    if (slow === fast) {    // 如果两个指针相遇，说明存在环
      return true;
    }
  }
  
  return false;
}

2. 找到链表的中间节点

使用快慢指针可以找到链表的中间节点：

function findMiddle(head) {
  if (!head) {
    return null;
  }
  
  let slow = head;
  let fast = head;
  
  while (fast && fast.next) {
    slow = slow.next;       // 慢指针每次移动一步
    fast = fast.next.next;  // 快指针每次移动两步
  }
  
  return slow; // 当快指针到达末尾时，慢指针正好在中间
}

3. 反转链表

反转链表是另一个常见问题：

function reverseList(head) {
  let prev = null;
  let current = head;
  let next = null;
  
  while (current) {
    next = current.next;    // 保存下一个节点
    current.next = prev;    // 反转指针
    prev = current;         // 移动prev指针
    current = next;         // 移动current指针
  }
  
  return prev; // 新的头节点
}

4. 合并两个有序链表

function mergeTwoLists(l1, l2) {
  // 创建一个哨兵节点
  const dummy = new Node(0);
  let tail = dummy;
  
  while (l1 && l2) {
    if (l1.data <= l2.data) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  
  // 连接剩余部分
  tail.next = l1 ? l1 : l2;
  
  return dummy.next;
}

5. 删除链表的倒数第N个节点

使用双指针可以在一次遍历中删除链表的倒数第N个节点：

function removeNthFromEnd(head, n) {
  const dummy = new Node(0);
  dummy.next = head;
  
  let first = dummy;
  let second = dummy;
  
  // 先让first指针前进n+1步
  for (let i = 0; i <= n; i++) {
    first = first.next;
  }
  
  // 然后两个指针一起前进，直到first到达末尾
  while (first) {
    first = first.next;
    second = second.next;
  }
  
  // 此时second.next就是要删除的节点
  second.next = second.next.next;
  
  return dummy.next;
}

链表的应用场景

链表在实际编程中有许多应用场景：

1. 实现其他数据结构：链表可以用来实现栈、队列、哈希表等数据结构
2. 内存管理：操作系统中的内存分配和回收
3. 历史记录：浏览器的前进/后退功能
4. 音乐播放列表：特别是循环链表适合实现循环播放功能
5. 图的邻接表表示：用链表表示图中每个顶点的邻接点
6. 多项式表示：用链表表示多项式的每一项

链表的性能分析

操作	单链表	双链表	循环链表
访问元素	O(n)	O(n)	O(n)
在头部插入	O(1)	O(1)	O(1)
在尾部插入	O(n)/O(1)*	O(1)	O(1)/O(n)**
在中间插入	O(n)	O(n)	O(n)
删除元素	O(n)	O(n)	O(n)
查找元素	O(n)	O(n)	O(n)

*如果维护一个尾指针，单链表在尾部插入可以是O(1)
**如果不维护尾指针，循环链表在尾部插入需要O(n)时间

链表与其他数据结构的比较

链表 vs 数组

特性	链表	数组
内存分配	动态分配，不连续	静态分配，连续
随机访问	O(n)	O(1)
插入/删除	O(1)（已知位置）	O(n)
内存利用	每个节点需要额外空间存储指针	只存储数据，空间利用率高
大小调整	灵活，可以动态增长	固定大小或需要重新分配

链表 vs 栈/队列

链表可以用来实现栈和队列，提供O(1)时间的插入和删除操作：

• 栈：在链表头部进行插入和删除操作
• 队列：在链表头部删除，尾部插入

链表的实际应用示例

实现LRU缓存

最近最少使用（LRU）缓存可以使用双链表和哈希表实现：

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // 哈希表，用于O(1)时间查找
    this.list = new DoublyLinkedList(); // 双链表，用于维护顺序
  }
  
  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    
    // 找到节点
    const node = this.cache.get(key);
    
    // 将节点移到链表头部（表示最近使用）
    this.list.moveToHead(node);
    
    return node.value;
  }
  
  put(key, value) {
    // 如果key已存在，更新值并移到头部
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this.list.moveToHead(node);
      return;
    }
    
    // 如果缓存已满，删除最久未使用的项（链表尾部）
    if (this.cache.size >= this.capacity) {
      const tail = this.list.removeTail();
      this.cache.delete(tail.key);
    }
    
    // 添加新节点到头部
    const newNode = this.list.addToHead(key, value);
    this.cache.set(key, newNode);
  }
}

// 为LRU缓存定制的双链表实现
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  addToHead(key, value) {
    const newNode = {
      key,
      value,
      prev: null,
      next: null
    };
    
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    
    return newNode;
  }
  
  moveToHead(node) {
    if (node === this.head) {
      return;
    }
    
    if (node === this.tail) {
      this.tail = node.prev;
      this.tail.next = null;
    } else {
      node.prev.next = node.next;
      node.next.prev = node.prev;
    }
    
    node.prev = null;
    node.next = this.head;
    this.head.prev = node;
    this.head = node;
  }
  
  removeTail() {
    const tail = this.tail;
    
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
      return tail;
    }
    
    this.tail = tail.prev;
    this.tail.next = null;
    
    return tail;
  }
}

总结

链表是一种基础但强大的数据结构，它通过指针将节点连接起来，形成一个线性序列。在JavaScript中，我们可以轻松实现单链表、双链表和循环链表，并利用它们解决各种编程问题。

链表的主要优势在于其动态性和灵活性，特别是在需要频繁插入和删除操作的场景中。虽然链表在随机访问方面不如数组，但它在内存利用和结构调整方面具有显著优势。

通过掌握链表的基本操作和常见算法，如检测环、查找中间节点、反转链表等，开发者可以更有效地解决复杂问题，并在适当的场景中选择最合适的数据结构。

参考资源

• MDN Web Docs: JavaScript数据结构
• LeetCode: 链表相关题目
• JavaScript数据结构与算法
• 计算机科学中的链表
• JavaScript中的数据结构：链表