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

下方该图中是往顺序表中插入一个元素的原理图。在下图中，我们往AB与CD之间插入一个M 。在插入M之前我们需要做的事情就是将CD整体往后移动一个位置，为M腾出一个位置，然后再将M这个元素进行插入。
文章插图
顺序表的插入还是比较简单的，也是非常好理解的，那么用代码实现起来也是用不了几行代码的。下方截图就是是顺序线性表的元素插入的具体实现的代码。首先检查index的合法性，检查index是否在合理范围内，然后将index后的元素依次往后移动，然后将元素插入即可。
文章插图
2. 顺序线性表的元素移除
上面介绍完元素的插入后，接下来要聊一下元素的移除。也就是移除指定索引中的元素。该过程恰好与上述插入的过程相反，上述在插入之前是相应的元素往后移，腾出index位置。而移除特定索引的元素时，是相应的元素左移，覆盖掉要删除的元素，然后将最后一个元素进行移除掉。下方的原理图对此过程进行了说明。
文章插图
该部分比较简单，下方的代码段就是将指定索引的元素进行移除。在线性表的顺序存储中，前驱和后继的关系由内存地址的先后顺序所关联，所以插入和删除元素会相对麻烦一些，而查找和修改元素就比较简单了，直接由index可以找到相应的元素，再次就不做过多赘述了。 github上所分享的Demo中会有完整示例。
文章插图
三、线性表的单链存储
介绍完线性表的顺序存储，接下来我们来介绍线性表的链式存储。当然，本部分是对单向链表的介绍，下部分将会对双向链表的介绍。下方截图就是我们单向链表相关示例的运行结果，首先我们先正向的创建链表，也就是后来的元素插入到链表的后方。然后在给出逆向创建链表，与正向创建链表相反，后来的元素掺入到头结点的后方。创建链表完毕后，我们会给出链表元素的插入和移除的解决方案。
文章插图
1.单向链表的创建
【算法与数据结构线性表的顺序存储与链式存储(Swift版)】在链表创建之前，我们得先创建节点的类，因为链表是多个节点的连接。下方这个OneDirectionLinkListNote类就是单向链表的节点类。其中的data属性存储的是该节点所存储的数据，而变量next就是指向下一个节点的指针，链表中节点间的关系由next指针所关联。 init和deinit就是该类的构造和析构函数了，就不做过多赘述了。
文章插图
2.链表协议的创建
在创建链表之前，我们可以先创建一个链表协议ListProtocalType 。在ListProtocalType协议中定义了链表所必须的方法，无论是单向链表还是双向链表都要遵循该协议。其实这就是“面向接口”的体现。单向链表与双向链表都遵循了这协议，那么说明这两种链表对外的接口是一致的，这样便于程序的维护，这也是面向接口编程的好处。下方就是我们事先定义好的ListProtocalType协议的部分内容。
下方协议中只给出了方法的定义，未给出具体实现。所有链表都要遵循该协议， ListProtocalType中定义了链表结构所必须的方法。可以说下方这个协议就是链表的大纲。
文章插图
3.单向链表的构建
下方就是我们单向链表类的属性和构造函数。 headNote就是我们链表的头结点，而tailNote是我们链表的尾结点。 length就是我们链表的长度，也就是我们链表中元素的个数。一个空链表中tailNote = headNote 。
文章插图
下方我们将会介绍链表的正向创建和逆向创建。下方这个截图中就是正向创建链表，其实就是将新创建的数据往链表的尾部插入，然后更新一下tail的位置即可。关键步骤就两步，第一步是tail->next = newNode ，第二步是tail = newNode 。插入步骤如下所示：
文章插图