Array、Linked List、Skip List

正确理解数组和链表在上面样的情景下使用非常重要,而且对数据结构的各个操作的复杂度要很清楚、


数组、链表、跳表

数据结构的存储方式从抽象到具体,其基础结构只有两种:数组(顺序存储)和链表(链式存储)。

Array

  顺序存储:计算机在内存中开辟了一块连续的地址,每个地址可通过内存管理器 来访问,所以无论访问哪个元素的速度都是一样的,可以随机访问任意元素。

  数组理论上每个元素的类型必须是相同的,但是在高级语言比如python中就可以在一个数组中有不同类型的元素

  • 优点:访问速度非常快
  • 缺点:在增加和删除元素的时候比较复杂

  插入操作,需要把插入位置后面的元素都向后移动,然后再插入,最坏的复杂度为O(n),最好的就是插在最后复杂度为O(1)。

  删除操作,先把要删除的地址对应的数据清除掉,然后把该位置后面的所有元素向前补位,最后一个位置设为空。唤起垃圾回收机制,或手动对数组的size进行修改。

平均复杂度 :

Insert操作指的是拥有要操作的项的引用时

Look up Search Insert Delete Space Complexity
O(1) O(n) O(n) O(n) O(n)

Linked list

Singly linked list

1
2
3
4
5
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

Doubly linked list

1
2
3
4
5
struct ListNode{
int val;
ListNode *prev, *next;
ListNode(int val):val(val),prev(NULL),next(NULL){}
};

两者复杂度相同,平均复杂度 :

Insert操作指的是拥有要操作的项的引用时

Look up Search Insert Delete Space Complexity
O(n) O(n) O(1) O(1) O(n)

Array vs Linked Lisk

  链表和数组在只知道下标的情况下,其时间复杂度都是O(n),因为数组不需要遍历,能直接取得要操作的对象,但是需要移动其后的所有项。链表无法直接获取要操作的对象,需要遍历获取,之后直接删除或者插入,而不需要移动其他项。

  之所以说链表的插入和删除比数组的性能好, 并不是说在任何情况下链表的插入和删除效率都要比数组的高 ,而是链表插入删除的最差时间复杂度也就是O(n),而在已得到要操作的结点的引用时,它就能省去遍历的步骤直接插入删除,时间复杂度为O(1),并且数组会有比如扩容等操作造成很多额外的时间支出,以及内存碎片所导致的空间支出。

  倘若不考虑这些,在只有下标的情况下执行插入和删除,它们的性能其实是没有太大区别的,就时间复杂度上来看都是O(n),然而实际情况下是不可能不考虑这些的。

  • 插入、删除:链表性能好
  • 查询、修改:数组性能好

Skip List

时间复杂度

  跳表的特点:跳表是基于链表的,但是有序的链表,所以跳表里面的元素始终是有序的。

  • 跳表对标的是平衡树(AVL Tree)和二分查找,

  • 优势原理简单、容易实现、方便扩展、效率更高。

  • 工程应用:Redis、LevelDB、LRU缓存机制

  对于一个链表来说,它的搜索效率是不高的,我们需要遍历所有的元素,才能知道一个元素是否存在于一个链表中,如何高效的对链表进行搜索呢?

   升维思想 :如何利用附加信息加速,一维信息如果要进行加速的话经常采用的方式是升维度变为二维。多一级的信息就是用空间换时间。

   如何进一步提高效率,那就再加多级索引

   时间复杂度:

跳表的缺点:

  • 由于元素的增加和删除导致索引发生改变
  • 维护成本较高,增加或删除元素都需要对索引进行更新

平均复杂度 :

Insert操作指的是拥有要操作的项的引用时

Look up Search Insert Delete Space Complexity
O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(nlog(n))

空间复杂度分析

12+14+18+...<1\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ... < 1
(12+14+18+...)n<n(\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ...) \cdot n < n

取最大复杂度,所以空间复杂度为O(n)

参考

https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
https://www.zhihu.com/question/20202931
https://leetcode-cn.com/problems/lru-cache/

Big things have small beginnings.