【0642_Week 01】学习总结

[gk918]

数组
数组用一块连续的内存空间，来存储相同类型的一组数据。
支持随机访问，时间复杂度 O(1)
插入、删除操作比较低效，为了满足连续空间需要进行数据的搬移，平均情况时间复杂度为O(n)

链表
链表内存空间可以不连续
链表类型有：单链表、双向链表、循环链表、双向循环链表等
更适合插入、删除操作频繁的场景，时间复杂度 O(1)
但是访问时需要遍历链表 ，平均情况时间复杂度为O(n)
某些情况下双向链表的访问比单链表更高效，如指定访问某个节点前面的节点
为了提高访问效率，用空间换时间的设计思路出现跳表

跳表
通过空间换时间，构建多级索引来提高查询的效率，实现了基于链表的“二分查找”
是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度为O(nlogn)

[AndrewOYLK]

总结的挺详细，我也稍微补充下：

1. 数组
   在随机访问的情况下，即通过索引访问数组中的元素时，时间复杂度是O(1)
   但是如果需要查找指定的值时，是需要遍历数据，这时时间复杂度是O(n)

2. 链表
   不支持随机访问，所以查看指定值时需要遍历链表，所以时间复杂度时O(n)
   在插入、删除操作的时候，需要考虑是否需要先查找数据，如果先查找数据，再执行插入和删除那么时间复杂度也是O(n)，如果是在已知结点的情况下进行插入或者删除，这时候时间复杂度是O(1)

小结：主要想表述的是，要区分是否是给定值还是需要查找指定值的情况下，去判断数组和链表在查找、插入、删除的时间复杂度