算法与数据结构线性表的顺序存储与链式存储(Swift版) 接触过数据结构的小伙伴应该

接触过数据结构的小伙伴应该都知道程序 = 数据结构 + 算法。数据结构乃组织组织数据的结构，算法就是对这些结构中的数据进行操作，可见数据结构的重要性，就连算法也是依赖于数据结构的。
在博客的开头，我们先简单的聊些数据结构整体的东西。数据结构整体可以分为物理结构和逻辑结构，物理结构指的是数据在磁盘、内存等硬件上的存储结构，主要包括顺序结构和链式结构。而逻辑结构是数据本身所形成的结构，包括集合结构、线性结构、树形结构以及图形结构。针对不同的数据结构我们可以依据算法解决不同的问题，如我们在以后博客中要介绍的最小生成树，就是根据算法将带权的连通图转换成最小生成树，在转换这个过程中我们就用到了Prim算法和克鲁斯卡尔算法。当然各种排序算法，最短路径等等也是算法与数据结构的结晶体。
一、线性表综述
本篇博客我们主要介绍的是逻辑结构中的线性表，也就是线性结构。线性结构的特点就好比一串珠子，其特点是第一个节点只有一个后继，没有前驱，最后一个节点是只有一个前驱，没有后继。而其余的节点只有一个前驱和一个后继。说罢了线性表就是一串。下方这个图就是线性表的示例图。中间蓝色的节点前方的是就是改点对应的前驱，后边就是改点对应的后继。从下方可以明确看出head没有前驱只有后继，而tail只有前驱没有后继。
文章插图
上面这个是线性表的逻辑结构，接下来我们来聊一下线性表的物理结构，也就是存储结构。线性表的物理结构可分为顺序存储结构和链式存储结构。顺序存储结构之所以称之为顺序存储结构因为每个线性表中节点的内存地址是连续的，而链式存储结构中线性表的节点的内存地址可以是不连续的。这也就是在C语言实现顺序存储线性表时先Malloc一块连续的区域，然后用来顺序的存储线性表。而链表中就可以不是连续的了，前驱与后继间的关系由指针连接。
下方这个指示图中，上面这个就是链式存储，下方这个就是顺序存储。可见链式存储是有指针域的，也就是前驱和后继的关系有指针来链接。下方这个链式存储就是单向链表，因为只有前驱到后继的指针，而没有后继到前驱的指针。关于双向链表下方会具体给出详细的说明。而下面第二个图就是顺序存储，前驱与后继的关系是由紧挨的内存地址所关联。
文章插图
上面这两种存储方式我们可以换另一种更为形象的方式来进行说明，如下所示。顺序存储的内存区块的内存地址是紧挨的，线性关系有相邻的内存地址所保存。当然下方我们是模拟的内存地址，就使用了0x1, 0x2等等来模拟。而链式存储的线性表，在物理存储结构中是不相邻的，仅仅靠内存地址无法去维持这种线性关系。所以就需要一个指针域来指向后继或者前驱节点的内存地址，从而将节点之间进行关联。在单向链式存储中，一个节点不仅仅需要存储数据，而且还要存储该节点下一个节点的内存地址，以便保持这种线性关系。具体请看下图。
文章插图
原理性质的东西先就聊这么多，下面我们会给出具体实现。主要包括线性表的顺序存储及其操作，以及线性表的单链以及双链存储及其操作。下方的实例依然采用Swift面向对象语言实现，思想理解后，用什么语言都是可以的呢。
二、线性表的顺序存储
关于线性表的顺序存储，我们就使用NSMutableArray来实现，也就是使用OC中的可变数组类型来实现。我们就假设其存储的内存地址是连续的，当然数组中存储对象时要复杂得多，我们暂且假设其中的地址是连续的。下方的list就是我们的顺序线性表， count存储的是已经存入到线性表中的元素个数，而capacity则是记录线性表整个容量的大小。当然上述三个属性都是private的，而下方的计算属性length是internal类型的，供外界访问，返回线性表元素的个数。
下方是整体结构，我们下方会给出线性表具体的关键操作，并分析其时间复杂度。
文章插图
1.往顺序线性表中插入数据
有时候我们会给据特定的算法往线性表中指定的位置插入数据，比如我们常见的插入排序算法，如果你的数据是顺序存储的话，那么就需要将数据插入到顺序表中。接下来我们就将数据插入到指定的位置。