一、介绍
JavaScript 原生提供了数组类型，但是却没有链表，虽然平常的业务开发中，数组是可以满足基本需求，但是链表在大数据集操作等特定的场景下明显具有优势，那为何 JavaScript 不提供链表类型呢？怎么实现一个完整可用的链表呢？
数组的特点
- 线性结构，顺序存储
- 插入慢，查找快
- 查找、更新、插入、删除，的时间复杂度分别为，O(1)、O(1)、O(n)、O(n)
链表的特点
- 线性结构，随机存储（省内存）
- 插入快，查找慢
- 查找、更新、插入、删除，的时间复杂度分别为，O(n)、O(1)、O(1)、O(1)
二、单链表
talk is easy, show the code, 下面用 JavaScript 实现一个相对完整的单链表，并提供以下方法供调用：
- push(element) // 链表尾部插入节点
- pop() // 链表尾部删除节点
- shift() // 删除头部节点、
- unshift(element) // 插入头部节点
- find(index) // 查找指定位置节点
- insert(element, index) // 指定位置插入节点
- edit(element, index) // 修改指定位置节点
- delete(index) // 链表删除指定位置节点
- cycle() // 使链表首尾成环
function initList() { class Node { constructor(item) { this.element = item } } class List { constructor() { this.head = null this.size = 0 this.last = null } /** * 链表查找元素 * @param index 查找的位置 */ find(index) { let current = this.head for (let i = 0; i < index; i++) { current = current.next } return current } /** * 链表尾部插入元素 * @param element 插入的元素 */ push(element) { let newNode = new Node(element) if (this.size === 0) { this.head = newNode this.head.next = null this.last = this.head } else { this.last.next = newNode this.last = newNode newNode.next = null } this.size += 1 } /** * 链表尾部删除元素 * @param element 删除的位置 */ pop(element) { this.last.next = null } /** * 链表头部删除元素 */ shift() { if (this.size === 0) return this.head = this.head.next if (this.size === 1) this.last = null this.size -= 1 } /** * 链表头部插入元素 * @param element 插入的元素 */ unshift(element) { let newNode = new Node(element) newNode.next = this.head this.head = newNode if (this.size === 0) this.last = this.head this.size += 1 } /** * 链表插入元素 * @param element 插入的位置, index 插入的位置 */ insert(element, index) { if (index < 0 || index > this.size) { console.error('超出链表节点范围') return } let newNode = new Node(element) if (this.size === 0) { // 空链表 newNode.next = null this.head = newNode this.last = newNode } else if (index === 0) { // 插入头部 newNode.next = this.head this.head = newNode } else if (index == this.size) { //插入尾部 newNode.next = null this.last.next = newNode this.last = newNode } else { // 中间插入 let preNode = this.find(index - 1) newNode.next = preNode.next preNode.next = newNode } this.size += 1 } /* *链表编辑元素 * @param element 编辑的元素，index 元素位置 */ edit(element, index) { let current = this.find(index) current.element = element } /* *链表删除元素 * @param index 删除元素位置 */ delete(index) { let current = this.find(index) if (index === 0) { // 删除头节点 this.head = this.head.next } else if (index === ((this.size) - 1)) { // 删除尾节点 let preNode = this.find(index - 1) preNode.next = null } else { // 删除中间节点 let preNode = this.find(index - 1) let nextNode = preNode.next.next let removeNode = preNode.next preNode.next = nextNode } this.size -= 1 } /* *链表使首尾成环 */ cycle() { this.last.next = this.head } } return new List() } let list = initList()
