[Day06]程序菜鸟自学C++资料结构演算法 – 常见的线性串列其一：链结串列Linked List

前言：讨论完阵列之後接着就要来看看它的好兄弟链结串列Linked List，在Day03的文章中有提到阵列是属於静态资料结构，而链结串列则是属於动态资料结构，接下来就解释一下动态资料结构的特点。

链结串列(动态资料结构)的特性：

1. 是一种将线性串列的资料使用不連续记忆空间來储存。
2. 优点是资料的插入或删除都相当方便，不需要移动大量资料。
3. 记忆体配置是在执行时才发生，所以不需事先宣告，能够充份节省记忆体空间。
4. 缺点就是设计资料结构时较为麻烦，另外在搜寻资料时，也无法像静态资料一般可随机讀取资料，必须循序找到该资料为止。

看起来很难理解，那生活中有没有甚麽相似的实物？

图片来源：https://img.pcstore.com.tw/~prod/M17326047/_sE_5938373233.jpg?pimg=static&P=1400414726
活页笔记本的便利之处想必大家都非常清楚，这种笔记本不管是在新增或移除叶面都相当方便，但如果没有标上页数，在寻找想要的内容之前是不是都得把笔记本都翻过一遍？
活页笔记本是否和连结串列有异曲同工之处呢？或着是可以加减车厢的捷运也是一样的道理喔！

单向链结串列：

再来就是比较专门的知识了，链结串列还能再细分成单向、双向和环状三种，先来看看单向链结串列。

1. 第一个节点又被称作头节点
2. 每个节点都有资料和指标
3. 只能透过指标寻访下一笔节点的资料(只能同一方向)
4. 最後一个节点的指标不指向任何地方(标示为Null)，表示串列的尽头。

删除节点：只要把A原本指向B的指标改为C，再把B节点删除就完成了。

新增节点：假设新增一E节点再AB之间，把A的指标指向E，再把E的指标指向B就可以罗，是不是比阵列简单很多！

双向链结串列：

进入到下一个双向链结串列，不过其实只是依样画葫芦，只要多增加向前一个节点的指标就可以了喔！

一个节点就包含两个指标(前後)和资料，双向链结串列也有能快速修补脱落节点的妙用！

环状链结串列：

终於到了最後的环状链结串列，只要把最後一个节点指向第一个节点就可以了。

今日小结：今天介绍完了链结串列，明天就要来实作练习了，双向和环状链结串列的新增和删除跟单向链结串列都大同小异，只要更动指标的指向的节点，有兴趣的人可以练习看看(≧▽≦)