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

上面这个示意图是往链表的后方添加元素，接下来是往链表的头部插入元素。该过程也是由关键的两步组成，第一步就是newNode->next = head->next ，第二步是head->next = newNode 。经过这两步我们就可以把元素插入到头结点的后方了。
文章插图
下方这段代码是正向创建链表的具体代码，就是一直往链表的尾部插入元素。逆向创建链表的代码就不往上粘贴了，与下方代码类似， github上会进行完整实例的分享。上面虽然是往头结点和尾部结点的插入，但是原理是适用于往两边中间插入元素的，在此就不做过多赘述了。
文章插图
4.单向链表元素的移除
上面我们聊完元素的插入，接下来我们要聊一下元素的移除。要想移除单向链表中的一个元素，首先我们得找到被移除结点的前驱的位置，比如是pre 。当前移除的元素是remove ，让我我们让pre->next = remove->next, 然后再执行remove->next = nil 。经过上面这些步骤， remove这个结点就与链表脱离关系了。示意图如下所示。
文章插图
根据上述的示意图，我们就可以给出具体的代码实现了。单向链表的核心操作就介绍完了，其他更多细节请参考在github上分享的源代码，因为篇幅有限，关于单向链表的更多细节就不做过多赘述了。
文章插图
四、双向链表
如果你对单向链表已经理解的话，那么理解双向链表来说并非难事。双向链表与单向链表相比多了一个指向前驱的节点。我们暂且称为将指向前驱的节点命名我pre指针。下方这个示意图就是双向链表的示意图，与单向链表相比，多了一个指向前驱的指针域。如下所示。接下来将会给出双向链表的插入和移除。
文章插图
1.双向链表元素的插入
双向链表的插入要比单向链表的插入要复杂一些，不过也是蛮好理解的。下方示意图中就是往节点A后方插入一个节点D 。主要分为四个步骤，第一步是将D节点的next指针指向A节点next指针指向的节点，也就是D->next = A->next 。第二步是将D节点的pre指针指向A节点，也就是D->pre = A 。第三步是将A的next指针指向D ，也就是A->next = D 。最后将D节点的下一个节点的pre指针指向D ，也就是D->next->pre = D 。经过这几步，我们就可以将节点D插入到A与B的中间。当然这个顺序不是一定的，只要能保证链的正确关联即可。
文章插图
下方是上述元素插入的核心代码，如下所示。主要将newItem节点，插入到cursor节点后方。
文章插图
2.双向链表元素的删除
双向链表因为比单向链表多一个前驱指针域，所以元素的删除要麻烦一下，不过还是比较好理解的。下方这个截图就是删除B节点的示意图。首先将B节点前驱节点的next指针域指向B节点的后继，也就是B->pre->next = B->next 。然后将B节点的后继节点的前驱指针指向B的前驱节点，对应着B->next-pre = B->pre 。最后将B的next和pre指针域置为nil 。如下所示：
文章插图
下方代码段就是双向链表移除节点的具体实现，如下所示。至于链表的遍历等其他操作在此就不做过多的赘述了，具体内容请看github上分享的源代码。
文章插图
五、面向接口编程的优点
在上述我们实现两种链表时，我们先定义了一个链表协议ListProtocalType 。无论是双向链表还是单向链表都遵循这个协议，也就是说，该协议就是链表对外统一的接口，该协议就是操作链表的一个规范。下方的testLinkedList()就是我们链表的测试方法，该函数的参数是遵循ListProtocalType协议的所有类的对象。也就是说只要遵循了ListProtocalType这个协议的类的对象，都可以作为该函数的参数。至于具体操作，那么不同的类会给出不同的操作的。
在调用该函数时，第一个传入的是单向链表的类的对象，第二个是双向链表的类的对象。虽然都是执行同一个方法，但是因为传入的类的对象不同，所以执行的结果显然是不同的。这也就是利用了面向对象的多态性，在之前设计模式系列的博客中介绍过，下方这种与策略模式类似。