数组

• 内存管理器
  • 申请数组时内存管理器在内存中开辟一段连续地址
  • 每个地址都可以通过内存管理器进行访问
  • 访问任何一个元素的时间复杂度都是O(1)
• 数组的查询时间复杂度都是O(1) 非常快
• 数组的问题
  • 增、删操作的时间复杂度是O(n)
  • 增加元素的操作会先拷贝目标index后面的元素都往后移一位，然后在index中插入
  • 删除是增加的反向操作也是平均下来是O(n)的复杂度
  • 所以尽量在增、删的时候操作数组的最后一项，降低复杂度

链表

• LinkedList
• 弥补数组增删的缺点
• 工程应用
  • LRU算法

• 分类
  • 单向链表（只有next指向后一个元素）
  • 双向链表（既有next也有previous）
  • 循环链表（tail的next指向head）
• 增删节点时间复杂度为O(1)，但平均查询的时间复杂度为O(n)必须从头或尾一步一步查询

跳表

• SkipList
• 解决链表查询时间复杂度高的问题，降到O(log n)
  • 升维，不再一步一步走
  • 空间换时间，使用更多的index索引加快访问速度
• 工程应用
  • Redis中使用

• 空间复杂度

实战

讲解

• https://leetcode.cn/problems/move-zeroes/
• https://leetcode.cn/problems/container-with-most-water/
• https://leetcode.cn/problems/climbing-stairs/
• https://leetcode.cn/problems/two-sum/

• https://leetcode.cn/problems/3sum/

  练习

• https://leetcode.cn/problems/reverse-linked-list/

• https://leetcode.cn/problems/swap-nodes-in-pairs
• https://leetcode.cn/problems/linked-list-cycle
• https://leetcode.cn/problems/linked-list-cycle-ii
• https://leetcode.cn/problems/reverse-nodes-in-k-group/
• https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
• https://leetcode.cn/problems/rotate-array/
• https://leetcode.cn/problems/merge-two-sorted-lists/
• https://leetcode.cn/problems/merge-sorted-array/
• https://leetcode.cn/problems/plus-one/