看图轻松理解数据结构与算法系列(单向链表)

时间:2024-03-31 13:18:24

前言

推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。

单向链表

单向链表属于链表的一种,也叫单链表,单向即是说它的链接方向是单向的,它由若干个节点组成,每个节点都包含下一个节点的指针。

单链表特点

  • 创建单链表时无需指定链表的长度,这个比起数组结构更加有优势,而数组纵使实现成动态数组也是需要指定一个更大的数组长度,而且要把原来的数组元素一个个复制到新数组中。
  • 单链表中的节点删除操作很方便,它可以直接改变指针指向来实现删除操作,而某些场景下数组的删除会导致移动剩下的元素。
  • 单链表中的元素访问需要通过顺序访问,即要通过遍历的方式来寻找元素,而数组则可以使用随机访问,这点算是单链表的缺点。

单链表创建

创建一个空链表,

看图轻松理解数据结构与算法系列(单向链表)

插入链尾

nobody grows old merely by a number of years这些单词按顺序分别插入尾部,创建“nobody”节点,

看图轻松理解数据结构与算法系列(单向链表)

连接起来,

看图轻松理解数据结构与算法系列(单向链表)

继续创建“grows”节点,

看图轻松理解数据结构与算法系列(单向链表)

再连接起来,

看图轻松理解数据结构与算法系列(单向链表)

以此类推,将剩下的分别创建节点并连接起来。

看图轻松理解数据结构与算法系列(单向链表)

看图轻松理解数据结构与算法系列(单向链表)

创建迭代器

迭代器的 current 指针初始指向head,

看图轻松理解数据结构与算法系列(单向链表)

执行两次 next 操作, current 指针指向索引为2的节点,

看图轻松理解数据结构与算法系列(单向链表)

此时的节点值为,

看图轻松理解数据结构与算法系列(单向链表)

设置 current 指针指向索引为4的节点,

看图轻松理解数据结构与算法系列(单向链表)

插入节点

在索引1后面插入“but”和“someone”两个节点。先将 current 指针指向索引为1的节点,创建一个”but”新节点,

看图轻松理解数据结构与算法系列(单向链表)

插入到 current 指向位置,

看图轻松理解数据结构与算法系列(单向链表)

执行 next 操作,

看图轻松理解数据结构与算法系列(单向链表)

创建一个”someone”新节点,

看图轻松理解数据结构与算法系列(单向链表)

插入到 current 指向位置,

看图轻松理解数据结构与算法系列(单向链表)

删除节点

将“but”和“someone”两个节点删除,先删除“but”节点,

看图轻松理解数据结构与算法系列(单向链表)

看图轻松理解数据结构与算法系列(单向链表)

删除“someone”节点,

看图轻松理解数据结构与算法系列(单向链表)

看图轻松理解数据结构与算法系列(单向链表)

————-推荐阅读————

我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、mysql协议、chatbot)

为什么写《Tomcat内核设计剖析》

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇


跟我交流,向我提问:

看图轻松理解数据结构与算法系列(单向链表)

欢迎关注:

看图轻松理解数据结构与算法系列(单向链表)