盒子
盒子
文章目录
  1. 本质
  2. 插入
  3. 删除
  4. 注意点
    1. 指针的指向问题
    2. 边界问题
    3. 哨兵优化
  5. 经典实例
  6. 项目

链表:由浅入深

今天又到了算法的主题了,上次我们聊到了数组:面试中的疑难点,这次我们来聊另外一种线性结构,链表。

本质

虽然链表与数组一样都是线性结构,但它们之间还是有本质的区别的。

数组在内存中是一块连续的存储区域,而链表可以支持随机存储,非连续的存储空间。

链表的种类可以分为,单链表、双向链表、循环链表、双向循环链表。

它们的本质都是一样的,不同的是具体的表现与应用。

简单来说,对于单链表是每一个节点都有一个next后续指针,它都指向当前节点的下一个链表节点;对于链表的尾节点,由于是链表的最后一个节点,所以它的next为null。


双向链表与单链表所不同的是,它除了有next指针之外,还有prev前驱指针,它指向于当前节点的上一个节点;特殊的,链表的头节点的prev为null。

循环链表与单链表的区别是,它的最后一个节点的next将不再为null,而是指向头节点或者链表的其它位置节点。

而对于双向循环链表也是同样的原理。

插入

我们都听过这么一句话,链表适合插入与删除。

这主要是由于链表自身的数据结构决定的。

对于单链表来说,向已知的一个节点后插入一个新的节点,它所要做的事情就是将当前节点的next指针指向新的节点,然后再将新节点的next指向指向当前节点的之前的后续节点。而这个过程不需要任何数据的迁移,只需改变节点的next指针指向,所以它的时间复杂度为O(1)。

看图很简单,但真正去实现的话,不一定都会,尤其是首次接触到链表的读者。容易犯的是下面这个错误

1
2
node.next = newNode
newNode.next = node.next

犯这个错误的本质绝大多数还是对链表的指针理解不到位。其实对于指针的理解,我们只需记住一点,指针指向的是节点在内存中的地址。改变指针就是改变指向的地址。

正确的做法是下面这种

1
2
newNode.next = node.next
node.next = newNode

当然,为了杜绝这个问题,还有一个简单的方法就是多练,写多了自然就会了。

所谓书读百遍其义自见,应该就是这个道理。

还有上面的时间复杂的是基于一个前提的:已经找到了插入节点的位置。而查找当前插入点,需要通过遍历整个链表的,所以链表中查找一个节点的时间复杂度为O(n)。

可能有的读者一直都有一个疑问,为什么有了单链表还有出来一个双向链表,你看这插入双向链表也是与单链表一样,时间复杂度都为O(1),而双向链表由于它每个节点都额外需要prev前驱节点,导致它更加浪费内存。

针对这类问题,我们将上面的插入位置做一下调整。

现在已知了当前节点的位置,下面需要将新节点插入到当前节点的前面。

如果是单链表,由于只有next指针,所以只能重新遍历链表,找到当前节点的上一个节点,然后再重复上面的转移指针的步骤,此时时间复杂度为O(n)。

而对于双向链表,由于它还有prev执行,所以它可以直接改变prev的指向,来将新节点插入到当前节点的前面,所以它的时间复杂度为O(1)。

正是由于这特性,在实际运用中,双向链表比单链表更加普遍,例如我们所熟悉的LinkedList

1
2
3
4
5
6
7
8
9
10
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

删除

链表的删除与插入原理类似,都是改变节点的指针指向。

对于单链表,如果删除当前节点的后续节点,只需将当前节点的next指针指向当前节点的后续节点的后续节点。文字有点绕,还是直接看代码

1
node.next = node.next.next

而对于双向链表来说,除了改变next节点,还要改变next指向的prev节点。

1
2
node.next = node.next.next
node.next.prev = node

它们的时间复杂度都为O(1)

另外的删除节点为当前节点的前驱节点。这个与插入原理类似,这里就不做详细分析。单链表的时间复杂度为O(n),双向链表的时间复杂度为O(1)。

注意点

现在我们已经对链表有了一个较全面的了解。但开始上手写的时候还是会很容易犯错。

下面我结合自己的一点微薄的经验还对容易犯的错误做一个总结,并对其提出相应的解决方案。

指针的指向问题

首先是写链表时,对于指针的指向错乱问题。

如果遇到简单的插入删除,步骤不是很频繁的情况,相信大家都能够很容易的完成。一旦涉及到链表的指针频繁改变,亦或者是双向链表(再加一个前驱指针),这时犯错率就会直线提升。

对于这种问题,我给出的解决方案是:

  1. 放下心来仔细思考,理清整个过程,再动手写代码。
  2. 借助辅助工具,例如停下手来,找只笔找张纸,把链表的结构画出来,然后在画它们间的指针指向。
  3. 简单粗暴,多看多练。基本上做个每天做个一两道,坚持一星期基本就可以了。

边界问题

在写链表的过程中,还有一种情况就是对边界的处理。

可能是忘了对边界的处理;也可能是直接处理错误。

对于链表的边界就是它的头节点与尾节点。由于它们的特殊性,针对它们的插入与删除,可能与别的节点不同,需要额外进行特殊处理。

针对这种问题,我们需要做的就是,写完链表之后,时刻都要提醒自己是否对边界做了处理,如果做了也要停下来思考一遍是否处理正确。

这样就能很好的保证边界处理的正确性。

千万不要偷懒,别因为这个边界问题导致在面试过程中的评分打折扣。因为这能从侧面体现一个人的思维的全面与缜密性。

哨兵优化

针对上面的边界问题,有没有代码上的优化呢?

有的,这里要说的就是哨兵优化。

所谓的哨兵,简单的理解就是固定一个标识,让它像边界的士兵一样,一直屹立在他的边界岗位,守卫国土的安全。

例如,我们拿上面的双向链表的删除来说。

对于非头节点的删除,我们只需找到当前的节点,然后改变它前后节点的next与prev指针的指向即可

1
2
node.prev.next = node.next
node.next.prev = node.prev

现在如果当前节点是头节点,上面的代码就不能运行,因为头节点的prev节点为null,所以常规的做法是做特殊判断

1
2
3
if (node == head) {
node.next.prev = null
}

这样就是边界问题的处理,如果你记得处理那还好,一旦忘了就导致异常。

而使用哨兵就能够完全规避边界的判断,我们来看具体使用方式

1
2
3
4
5
6
7
8
9
10
11
12
// 建立哨兵,新建#节点,并将其next指针指向头节点
val guard = LinkedNode("#")
val newLinked = guard.next = head
head.prev = guard

...

// 节点删除(包括头节点)
node.prev.next = node.next
node.next.prev = node.prev
// 返回删除后的链表
return newLinked.next

经典实例

下面是一些关于链表的经典的实例,如果对链表还不熟悉的推荐亲自去写一遍。

写完之后你将对链表有一个全新的认识。

  1. 环的检测
  2. 单链表反转
  3. 删除链表倒数第n个结点
  4. LRU
  5. 求链表的中间结点
  6. 两个有序链表的合并
  7. 单链表判断回文

我这里也提供了全部的源码,kotlin与java都有,希望对你有所帮助。

daily_algorithm

项目

android_startup: 提供一种在应用启动时能够更加简单、高效的方式来初始化组件,优化启动速度。不仅支持Jetpack App Startup的全部功能,还提供额外的同步与异步等待、线程控制与多进程支持等功能。

AwesomeGithub: 基于Github的客户端,纯练习项目,支持组件化开发,支持账户密码与认证登陆。使用Kotlin语言进行开发,项目架构是基于JetPack&DataBinding的MVVM;项目中使用了Arouter、Retrofit、Coroutine、Glide、Dagger与Hilt等流行开源技术。

flutter_github: 基于Flutter的跨平台版本Github客户端,与AwesomeGithub相对应。

android-api-analysis: 结合详细的Demo来全面解析Android相关的知识点, 帮助读者能够更快的掌握与理解所阐述的要点。

daily_algorithm: 每日一算法,由浅入深,欢迎加入一起共勉。

支持一下
赞赏是一门艺术