Aloha！又是我少女人妻 Uerica ，今天中秋节大家吃肉了吗！传说中后羿的狗狗偷吃了嫦娥吃剩的灵药，就跟嫦娥一样一起飞到月亮上，然後把嫦娥跟月亮都吃掉了！恩...狗狗这麽贪吃也合理啦。

连结串列 (Linked List)

好的～今天要来聊一下链结串列在记忆体中是如何储存资料的吧！连结串列与阵列 (Array) 一样是线性资料结构，但一般的程序语言在宣告阵列时，需要先规定记忆体储存空间的大小（阵列长度），所以如果不知道资料会增长到多大，常常会碰到不知道如何规定资料大小，或是记忆体预留过多空间，造成空间浪费等情况，此部份在介绍阵列的资料结构会有更详细的说明。但 JavaScript 所提供的阵列方法并没有一般语言来得严谨，原因是底层作用不太一样，这部分之後再写一篇与大家说明瞜～

连结串列定义与特性

连结串列是由多个节点 (node) 所组成，节点之间会用指标 (pointer) 来做连结，所谓的指标就是纪录指向的另一个节点在记忆体中的位置，如果没有下一个节点则为 null。而每个节点中会纪录需要被存取的资料元素。

节点 (node) 中存取的资料：

• 资料元素 (：需要被存取的一笔资料
• 指标：指向的节点在记忆体中的位置

而连结串列的特性是便於插入或删除节点，但在存取数据时，一笔资料元素的存取会占较多记忆体空间也较为费时。不过因为拥有指标，所以不用像阵列一样连续式的储存在记忆体内，而是可以分散在不同地方。

• 优点
  • 便於资料元素插入、删除
  • 非占用连续记忆体空间，无须先定义资料大小与长度
• 缺点
  • 由於节点是被分散在记忆体各个角落，且要依照指标才能找到下一个节点，所以只能用顺序存取 (sequential access) 的方式。
  • 在增加一个资料元素时，因除了写入资料元素在节点外还需要写入指向的指标，所以增加一个节点比起阵列单纯增加资料元素占较多记忆体空间。

连结串列是由一连串结点所组成

实际在记忆体中会是这个样子，无需连续储存

常见的基本操作

插入新节点

连结串列若要插入新节点(如图示的 Node New 要插入 Node A 与 Node B 之间)，只需改变 Node A 指标指向的位置，以及在 Node New 写入Node B 位置即可。

将 Node New 插入 Node A 与 Node B 之间

只需改写或增加下一个 node 的位置

删除节点

承上图，假设现在我们要删除 Node B ，则将 Node New 的指标指向 Node C 的位置即可。

此时 Node B 已无法存取，可删除或持续保留在记忆体中，这边也可发现若有两个 Node 指向同一个 Node 是可行的，这也是连结串列中资料可共享的优势。

连结串列类型

单向连结串列（Singly Linked List)

单向连结串列，也是最基本的连结串列，每个节点的指标指向下一个节点，存取时只能使用顺序存取的方式从头开始依序往下读取。

双向连结串列（Doubly Linked List）

双向连结串列与单向不同的是，每个节点都有指向上一个节点与下一个节点的指标，所以在存取时可从任一节点开始。

回圈连结串列（Circularly Linked List）

回圈连结串列与双向连结串列类似，但回圈连结串列头尾节点的指标会再指向对方并连成一个环。

关於连结串列的时间复杂度

由於连结串列属於线性关系，所以在资料存取需要 O(n) 的时间复杂度，不过插入与删除通常只需要 O(1) 的时间复杂度。

参考资料：

Linked list Javascript实作及Leet code题目解析

JavaScript 学演算法（五）- 链结串列 Linked list

维基百科 - 连结串列

资料结构: Pointer 指标与Link-link实作 youtube影片

感谢各位阅读！最近写文章很少陪狗狗玩，再不带她出门遛遛我可能也会被吃了！哈哈哈哈，明天见啦掰掰～