什么是线性表：
零个或者多个数据元素的有限序列，这些定义就简单的说下就行了，相信大家都能明白，然而我要说的是线性表的几种存储结构
顺序存储结构 （大家都明白，不做赘述）
大家常用的就是顺序存储结构，例如一个数组，或者java中的 ArrayList
优点：
1 无需为表中元素之间的逻辑关系而增加额外的存储空间
2 可以快速的存取表中的任一位置的元素
缺点：
1 插入和删除元素操作需要移动大量的元素
2 当线性表的长度变化较大时，难以确定存储空间的容量
3 造成存储空间的碎片
链式存储结构
为了解决插入操作和删除操作带来的巨大消耗，对于需要频繁增加删除的线性存储结构推荐使用链表,相对于一段连续的存储区域,链表结构通过：前一个元素保存后一个元素的指针（引用）的方式产生松散的数据存储结构，保证内存的有效利用，而且减少了插入删除带来的内存消耗。
单链表：
单链表相比于顺序线性表的顺序存储结构而言，多了一个指向后继数据元素的指针（或者持有后继元素的引用），当其后继元素没有时（处于表尾）后继指针指向空。看下边：
public class LinkedListItem<T> {
public T data; ／／内容
public LinkedListItem<T> cur; ／／后继元素的引用
}
单链表的整表创建：
1 使用让新的节点在第一位置，这种算法简称：头插法。
2 反之每次新结点都插在终端结点的后面，这种算法简称：尾插法。
静态链表：
相比于普通单链表这种松散的存储结构，想要对存储结构的长度进行限制以及对已经删除了的元素所占用的空间加以利用，普通单链表是难以做到的。然而静态链表则建立在一块连续的存储存储地址上（或者是数组中）
为了明白什么是静态链表我们先要知道静态链表的几个设计：
1 数组第一个和最后一个元素作为特殊元素处理，／／不存数据
2 我们把未使用的数据元素称为备用链表
3 数组的第一个元素，即下标为0的元素的cur只存放备用链表的第一个结点的下标
4 数组的最后一个元素的cur则存放第一个有数值的元素的下标（想要知道第一个存放数据的元素在哪里必须访问数组的尾结点）相当于头结点的作用。
什么是静态链表：
1 第一个元素嫉妒空闲空间的第一个元素的下标。
2 每个元素（除了数组的第一个元素和最后一个元素不存数据作为特殊元素处理）持有下一个元素的下标（引用）——这是链表的共性
3 数据元素的下一个位置数据为null时，则其持有的下标为0.因此 该元素表示数据元素的尾结点。
4 数组最后一个元素的cur用来存放第一个插入元素的下标
概念摘出：
第一个元素：无视有无数据，数组的第一个元素
每个元素： 无视有无数据，数组中的每个元素
数据元素：存放有数据的元素
数组最后一个元素：无视有无数据，数组的最后一个元素。
循环链表
将单链表中终端结点的指针端由空指针指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
双向链表
双向链表是在单链表的每个结点中，再设置一个指向前驱结点的指针域
网友评论