看图轻松理解单向链表

前言

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

单向链表

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

单链表特点

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

单链表创建

创建一个空链表，

image

插入链尾

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

image

连接起来，

image

继续创建“grows”节点，

image

再连接起来，

image

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

image

image

创建迭代器

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

image

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

image

此时的节点值为，

image

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

image

插入节点

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

image

插入到 current 指向位置，

image

执行 next 操作，

image

创建一个"someone"新节点，

image

插入到 current 指向位置，

image

删除节点

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

image

image

删除“someone”节点，

image