线性表
线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。
线性表分为顺序存储结构和 链式存储结构
顺序储存结构：所有元素的内存地址是连续的
使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：
顺序表申请的存储容量；
顺序表的长度，也就是表中存储数据元素的个数；
数组
int[] array = new int[]{11,22,33};
image
很多编程语言中，数组都有一个致命的缺点，无法动态修改容量，
但是实际开发中，我们更希望数组的容量是可以动态改变的，我们可以尝试实际一个动态扩容的数组，
需要注意的几个方法：
int size(); //元素的数量
boolean isEmpty(); // 是否为空
boolean contains(E element); // 是否包含某个元素
void add(E element); // 添加元素到最后面
E get(int index); //返回index位置 对应的元素
E set(int index, E element);//设置index位置的元素
void add(int index, E element); //往index位置添加元素
E remove(int index); //删除index位置对应的元素
int index0f(E element); //查看元素的位置
void clear(); //清除所有元素
链式存储结构：
所有元素的内存地址不一定是连续的
- 单链表
- 静态链表
- 循环链表（单向循环）
- 双向链表
- 双向循环链表
单链表
image
链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素,如上图
链表中每个数据的存储都由以下两部分组成：
数据元素本身，其所在的区域称为数据域；
指向直接后继元素的指针，所在的区域称为指针域；
每个数据我们称之为节点，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，
image
头节点，头指针和首元节点
- 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
- 节点：链表中的节点又细分为头节点、首元节点和其他节点：
- 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
- 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
- 其他节点：链表中其他的节点；
静态链表
也是线性存储结构的一种，它兼顾了顺序表和链表的优点于一身，可以看做是顺序表和链表的升级版。
使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持（和链表类似）。
接着，在将数据存放到数组中时，给各个数据元素配备一个整形变量，此变量用于指明各个元素的直接后继元素所在数组中的位置下标，如图 下图 所示：
image
静态链表中的节点
通过上面的学习我们知道，静态链表存储数据元素也需要自定义数据类型，至少需要包含以下 2 部分信息：
- 数据域：用于存储数据元素的值；
- 游标：其实就是数组下标，表示直接后继元素所在数组中的位置；
静态链表已经逐步被替代，具体内容这里就不在详细描述。
循环链表
可以把链表的两头连接，使其成为了一个环状链表，
image
循环链表和动态链表唯一不同在于它的首尾连接，这也注定了在使用循环链表时，附带最多的操作就是遍历链表。
在遍历的过程中，尤其要注意循环链表虽然首尾相连，但并不表示该链表没有第一个节点和最后一个结点。所以，不要随意改变头指针的指向。
经典的约瑟夫问题就是循环链表的代表
双向链表
双向，指的是各节点之间的逻辑关系是双向的，但通常头指针只设置一个，除非实际情况需要。
image
双向链表中各节点包含以下 3 部分信息
指针域：用于指向当前节点的直接前驱节点；
数据域：用于存储数据元素。
指针域：用于指向当前节点的直接后继节点；
image
双向循环链表
上面我们已经知道了双向链表，和循环链表，相信大家可以很好的理解双向循环链表了，
双向循环链表是单向循环链表的功能扩充，双向循环链表的原理和单向链表很相似：尾节点的next指向链表的头节点。在此基础上，头节点的prev指向尾节点，这样就实现了双向循环链表。同样，为了防止循环引用，尾节点指向头节点要用弱引用。
image
详细代码见 线性表demo-day416
网友评论