本文共 543 字，大约阅读时间需要 1 分钟。

一、数组

1. 数组是一段连续地址的内存，使用内存管理器（memory controller）访问，访问的时间复杂度为O（1）。
2. 增（删）元素：插入（删除）一个元素，该位置后元素全部后移（前移），时间复杂度为O（n）。
3. 数组扩张时，如果原有内存大小不能满足需求，则开辟一块原来大小两倍的内存，用以复制旧数组。

二、链表

1. node，有单链表、双向链表、循环链表，pHead/pTail/构造函数。
2. 增删不涉及群移操作，移动和修改操作的时间复杂度为O（1）。
3. 访问元素节点的时间复杂度为线性复杂度O（n）。
4. LRU cache利用链表。

三、跳表

1. Skip List，只能用于元素有序的情况。
2. 跳表对标的是平衡树AVL和二分查找，是一种插入/删除/搜索都是O（logn）的数据结构。
3. 优势是原理简单、容易实现、方便拓展、效率高，在一些热门的项目中来替代平衡树，如Redis，LevelDB（Google，Jeff Dean）
4. 跳表是一维数组升维实现的，在思考提升链表插座的效率的过程中，原链表如下：

建立第一级索引：

建立第二级索引：

建立多级索引：

5. 现实中跳表的形态

6.跳表查找的时间复杂度为O（logn）；增加和删除需要维护更新索引，时间复杂度为O（logn），空间复杂度为O（n）。

转载地址：https://blog.csdn.net/Fan_z_0802/article/details/107828761 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！