02.数组、链表、跳表
一、数组 Array
- 申请数组,会开辟出一个连续地址的内存空间。访问数组中的任何一个元素,时间复杂度都是一样的,都是常数时间O(1)。访问速度快是数组的特性之一。
- 增加/删除数组,时间复杂度的效率低。
二、链表 Linked List
链表的 数据结构就是为了弥补数组的缺点。
单链表:只有一个Next指针。
双向链表:有向后指针 Next 和先前指针 prev或 previous。
头指针:Head
尾指针:Tail
最后一个尾数:Next 指向空 None 。
循环链表:最后 Next 从Tail 指向 Head 。
- 链表的添加/删除操作,没有引起整个链表的群移操作,也不需要复制元素,挪动到新的位置。因此,链表的移动效率和修改操作的效率非常高为O(1) 。
- 链表从头节点或从尾节点访问,时间复杂度为O(1)。但缺点是要访问这个链表中任何一个位置,就比较复杂了。随机查看里边的任何一个元素,时间复杂度为O(n)。
三、跳表 skiplist
链表元素有序的时候,一种新的数据结构出现了——跳表。
跳表在 Redis 中使用最多,而 redis 不使用红黑树。
- 跳表的特点:
- 思考一个问题:
【重要思想】一维有序的数据结构,要想使时间复杂度变低,经常采用的加速方法就是升维,也就是说变成二维。因为,多一个维度,就会有多一级的信息在里面。
增加多级索引
- 跳表查询的时间复杂度O(log n)
- 跳表的空间复杂度
- 高级数据结构
小结
- 数组、链表、跳表的时间复杂度、空间复杂度
- 工程应用
- 跳表:升维思想 + 空间换时间