一、什么叫链表

  1. 多个元素存储的列表
  2. 链表中的元素在内存中不是顺序存储的，而是通过”next”指针联系在一起的。

    js中的原型链 原理就是 链表结构

二、链表和数组的区别

  1. 数组：有序存储的，在中间某个位置删除或者添加某个元素，其他元素要跟着动。

    • arr[0]，arr[1] 数组随机访问的时间复杂度是O(1)
    • [1,2,3,4]在2后加上一个6，那么3，4先往后移动一个位置，然后再加上6。数组新增(删除)元素的时间复杂度是O(n)，数组新增元素，插入和删除元素性能都比较差

  2. 链表：不是顺序存储的，而是通过”next”指针联系在一起的。

    • 随机访问的时间复杂度O(n)，因为是一个一个找
    • 删除和插入的时间复杂度O(1)，1 x 断了2 x 断了3===》1=>3=>4
      1. // 1=>2=>3=>4 链表（单项链表）
      2. {
      3. a:1,
      4. next:{
      5.  b:2,
      6. next:{
      7.  c:3,
      8.  next:null
      9. }
      10. }
      11. }

      讲数据结构的时候，通常都是讲它的增删改查，如链表的增删改查

时间复杂度、空间复杂度，现在更关注时间复杂度，因为存储很便宜，时间很值钱

  1. 链表的类型

单项链表
双向链表
环形链表
…
单向链表.png
双向链表.png

  1. 数组，链表数据结构分别什么时候使用：

javascript中没有链表，可以用js写一个
随机访问用数组、删除插入用链表

  1. 查找最后一个值：数组遍历可以直接用length、for循环直接查最后一个。而链表的查找最后一个只能用while、do…while…

三、链表的增删改查

  1. // 链表
  2. let a = {key:'aaa'};
  3. let b = {key:'bbb'};
  4. let c = {key:'ccc'};
  5. let d = {key:'ddd'};
  7. a.next = b;
  8. b.next = c; 
  9. c.next = d;
  10. d.next = null;
  12. console.log( a );
  1. 遍历链表 ```javascript let obj = a; // a为头节点

while( obj && obj.key ){ console.log( obj.key ); obj = obj.next; // 遍历的条件 }

  2. 2. 链表中插入节点
  3. ```javascript
  4. let m = {key:'mmmmm'};
  5. c.next = m;
  6. m.next = d;
  7. console.log( a );

  1. 删除链表某个节点

    1. 直接改变next指针指向
    1. // 删除上面新增的m节点
    2. c.next = d;