线性表

导言： 算法特性：有穷性、确定性、可行性、输入、输出。时间复杂度：T(n) = O(f(n))、空间复杂度：S(n) = O(f(n))

定义

若干个数据元素的有限序列。个人觉得可以类比Objective-C中的NSArray（有索引）、NSSet（无索引），对比理解就好。

线性表的顺序实现就是存储地址连续，好比NSArray（随机存储特性）。链式实现其实就是每个节点保存自己数据的同时，保留了相邻节点的指针。

顺序实现的线性表：

随机存储（因为逻辑相邻的两个数据元素的物理地址也相邻），因为知道了首个数据元素的地址，所以每一个元素的地址都知道了，直接根据地址取任意一个元素（T(n) = O(1)）。对于，顺序实现的线性表，增删查检中比较吃亏的是插入和删除。（在第i 个元素后插入一个新的元素或者删除第i个元素，i后面的所有元素均需要移动位置，T(n) = O(n)）

链式实现的线性表：

无法随机存储（因为逻辑相邻的两个数据元素的物理地址不相邻），查找必须遍历链表T(n) = O(n)。在第i 个节点之前插入一个新的节点，必须先查找到第i-1个节点T(n) = O(n)，然后再插入T(n) = O(1),所以插入删除的T(n) = O(n)。

双向链表对比于单向链表，在已知第i个数据元素的前提下，查找下一个元素，时间复杂度都是O(1)，但是查找上一个数据元素单向的时间复杂度是O(n)，因为没有指向上一个数据元素的指针，必须遍历链表，找到指针指向自己的元素。对于双向就不一样，它存有上一个数据元素的指针。

合并：

无序：

两个线性表LA、LB合并（不能含有相同元素）｜T(n) = O(n^2)

如果采用快速排序先对数组进行排序 ｜ T(n) = O(n*log(n))

有序：

两个线性表LA、LB合并（不能含有相同元素）｜T(n) = O(2n)

个人总结：

常规的线性表（顺序实现、链式实现）多用来存储数据，在Objective-C中对应的NSArray就是如此。不过链式实现也提供了一些思路：比如责任链的设计模式（双向链表）。终归到底，还是看个人把问题转换为什么数据结构去处理，P = (C , R)这个表达式很重要。

注：上述总结纯属本人对数据结构扫盲的总结，不对之处希望指正。