链表（多个元素组成的列表）

数组与链表区别

• 数组中增删非首尾元素都需要移动元素
• 链表不需要移动元素，只需要更改next指向。

概念

JS中没有链表，需要使用Object来模拟链表

1. 遍历列表

   1. 声明一个新的指针指向链表头部

   2. 使用while循环不断访问指针的next

   3. let p = a
      while(p){
          console.log(p)
          p = p.next
      }
      

2. 插入和删除

   1. 直接改变next的指针

      1. // 插入
         const e = { val:e }
         c.next = e
         e.next = d
         
         // 删除
         c.next = d
         

实际算法

1. leetcode 237 (opens new window)

   1. 时间复杂度：没有循环O(1)
   2. 空间复杂度：没有数组和矩阵O(1)

2. leetcode 206 (opens new window)

3. 思路

   • 简化：翻转两个节点，即将n+1的next指向n

4. 两个数相加 (opens new window)

5. 删除排序链表中的重复元素 (opens new window)

6. 环形链表 (opens new window)

JS与链表相关概念：原型链

• 原型链的本质就是链表。
• 如果A.__proto__能找到B.__proto__则 A instanceof B 为true
• 如果A对象上找不到X属性，则会沿着A的原型链向上查找X属性

总结