基础概念
数据结构的分类
在数据结构中，按照不同的角度，数据结构分为逻辑结构和物理结构（存储结构）。
逻辑结构：指的是我们面对的数据对象中数据元素之间的相互关系。
物理结构：数据的逻辑结构在计算机中的存储形式。
逻辑结构又可以细分为4种更加具体的结构，如下图：
集合结构
线性结构
树形结构
图形结构
从上面的四幅图片，可以很容易理解这4种常用的逻辑结构。
数据的物理结构又分为2种类型
顺序存储结构：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和存储关系是一致的。
链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元的结构是随机的。
综上，数据结构分类可以归结如下
- 逻辑结构
- 集合结构
- 线性结构（一对一）
- 树形结构（一对多）
- 图形结构（多对多）
- 物理结构
- 顺序存储（占用连续的存储空间）
- 链式存储（占用非连续的存储空间）
抽象数据类型ADT
抽象数据类型（Abstract Data Type）ADT。
抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
抽象数据类型描述的一般形式如下：
ADT 抽象数据类型名称 {
数据对象：
……
数据关系：
……
操作集合：
操作名1：
……
……
操作名n：
}ADT抽象数据类型名称
ADT,不只是包括元素结合的定义，还包括操作集合。
如何使用数据的物理结构正确而又高效的反映数据元素的逻辑结构，实现其抽象数据类型，就是数据结构要完成的工作
线性表
线性表:零或多个数据元素的有限序列。其中，除了第一个元素之外，每一个元素有且只有一个直接前驱元素，除了最后一个元素之外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
线性表 抽象数据类型(ADT)
线性表的顺序存储结构实现
线性表的顺序存储结构，典型的可以用一维数组实现，线性表查找、添加和删除元素的实现。
下面是用数组实现的线性表抽象操作集合中的查找，添加 和删除算法。
public class LinearStructTest {
//线性表的长度
private static int length;
public static void main(String[] args) {
int[] data = new int[30];
//在线性表的某个位置插入元素
dataInsert(data, 1, 101);
dataInsert(data, 2, 102);
dataInsert(data, 3, 103);
dataInsert(data, 4, 104);
dataInsert(data, 5, 105);
dataInsert(data, 6, 106);
dataInsert(data, 3, 1003);
dataInsert(data, 4, 1004);
dataDel(data, 1);
dataDel(data, 5);
System.out.println("after insert :");
for (int e : data) {
System.out.print(e + " ");
}
System.out.println("");
//获取某个位置的数据元素
int a = getData(data, 5);
System.out.println("the element at pos=5 is " + a);
System.out.println("\nthe length =" + length);
}
/**
* 删除位置pos的元素,这里的pos 不是数组下标，而是正常自然位置
*
* @param data
* @param pos
*/
private static boolean dataDel(int[] data, int pos) {
//线性表位空
if (length == 0) {
return false;
}
//
if (pos < 1 || pos > length) {
return false;
}
if (pos < length - 1) {
for (int m = pos; m < length; m++) {
data[m - 1] = data[m];
}
}
length--;
return true;
}
/**
* 将新元素e插入到数组data的第i个位置之前
*
* @param data
* @param pos
* @param e
* @return
*/
private static boolean dataInsert(int[] data, int pos, int e) {
//线性表已满
if (length == data.length) {
return false;
}
//位置越界
if (pos < 1 || pos > length + 1) {
return false;
}
if (pos <= length) {
//从pos-1 位置的元素都往后移动
for (int m = length - 1; m >= pos - 1; m--) {
data[m + 1] = data[m];
}
}
data[pos - 1] = e;
length++;
return true;
}
/**
* 获取线性表中第i个位置的元素
* @param data
* @param i
* @return
*/
private static int getData(int[] data, int i) {
//线性表为空，或者位置越界返回-1
if (length == 0 || i < 1 || i > length) {
return -1;
}
return data[i - 1];
}
}
从以上代码，可以看出，对于顺序存储结构的线性表，由于数组具有随机存取的特性，因此，在其中查找某个特定位置元素是很容易实现的，其时间复杂度为O(1),而对于添加或删除元素的操作，则需要移动大量的元素实现，时间复杂度为O(N)。
对于以上线性存储结构中不易增删的缺点，可以考虑使用下面链式存储结构的。
线性表的链式存储结构实现
在链式存储结构中，为了维持线性表的特性；对于每一个元素来说，除了存储本身的信息之外，还需要存储其直接后继元素的存储位置；我们把存储数据信息的域称为数据域，把存储直接后继位置的域称为指针域。这样的一个存储区域称为结点（Node）。
链式结构，顾名思义，就是在计算机内容中，存储数据的内存空间不再是连续的，而是随机的在各个位置，而这些位置通过一个特定的东西（指针）连接起来；这样的一种物理结构就是链式结构。
为了更有效率的用链式结构实现数据的逻辑结构，链表结构又分为以下几种情况。
单链表
n 个结点链结成为一个链表，即为线性表的链式存储结构，也叫做单链表。
- 头指针：链表中第一个结点的存储位置，如果存在头结点，那么头指针指向头结点。
- 头结点： 单链表第一个结点之前的结点；其数据域可以存储任何信息，指针域存储的是指向第一个结点的指针，
- 单链表的最后一个结点的指针域为NULL
- 如果单链表为空，则头结点的指针域为NULL.
循环链表
在单链表中，最后一个结点的指针域为NULL,因此到了最后一个结点，就没有办法在访问链表中其他结点了。因此，我们将单链表中最后一个结点的指针域由NULL改为指向头结点，这样就使单链表形成一个环，这种头尾相连接的单链表称为单循环链表，简称循环链表。
在循环链表中，为了统一方便的访问链表中的每一个元素，不再使用头结点，而是尾节点，一个指向链表中最后一个元素的结点，如图所示。
双向链表
无论是单链表还是循环链表的存储结构，由于每一个结点只存储了其直接后继结点的位置，这个时候如果要访问其直接前驱结点是非常困难的，在单循环链表中为了实现这样的操作，需要把整个链表遍历一遍，这是非常糟糕的。因此，我们很容易想到，既然这样，为每个节点添加一个存储区域，把直接前驱结点的位置存下来不就好了吗，是的，这就是双向链表 。
再结合循环链表的优点，我们就可以定义一种更加普适的链表结构，双循环链表。
对比图单链表可以看出，双循环链表的结构较之虽然看着貌似复杂了很多，但是总的来说只是多了一个指针域而已，从而使得链表中相邻节点的访问变得更加容易。
双向循环链表为空时的结构
下面就看看看，如何使用双循环链表实现线性表的抽象数据类型。
带前驱、后继指针的结点DNode
/**
*
* 结点对象
*/
class DNode<T> {
DNode prev,next;
T value;
DNode(){
this(null, null, null);
}
private DNode(DNode prev, DNode next, T value) {
this.prev = prev;
this.next = next;
this.value = value;
}
}
双向循环链表抽象数据操作集合
/**
*
* 双向循环链表
*/
class DoubleLoopLink<T> {
//头结点
private DNode<T> mHead;
//节点个数
private int mCount;
/**
* 初始化线性表
*/
DoubleLoopLink() {
//初始化头结点
mHead = new DNode<>();
//创建一个空的循环链表，头结点的前驱、后继指针都指向自己
mHead.prev = mHead;
mHead.next = mHead;
//结点个数
mCount = 0;
}
/**
* 返回线性表元素个数
* @return
*/
int size() {
return mCount;
}
/**
* 获得线性表某个结点
* @param index index 范围（0~mCount-1)
* @return
*/
DNode getNode(int index) {
//位置越界
if (index < 0 || index >= mCount) {
throw new IndexOutOfBoundsException();
}
DNode mNode;
// 比较一下查找位置和结点个数的关系，优化查找区间
if (index < mCount / 2) {
//指向头结点的后继结点，顺时针查找
mNode = mHead.next;
for (int i = 0; i < index; i++) {
mNode = mNode.next;
}
} else {
//指向头结点的前驱结点，逆时针查找
mNode = mHead.prev;
for (int i = 0; i < mCount - index - 1; i++) {
mNode = mNode.prev;
}
}
return mNode;
}
/**
* 在线性表某个位置index插入结点
* @param index
* @param value
*/
void insert(int index, T value) {
//创建一个新的结点
DNode<T> newNode = new DNode<T>();
//新节点数据域赋值
newNode.value = value;
//插入到第一个结点之前
if (index == 0) {
//新节点前驱指向头结点前驱
newNode.prev = mHead;
//新节点后继指向头结点的后继，即第一个结点
newNode.next = mHead.next;
//第一个结点的前驱指向新节点
mHead.next.prev = newNode;
//头结点的后继指向新节点
mHead.next = newNode;
} else if (index == mCount) { //新节点追加到尾部结点之后
//新节点前驱指向尾部结点
newNode.prev = mHead.prev;
//新节点后继指向头结点
newNode.next = mHead;
//原先的尾部结点，后继指向新节点
mHead.prev.next = newNode;
//头结点前驱指向新节点
mHead.prev = newNode;
} else { //插入到非头尾的中间位置结点之前
//首先获取index位置的结点
DNode mNode = getNode(index);
//新节点前驱指向index结点的前驱
newNode.prev = mNode.prev;
//新节点的后继指向index位置结点
newNode.next = mNode;
//index 位置前驱结点的后继指向新节点
mNode.prev.next = newNode;
// idnex 位置结点前驱指向新节点
mNode.prev = newNode;
}
mCount++;
}
/**
* 返回某个位置的结点的数据域
* @param index
* @return
*/
T pop(int index) {
T value = null;
//获取Index位置的结点
DNode indexNode = getNode(index);
//index位置结点的--前驱结点的-后继指向--index位置的后继结点
indexNode.prev.next = indexNode.next;
//index位置结点的--后驱结点的-前驱指向--index位置的前驱结点
indexNode.next.prev = indexNode.prev;
value = (T) indexNode.value;
indexNode = null;
mCount--;
return value;
}
/**
* 线性表是否为空
* @return
*/
public boolean isEmpty() {
return mCount == 0;
}
}
对于链表结构俩说，他的插入和删除十分注重操作顺序，尤其在双向链表中，每一个结点都改动，都要同时兼顾其前驱和后继指针的指向。但也很有规律，参考以上代码和下面的图示，应该很容易掌握双向链表的插入和删除要点了。
双向链表插入
双向链表删除
可以发现，链表的循环实现只是让我们查找链表中某个结点变得容易，对链表结点的增删并不本质的改变。
线性表总结
前面我们说了，数据结构所要完成的工作就是使用数据的物理结构正确的反映数据元素的逻辑结构，因此，我们可以认为，数据结构就是如何将4种逻辑结构和2种物理结构，以最优的方式组合，实现ADT。线性表，就是最简单也最常用的线性结构，用两种存储结构的实现。
综上，关于线性表常用的实现方式可以做如下归类。
- 顺序存储结构
- 一维数组
- 链式存储结构
- 单链表
- 循环链表
- 双向链表
- 静态链表
静态链表，是对于某些语言，没有类似于C、C++、Java中指针，引用相关概念，无法按照常规方式实现链表，而是用数组代替指针描述链表的一种结构。此处暂不展开叙述。
总的来说，对于线性表这种结构，两种存储结构都各有优缺点；顺序存储结构，一般都会使用数组实现，这使得他可以随机存取，可以非常方便的实现特定位置元素的获取；但也因为数组的特性，存储空间被固定，插入元素需要考虑存储容量的大小；每一次的插入和删除操作都涉及数组元素的移动，十分不便；链式存储结构，对于插入和删除操作非常合适，同时也不用考虑容量大小的问题，但面对查找有会显得不那么给力。因此，两种实现方式各有千秋；实际开发中应该按照特定的场景选择合适的实现方式。
