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

单向链表

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

单链表特点

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

单链表创建

创建一个空链表，

插入链尾

将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”节点，