线性表

最近听了这么一段话，说武侠小说里少林寺的和尚们，在入寺时，并不会被授予易筋经、降龙十八掌等武功秘籍，而是给一个菜园，挑水，植菜，养猪，为什么呢？武功有招式和心法之分，招式建立与心法之上，内功深厚，招式才游刃有余。如今的 Android，iOS，Web 开发，说白了就是招式，招式可以千变外化，如果一味的追求招式，忽视内功的话，结果就像天龙八部里的鸠摩智，技术领略的内功修炼，数据结构和算法是很重要的一部分，所以我打算写几篇博客理一下数据结构。

先来看一张图，了解下线性表的概念

a1 是 a2 的前驱，a(i+1) 是 a(i) 的后继，a1 没有前驱，a(n) 没有后继；
n 为线性表的长度，若 n = 0，线性表为空表。

线性表有两种存储方式：顺序存储 和 链式存储

顺序存储

顺序存储本质上是一组地址连续的存储单元，使用数组实现，数组的大小需指定或者动态分配。

顺序存储需要预分配一定的空间，后期空间不够可动态添加；

优点：查找快，O(1)的时间复杂度

缺点：插入删除慢，需要移动大量元素（想象食堂排队），O(n)的时间复杂度

链式存储

线性表的链式存储有三种：单链表、循环链表、双向循环链表。

链式存储的特点就是可以用任意的存储单元来存储线性表的数据元素，即存储单元可以连续，可以不连续。

将单链表中的终端结点的指针端由空指针改为向头结点，使得整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表。

在单循环链表的基础上，为每一个元素添加一个指向其前驱结点的指针域，就形成了一个双向循环链表。

链式存储不需要分配空间，存储元素个数也不限制；

链表的优点：插入和删除效率高，O(1)的时间复杂度

缺点：查找效率低，O(n)的时间复杂度