概念

链表与数组相似，都是有序的线性结构，不过数组在内存空间中是连续的，而链表中的每一项——结点，则是离散的。
在链表中，每个结点包括两部分：数据域和指针域，指针域用来指向下一个结点。JS中的链表通过嵌套对象实现

  1. {
  2.   val: 1, // 数据域
  3.   next: {
  4.       val: 2,
  5.     next: ...
  6.   }
  7. }

链表结点的创建：

  1. function ListNode(val) {
  2.   this.val = val;
  3.   this.next = null;
  4. }
  6. const node1 = new ListNode(1)
  7. node1.next = new ListNode(2)

image.png

链表元素的添加，删除

添加

任意两个结点之间添加一个新结点：
image.png

  1. const node3 = new Listnode(3)
  2. node3.next = node1.next // 也就是 node2 
  3. node1.next = node3

删除

任意两个结点之间删除一个结点：
image.png
由于链表的访问是单向的，只能通过 next 指针从前往后访问，所以删除 node3 的关键是找到它的前驱结点 node1，直接让 node1 的 next 指向 node3 的next（node2），node3 由于不再被引用，会被自动垃圾回收掉。

  1. node1.next = node1.next.next

链表和数组的辨析

js 中的数组

大多数计算机语言中数组对应着一段连续的内存，假设数组的长度是 n ，那么增加/删除操作导致需要移动的元素数量与 n 成线性关系。所以数组的增加/删除操作对应复杂度是O(n)
但 js 中的数组未必是真正的数组

  1. const arr1 = [1, 2, 3] // 真正的数组
  2. const arr2 = ['a', 1, {name: 'wy'}]

arr2 就不是真正的数组，内存不连续，其底层使用哈希映射分配内存空间，是由对象链表来实现的。

链表与数组的对比

  • 增删操作高效：链表与数组对比，增删元素不需要挪动多余的元素，只需要改变指针的指向，与链表结点个数 n 无关，复杂度是常数级别O(1)
  • 访问操作低效：数组中可以直接通过索引访问元素，复杂度是O(1)。链表中访问元素只能从头遍历结点，复杂度与链表结点个数 n 成线性关系，复杂度是O(n)

总结来说：链表的插入/删除效率高，而访问效率低。数组的访问效率高，插入/删除效率低。