算法-2.2

算法

这里将第二章的第二节出现的算法进行实现，算法序号和原书中的序号保持一致。

algo-2.3 初始化线性链表

对应的方法是：

1. 顺序表的NewSequenceList方法
2. 链表的的NewSingleLinkedList方法

注意：

1. go是自带GC的强类型静态语言，所以不需要像C语言一样手动分配内存空间
2. 虽然go中也带有数组类型的概念，但是在数组之上又支持了动态数组的切片功能，一般开发中只需要使用切片即可

algo-2.4 线性链表元素的插入

在现有的线性链表中插入新的元素，对应的方法是：

1. 顺序表的InsertByIndex方法
2. 链表的的InsertByIndex方法

注意：

1. 顺序表使用了go中的切片而非数组类型，所以无法直接通过切片来展示新增元素对已有元素的影响，如最坏情况下，可能需要申请新的数组空间，并将原来的数据复制到新的空间中。想要理解具体的做法可以深入研究go中slice的实现，这里不再赘述。
2. 链表的插入动作就体现了该结构的优点，只需要变换指针的指向即可。和顺序表可能最坏的情况相比，链表的插入操作非常的稳定。

algo-2.5 线性链表元素的删除

在现有的线性链表中删除元素，对应的方法是：

1. 顺序表的DeleteByIndex方法
2. 链表的的DeleteByIndex方法

注意：

1. 顺序表使用了go中的切片而非数组类型，所以无法直接通过切片来展示删除元素对已有元素的影响，如最坏情况下，如果删除的是第一个元素，那后续所有的元素都需要向前移动才行。
2. 链表的删除动作就体现了该结构的优点，只需要变换指针的指向即可。和顺序表可能最坏的情况相比，链表的删除操作和插入操作一样非常的稳定。

algo-2.6 查找线性表中的特定元素

在现有的线性链表查找等于某个特定值的元素，对应的方法是：

1. 顺序表的GetElementIndexByValue方法
2. 链表的的GetElementIndexByValue方法

algo-2.7 两个有序线性表在顺序表表示下的合并操作

在上一节已经展示了基于interface的实现，该方法（MergeList(a, b LinearList)）的入参既可以是顺序表，也可以是链表，适用范围更广。

这里要求在顺序表下实现该算法，思路都一样，只需要将代表interface的LinearList直接替换成具体实现的类型SequenceList即可，所以不再赘述。

其他同类文章

• 数据结构 · 算法-2.4
• 数据结构 · 算法-2.3
• 数据结构 · 05-双向链表实现
• 数据结构 · 04-静态链表实现
• 数据结构 · 算法-2.2