数据结构是指计算机组织和存储数据的方式，不同的数据结构的特点影响着数据相关操作的效率。

线性数据结构是指元素之间的关系是一对一的。线性数据结构有栈，队列，双队列，数组，链表，串。

一、数组

数组是一种典型的顺序存储线性结构并且大小固定，其中元素都具有相同类型，数组在内存中是以一种连续的空间进行存储的，也就是说数组中的元素在内存空间中是两两相邻的，所以已知第一个元素的位置，其他元素的位置都可以通过位序推算出来，也就是数组索引角标的由来。

数组的结构特点及对应操作效率：

插入操作：由于数组的内存位置固定，插入数据需要移动数据，除非是在数组末端最快，插在数组始端最慢。平局需要移动半数的元素，时间复杂度位O(n)。

删除操作：与插入操作一样，时间复杂度均为O(n)。

查询操作：由于有数组角标的出现，可以很快通过角标直接查询元素，查询操作的时间复杂度O(1)。

修改操作：与查询操作一样，时间复杂度均为O(1)。

二、链表

链表：是在物理结构上不连续，但是逻辑结构上连续的数据结构，相对实现复杂，链表中的元素不单单储存了数据，也储存了下一个元素的物理地址，所以这就不要求元素存储在连续的物理位置上，也就不需要固定链表的大小，可以动态扩展规模。

链表的结构特点及对应操作效率：

插入操作：由于链表内存储了下个元素的地址，所以插入操作只需修改要插入位置的上一个元素和要插入元素中的存储下一个元素的地址,不需要移动数据，时间复杂度位O(1)。

删除操作：与插入操作一样，时间复杂度均为O(1)。

查询操作：由于链表并不像数组一样可以通过角标直接获取，而是通过存储的下一个元素的物理地址迭代查询，查询操作的时间复杂度O(n)。

修改操作：与查询操作一样，时间复杂度均为O(n)。

链表解决了数组缺陷的两个问题：第一个就是数组必须是连续空间且大小固定的问题，第二个就是解决数组插入删除效率低得问题。解决问题的同时创建了一个问题：查询效率低下。

在链表的基础上，又有一些新的链表结构产生：双向链表，它解决了链表查询效率极为低下的一种情况，就是逆序查找，由于链表只存储了下一个元素的地址，所以你想往回查找元素，是不可能的。所以双向链表在存储时，不仅要存储下一个元素的物理地址，还存储了上一个元素的地址，对于插入删除操作来说，只是多修改个地址值罢了，效率基本没有下降，但是查询却可以进行逆序查找，增加了查询效率。

还有一种链表结构叫做循环链表，它只是将链表的首位相连，从而可以实现任意节点的可达性，它的优点在于不需要任何内存的额外开销。它的产生主要解决了一些逻辑问题，比如约瑟夫问题。

三、栈

栈：是一种先入后出的数据结构，他可以基于上述两种线性结构进行实现，栈只是对数据操作进行了特定限制，并不是一种新的数据存储模型。栈的插入删除操作限定只在栈顶操作。

四、队列

队列：是一种先入先出的数据结构，他可以基于上述两种线性结构进行实现，队列只是对数据操作进行了特定限制，并不是一种新的数据存储模型。队列的插入操作限定只在队尾操作，删除操作要在队首进行。

五、散列表（哈希表）

散列表：根据关键值直接访问数据的结构。将关键值通过映射函数映射到数据的存储地址，达到根据关键值直接结算数据地址并且访问的目的，散列表有一个问题是不可避免的，就是映射函数计算出来的存储地址可能重复，那么这种地址冲突如何解决？再散列法，可以是不同的映射函数，也可以是同一映射函数不停递归。链地址法，将冲突元素用链表串联起来。公共溢出法，将冲突的元素全部放入公共溢出区。