数据结构与算法--线性表(二)

在概述一节中，介绍过数据结果会根据逻辑关系，有一个逻辑分类，分别是：集合结构、线性结构、树结构、图结构；

所谓的线性结构就是结构内的元素之间具有”一对一“逻辑关系。这种数据结构的最佳存储方式也是线性结构的存储。这种方式是"线性表"。

线性表定义

线性表（线性存储结构），使用线性表存储数据的方式可以这样理解，即"元素之间首尾顺序链接、如排列的队伍或一根绳索"。

线性表分类

线性表根据元素之间首尾相连的方式，在内存中的具体实现形式，可分为两类：

1.顺序存储结构（顺序表）
2.链式存储结构（链表）

顺序表

该种形式在数据存储时，会提前申请一整块足够大小的且连续的物理空间，然后将数据依次存储起来，前后元素之间无空隙。

所以顺序表，知道起始位置地址，和顺序表的容量或长度即可遍历所有元素。

链表

与顺序表不同，链表不会申请连续且固定的物理空间。链表存储的数据元素，在物理空间的地址是随机的、非连续的。各元素之间靠一个地址指针来关联链接。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

根据链表内元素之间的链接方式，链表又可分类为：
1.单向链表
2.双向链表
3.循环链表。

操作特点

顺序表

1.插入操作：顺序表插入的时候，时间复杂度O(n)，即直接在尾部插入即可。
2.查找操作：顺序表查找的时候，取决于顺序表元素是否有序，如果有序时间复杂度O(1)，如果无序时间负责度O(logn)(二分查找)

链表

1.插入操作：链表在插入(尾部)的时候可以达到O(1)的复杂度
2.查找操作：查找一个节点或者访问特定编号的节点则需要O(n)的时间，每次都需要从头开始遍历。

结构特点

顺序表

1.优点：有序空间，随机读取，元素之间无序额外地址空间链接。
2.缺点：容量固定，需要提前申请固定容量的地址空间。

链表

1.优点：容量不固定，随机内存动态增加删除。
2.缺点：必须顺序读取，无法随机读取元素，每个元素需要额外的地址指针域，空间开销变大。

线性表常见数据结构

1.队列
2.栈
3.链表（单向链表、双向链表、环形链表）
4.字符串
5.数组推广