带你读《图解算法小抄》一、链表（1）https://developer.aliyun.com/article/1348318?groupCode=tech_library
2. 链表（LinkedList）
链表是由一系列链表节点组成的数据结构。它具有一个头节点（head）和一个尾节点（tail），分别表示链表的开头和结尾。
链表类提供了一系列方法来操作链表，如在开头插入节点（prepend）、在末尾插入节点（append）、在指定位置插入节点（insert）、删除节点（delete）、查找节点（find）等。以下是链表类的实现代码：
class LinkedList { constructor() { this.head = null; this.tail = null; this.length = 0; } // 在链表尾部添加新节点 append(value) { const newNode = new Node(value); if (!this.head) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } this.length++; } // 在链表指定位置插入新节点 insertAt(value, index) { if (index < 0 || index > this.length) { throw new Error("Index out of range"); } const newNode = new Node(value); if (index === 0) { newNode.next = this.head; this.head = newNode; if (!this.tail) { this.tail = newNode; } } else if (index === this.length) { this.tail.next = newNode; this.tail = newNode; } else { let currentNode = this.head; let prevNode = null; let currentIndex = 0; while (currentIndex < index) { prevNode = currentNode; currentNode = currentNode.next; currentIndex++; } prevNode.next = newNode; newNode.next = currentNode; } this.length++; } // 获取指定位置节点的值 getAt(index) { if (index < 0 || index >= this.length) { throw new Error("Index out of range"); } let currentNode = this.head; let currentIndex = 0; while (currentIndex < index) { currentNode = currentNode.next; currentIndex++; } return currentNode.value; } // 删除指定位置的节点 removeAt(index) { if (index < 0 || index >= this.length) { throw new Error("Index out of range"); } let currentNode = this.head; let prevNode = null; let currentIndex = 0; if (index === 0) { this.head = currentNode.next; if (this.length === 1) { this.tail = null; } } else if (index === this.length - 1) { while (currentIndex < index) { prevNode = currentNode; currentNode = currentNode.next; currentIndex++; } prevNode.next = null; this.tail = prevNode; } else { while (currentIndex < index) { prevNode = currentNode; currentNode = currentNode.next; currentIndex++; } prevNode.next = currentNode.next; } this.length--; } // 遍历链表并将节点值以数组形式返回 toArray() { const result = []; let currentNode = this.head; while (currentNode) { result.push(currentNode.value); currentNode = currentNode.next; } return result; } }const linkedList = new LinkedList(); linkedList.append(10); linkedList.append(20); linkedList.insertAt(15, 1); linkedList.removeAt(0); console.log(linkedList.toArray()); // 输出: [15, 20]
3. 复杂度
链表的时间复杂度如下：
∙ 访问：O(n)
∙ 搜索：O(n)
∙ 插入：O(1)
∙ 删除：O(1)
链表的空间复杂度为O(n)，其中n是链表中的节点数。
4. 参考资料
∙ YouTube
