【Day3】[资料结构]-链结串列Linked List

链结串列(Linked List)常用来处理相同类型资料，在不连续的记忆体位置，以随机的方式储存，由於不用事先宣告一块连续记忆体空间，所以较不会造成记忆体的浪费。

由许多节点组成，每个节点包含资料栏与指标栏，指标栏会指向下一个资料所在的记忆体位置。因此再追加或删除资料相当方便，因为只需要更动指标的指向，但在读取资料就会较费时，因为必须从串列的头开始寻找。

可以想像一辆火车，透过挂勾将车厢一节一节地串起来，能够依乘客需求多寡来使用挂勾更动车厢数量。

单向链结串列Singly Linked List

基本的链结串列结构，从串列头(Head)开始依序指向下一笔资料，串列尾(Tail)为最後一笔资料指向空值(Null)。

追加资料的步骤

只需要更动指标的指向。

双向链结串列Doubly Linked List

每个节点会变成一个资料栏与两个指标栏，让资料可以从头或尾巴开始找，优点是可以让被破坏或遗失的节点被找回来，但在追加或删除资料时，必须更动比单向链结串列更多的指标次数。

环狀链结串列 Circular Linked List

在单向链结串列中，万一某节点被破坏或遗失，整个串列将会没作用，因此如果把串列最後一个节点指向串列头，这样每个节点都可以是串列头。

阵列与链结串列的优缺点比较

阵列的介绍可以参考此篇