链表
单链表
- 数组需要一块连续的内存空间来存储,而链表并不需要,而是通过指针将一组零散的内存块串联起来
- 为了将所有结点串起来,每个链表的结点除了存储数据之外,还需要记录下一个结点的地址
- 将记录下个结点地址的指针称为后继指针next
- 有两个结点比较特殊,分别是第一个结点和第二个结点,习惯性地称为头结点和尾结点
- 头结点用来记录链表的基地址
- 尾结点的指针指向的不是下一个结点,而是指向一个空地址NULL,表示这是链表上的最后一个结点
插入 + 删除
- 数组的插入和删除操作,为了保持内存数据的连续性,需要做大量的数据搬移,时间复杂度为
O(n)
- 链表的插入和删除操作,并不需要为了保持内存的连续性而搬移结点,因为链表的存储空间本身就不是连续的
- 因此在链表中插入和删除一个数据是非常快速的,只需要考虑相邻结点的指针变化,时间复杂度为
O(1)
- 因此在链表中插入和删除一个数据是非常快速的,只需要考虑相邻结点的指针变化,时间复杂度为
随机访问
- 链表中的数据并非连续存储,无法像数组那样,根据首地址和下标,通过寻址公式直接计算出对应的内存地址
- 而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点,时间复杂度为
O(n)
循环链表
- 循环链表是一种特殊的单链表,单链表的尾结点指向空地址NULL,而循环链表的尾结点指针指向链表的头结点
- 与单链表相比,循环链表的优点是从链尾到链头比较方便,当要处理的数据具有环型结构特点时,适合采用循环链表
双向链表
- 单向链表只有一个方向,结点只有一个后继指针next指向后面的结点
- 双向链表支持两个方向,每个结点除了有后继指针next指向后面的结点,还有前驱结点prev指向前面的结点
- 双向链表需要额外的空间来储存后继结点和前驱结点的地址,比单链表占用更多的内存空间,但支持双向遍历,更加灵活
- 双向链表查找前驱结点的时间复杂度为
O(1)
,在某些场景下,双向链表的插入和删除操作要比单链表简单高效 - 在实际的软件开发中,虽然双向链表占用更多的内存,但还是比单链表有更广的应用,体现了空间换时间的设计思想
插入 + 删除
- 删除结点中“值等于某个给定值”的结点
- 不管单链表还是双向链表,都需要从头结点开始一个一个依次遍历对比,直到找到的值等于给定值的结点
- 单纯的删除操作的时间复杂度为
O(1)
,但遍历查找的时间复杂度为O(n)
,因此总的时间复杂度为O(1)
- 删除给定指针指向的结点
- 此时已经找到要删除的结点,但删除某个结点需要知道其前驱结点,而单链表并不支持直接获取前驱结点
- 所以,单链表为了找到前驱结点,还是需要从头结点开始遍历链表
- 而双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历
- 在这种场景下,使用单链表的时间复杂度为
O(n)
,而使用双向链表的时间复杂度为O(1)
- 此时已经找到要删除的结点,但删除某个结点需要知道其前驱结点,而单链表并不支持直接获取前驱结点
- 同理,在链表中某个指定结点的前面插入一个结点,使用双向链表的时间复杂度为
O(1)
,而使用单链表的时间复杂度O(1)
查找
- 对于一个有序链表,双向链表按值查询的效率也要比单链表要高一些
- 可以记录上次查找的位置,每次查询时,根据情况决定往前查找还是往后查找,平均只需要查找一半的数据
对比数组
时间复杂度
操作 | 数组 | 链表 |
---|---|---|
插入/删除 | O(n) | O(1) |
随机访问 | O(1) | O(n) |
CPU缓存
- 数组使用连续的内存空间,可以利用CPU的缓存机制,预读数组中的数据,访问效率更高
- 链表在内存中并不是连续存储,对CPU缓存不友好,没办法有效预读
固定大小
- 数组的缺点是大小固定,一经声明就要占用整块连续内存空间
- 如果声明过大,系统就没有足够的连续内存空间来分配,导致内存不足
- 如果声明过小,就有可能出现不够用的情况,这时只能再申请一个更大的内存空间,把原数组拷贝过去,非常耗时
- 链表本身没有大小的限制,天然支持动态扩容,这是与数组最大的区别
- 如果程序对内存大小非常敏感,数组会是更优的选择
LRU缓存
- 维护一个有序单链表,越靠近尾部的结点是越早之前访问的,当有一个新的数据被访问时,从链表头开始遍历链表
- 如果此数据之前已经被缓存在链表中,遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部
- 如果此数据没有缓存在链表中,分为两种情况
- 如果此时缓存未满,则将此结点直接插入到链表头部
- 如果此时缓存已满,则将链表尾结点删除,并将新结点插入到链表头部
- 不管缓存有没有满,都需要遍历链表,时间复杂度为
O(n)
技巧
哨兵
插入
单链表中,在结点p后插入一个新节点
1 | // p有可能为null,例如空链表时,p == head == null |
如果要插入第一个结点(空链表),上面代码就不通用了,需要特殊处理,head表示链表头结点
1 | if (head == null) { |
删除
单链表中,删除结点p的后继结点
1 | // p.getNext()有可能为null,例如链表只有一个结点时,p == head |
如果要删除最后一个结点(链表中只有一个结点),上面代码也不通用了,需要特殊处理
1 | if (head.getNext() == null) { |
哨兵
- 针对链表的插入和删除操作,需要对插入第一个节点和删除最后一个结点的情况进行特殊处理,不简洁且容易出错
- 哨兵用于解决边界问题,不直接参与业务逻辑
- 引入哨兵结点(不存储数据),不管链表是不是为空,head指针都会一直指向哨兵结点,有哨兵结点的链表叫作带头链表
- 引入哨兵结点后,可以统一代码实现
边界条件
- 链表为空
- 链表只包含1个结点
- 链表只包含2个结点
- 处理头结点和尾结点
常见链表操作
1 |
|
1 |
|
单链表反转
1 | public void reverse() { |
检测链表中的环
1 | public boolean existRing() { |
合并两个有序链表
1 | public static <T extends Comparable> MyLinkedList<T> merge(MyLinkedList<T> l1, MyLinkedList<T> l2) { |
删除链表倒数第n个结点
1 | public MyLinkedList<T> deleteItemReverse(int n) { |
查找链表的中间结点
1 | public T findMiddle() { |