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

链表:由浅入深

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

本质

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

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

linked_memory

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

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

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

linked_single

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

linked_tow_way

循环链表与单链表的区别是,它的最后一个节点的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
11
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. 简单粗暴,多看多练。基本上做个每天做个一两道,坚持一星期基本就可以了。

边界问题

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

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

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

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

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

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

哨兵优化

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

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

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

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

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

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
13
// 建立哨兵,新建#节点,并将其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

linked_gurad

经典实例

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

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

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

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

daily_algorithm

推荐

android_startup: 提供一种在应用启动时能够更加简单、高效的方式来初始化组件。开发人员可以使用android-startup来简化启动序列,并显式地设置初始化顺序与组件之间的依赖关系。 与此同时android-startup支持同步与异步等待,并通过有向无环图拓扑排序的方式来保证内部依赖组件的初始化顺序。

AwesomeGithub: 基于Github客户端,纯练习项目,支持组件化开发,支持账户密码与认证登陆。使用Kotlin语言进行开发,项目架构是基于Jetpack&DataBindingMVVM;项目中使用了ArouterRetrofitCoroutineGlideDaggerHilt等流行开源技术。

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

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

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

支持一下
赞赏是一门艺术