线性表按存储方式分为顺序表和链表两种，其中链表又分为单链表，循环链表，双链表，双向循环链表。
顺序表
顺序表采用顺序存储结构，用一段连续的存储单元依次存储线性表的数据元素，对于非空的顺序表，其有着以下特性：
存在唯⼀一的⼀一个被称作”第⼀一个”的数据元素;
存在唯⼀一的⼀一个被称作”最后⼀一个"的数据元素；
除了了第⼀一个之外,结构中的每个数据元素均有⼀一个前驱；
除了了最后⼀一个之外,结构中的每个数据元素都有⼀一个后继。
在使用时类似与OC中的数组，可以用下标来操作。
顺序表的创建
顺序表的创建
插入
顺序表插入
取值和遍历
取值和遍历
删除和清空
删除和清空
链表
链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。相比于顺序表，链表不需要预先分配内存空间，其中一个个元素是一个个结点。
结点
结点
链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。在我看来就是前面是数据，后面是指向链表中下一个结点的指针。
单链表
单链表分为带头结点和不带头结点两种，不管有无头结点，头指针都指向链表的第一个节点（有头结点指向头结点，没有则指向首元结点），其逻辑状态如下图所示：
不带头结点的单链表逻辑状态
带头结点的单链表逻辑状态
后续代码是带头结点的，使用头结点的原因有两个：1.便于首元结点的处理，不需要再额外区分；2.便于空表和非空表的统一处理。
单链表的创建
单链表的创建
插入
单链表的插入
取值和遍历
取值和遍历
删除和清空
删除和清空
不同与顺序表的是，单链表清空和删除时需要释放对应内存空间。
头插法和尾插法创建单链表
面试经常问的应该就是头插法了。
头插法和尾插法
单向循环链表
为了对比，下面的单向循环链表没有加头结点，所以在使用时需要判断是否是首元结点。
单向循环链表逻辑状态
创建
创建
遍历
遍历
插入
插入
删除
删除
查询
查询
双向链表
双向链表结点和逻辑状态
双向链表结点
双向链表逻辑状态
对比单向链表，也就是结点中多了个指向前一个结点的指针prior。所以双向链表可以由一个结点找到前一个结点，而单链表只能找到后续结点。也是因为这点，双向链表可以直接找到对应结点进行操作，而不是找到对应结点的前一个结点（如下面的删除指定元素）。
创建
双向链表创建
插入
双向链表插入
删除
双向链表删除
双向循环链表
双向循环链表逻辑状态
相比于双向链表，双向循环链表头尾相连，所以处理时需要注意修改头结点的prior以及最后一个结点的next。
创建
创建
插入
插入
删除
删除
总结：
顺序表和链表比较
1）当线性表需要频繁查找，较少插入和删除时，宜采用顺序存储结构。若需要频繁插入和删除，宜采用链表。（ps：链表删除和插入时间复杂度是O(1)，指的是查找后，顺序表插入和删除则需要移动空间。）
2）当线性表的元素个数变化较大或不确定时，最好用链表，这样不需要考虑存储空间大小问题。当事先知道线性表的大小长度，用顺序存储结构效率会高一些。
参考资料：
网友评论