前言
虽然这个系列文章叫《java数据结构》，但是实际上讲的是数据结构，只是因为我主要用的语言是java，所以在讲述数据结构的时候，如果有涉及到需要用代码的地方，我都会通过java代码来展示，这才是我这样取名的原因。
也因此，我并不是在讲述java这门语言中的数据结构，应该说，我讲的不仅仅是java数据结构，而是包含java数据结构在内的对整个数据结构的分析和了解。
当然，这也没有什么，写这些文章的目的主要也是梳理自己的知识体系，如果顺便能给大家一点帮助，那当然是意外之喜了。
正文
一般来说，线性结构可以分为如下几种类型：
- 一般线性表
- 受限线性表（栈，队列，堆，串）
- 推广线性表（一维数组，广义表）。
而本文要分析的就是 一般线性表。
一般线性表在我们日常的开发中非常常见，java语言中的数组，集合，都是比较常见的一般线性表，也因此，我们会将其简称为线性表。那么，什么是一般线性表呢？
一般线性表是零个或者多个数据元素的有限序列。
而在这里，我们要注意两个关键词，一个是 有限，一个是 序列。
有限 意味着一般线性表的数据元素是有限的，序列 意味着一般线性表是一个序列，也就是说，数据元素之间是有顺序的。
当一般线性表的数据元素个数为0，这个时候称之为空表。
一般线性表的组成模型
假如设置一个一般线性表的模型，我们可以这样简单的设置：
A0，A1，A2，A3，A4，...，An-1
我们说这个表的大小是为n，那么在这个一般线性表中有一个数据元素为Ai，那么我们可以说，Ai-1是Ai的前驱元素，Ai+1是Ai的后继元素，而第一个元素A0就没有前驱元素，最后一个元素An-1则没有后继元素，那么，基于这些分析，我们可以得出一个简单的结论：
在一般线性表中，若元素有多个，那么第一个元素无前驱元素，最后一个元素没有后继元素，其他的元素则是既有前驱元素，也有后继元素。
一般线性表的存储结构
通常我们在分析一个数据结构的时候，都会同时分析存储结构和逻辑结构，但是一般线性表，我们通过名字也能知道，这种数据结构的逻辑结构就是线性结构。
那么，一般线性表的存储结构是什么呢？
一般线性表有两种存储结构，一种是顺序存储结构，一种链表存储结构。
顺序结构的一般线性表中，比较常见的运用到实际中的数据结构是一维数组，也就是平时说的数组。而链表存储结构的一般线性表中，比较常见的运用到实际中的数据结构则是链表。
代表着一般线性表的数组和链表，接下来我们来对这两个结构进行一个详细的分析。
顺序存储结构——数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。数组属于线性表的一部分。一般来说，线性表有两种存储方式
它的逻辑结构和存储结构如下：
-
存储结构：顺序存储结构
为什么说数组的存储结构是顺序存储呢？我们从数组的定义中可以得知，数组是用一组连续的内存空间来存储一组具有相同类型的数据。那么这就意味着数组需要一段连续的存储空间，这种存储方式，也就是顺序存储结构。
-
逻辑结构：线性结构
为什么说数组的逻辑结构是线性结构呢？线性结构中的数据最多只有向前或者向后两个方向，而很明显的是，数组是只有向后方向的，所以我可以知道数组结构是线性结构。
我们知道了数组的逻辑结构和存储结构，那么其实我们可以对数组的特性都有了大概的了解了。不过我们还是来对数组来做更精细的分析。
1. java中的数组
java中的数组应用其实比较广泛的。因此我们可以对java语言中的数组结构进行一定程度的分析。
1.1 普通数组
比如我们所知道的java中数组，如下所示：
public static void main(String args[]) {
int a[] = new int[3]; /*开辟了一个长度为3的数组*/
a[0] = 10; // 第一个元素
a[1] = 20; // 第二个元素
a[2] = 30; // 第三个元素
for(int i = 0; i < a.length; x++) {
System.out.println(a[i]); //通过循环控制索引
}
}
这种数组结构，在java语言中一般被称之为数组，这种数组，指的就是一组相关类型的变量集合，并且这些变量可以按照统一的方式进行操作。
这种比较传统的数组结构，它的长度大小是没有办法改变的，当它要插入元素的时候，或者要删除元素的时候，数组都没有办法去扩充的。
也就是说，这种数组结构，一旦元素长度确认了，就无法再改变。也没法插入新元素和删除旧元素。
由于这种数组结构，在实际的业务开发中的不适用，所以java在这个数组的基础上，创造动态数组，也就是javaer口中的集合结构。
1.2 动态数组（集合）
代码如下：
public static void main(String[]args) {
//确定数组的长度只有10
List<Integer> aList=new ArrayList<>();
aList.add(1); // 第一个元素
aList.add(2); // 第二个元素
aList.add(3);// 第三个元素
for(Integer a:aList) {
System.out.println(a); //通过循环控制索引
}
}
可以看出来，这个aList的集合，我在创建的时候，是没有声明它的大小的（当然，在初始化的时候集合是有默认大小的），而且在后续的插入中，我也没有关注这个集合的长度大小的扩充。
这也就是说，这种集合，底层确实是数组，但是在插入元素的过程中，数组的大小会不断的扩充。这种集合，叫做动态扩充数组。
1.3 数组的越界问题
先看一段代码，如下：
public static void main(String[]args) {
//确定数组的长度只有10
int[] a=new int[10];
for (int i=0;i<10;i++){
a[i]=i;
}
for (int c:a){
System.out.println(c);
}
//这里应该会爆出错误
System.out.println(a[11]);
}
运行后的结果如下：
E:\jdk\bin\java.exe
0
1
2
3
4
5
6
7
8
9
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException。
这是典型的数组: 11
at com.xxxx.service.impl.OrderServiceImpl.main(OrderServiceImpl.java:1397)
Process finished with exit code 1
当我在一个长度为10的数组中，试图去找出下标为11的数组的值的时候，会爆出一个错误ArrayIndexOutOfBoundsException。
这是典型的数组越界问题。
为什么会出现数组越界问题呢？
要知道数组的存储结构是顺序存储结构，那么也就是说数组是一个连续的内存空间，那么当我们访问下标为11的数组位置的时候，会发现超出了这个连续的内存空间，那么自然会报错。
要注意的是，在java这门语言中，即便使用的是动态数组，也会出现数组越界问题，比如下面这段代码：
public static void main(String[]args) {
//确定数组的长度只有10
List<Integer> aList=new ArrayList<>();
aList.add(1);
aList.add(2); // 第二个元素
aList.add(3);// 第三个元素
System.out.println(aList.get(4));
}
运行后的结果如下:
E:\jdk\bin\java.exe
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 4, Size: 3
at java.util.ArrayList.rangeCheck(ArrayList.java:653)
at java.util.ArrayList.get(ArrayList.java:429)
at com.xxxx.service.impl.OrderServiceImpl.main(OrderServiceImpl.java:1394)
Process finished with exit code 1
我们发现，最后也是出现了数组越界问题。
2.数组的性能研究
数组在java语言中，得到了广泛的应用，甚至可以这么说，在java这门语言中，如果只是一般的业务场景，可以整个业务代码中只需要使用动态数组就够了。（别和我讲性能，使用java语言了都还讲什么性能！）
但是，我们要知道的是，数组结构虽然有着无与伦比的魅力，那么也必然存在着不能忽略的缺点，也因此，我们要对数组的性能有一个大概的了解，这是基于我们对数据结构最基本尊重！（ps：懵逼~我到底在说些什么？）
当我们看一个东西的时候，当然应该先看它的优点，这有益于我们更好的接受它们。当我们了解数组的时候，也是如此。
2.1 数组的优点
数组的优点是什么？
在我刚刚接触数据结构的时候，我发现，任何一个数据结构的优点和缺点，都和它们的存储结构和逻辑结构有着很大的关系，后来我渐渐察觉到，既然任何数据结构，实际上都是逻辑结构和存储结构组成，那么这些数据结构的优点和缺点，也就是逻辑结构和存储结构的优点和缺点。
因此，现在我们分析数组结构的优点的时候，我们可以去分析一下逻辑结构和存储结构的优点就可以了。
顺序存储机构和线性逻辑结构的优点是什么？这个就很明显了，查询速度很快。
知道这一点还不够，我们知道了数组的查询速度很快，那么，为什么数组的查询速度很快呢？
说白了，数组是顺序存储结构，那么数组在物理计算机上存储的时候，使用的是连续的内存空间，我们知道，计算机会给每个内存单元分配一个地址，那么，如果通过这个地址来访问内存中的数据，那自然就很快了。而不巧的是，数组就是这样来访问数据的。
当计算机去访问数组中的某一个数据的时候，会通过一个公式去计算出存储改元素的内存地址，公式如下：
a[i]_address = base_address + i * data_type_size
翻译一下，就是如下：
内存地址 = 内存块的首位地址 + 数组中每个元素的大小
2.2 数组的缺点
因为数组是顺序存储结构，那么就意味着存储的是一个连续的内存空间，那么当我们需要插入一个元素的时候，会发生什么呢？
这个时候，拿出我在《从头开始学习->java数据结构（一）：物理上的存储结构》中的一张图来说明一下这个问题：
从图所示的插入过程中，我们发现，自插入位置起，后面的所有数据元素都往后面移动了一位，想一想，如果数据量上去了，那么等于大量的数据都要移动，而且实际的情况，远远比这个更糟糕，所以这样的插入效率，可想而知。
如果想优化一下数组的插入，该怎么操作呢？
如果数组中存储的数据没有任何规律，插入后不需要保持原来的顺序，则可以进行如下操作：直接将第 k 位的数据搬移到数组元素最后，然后把新的元素直接放在第 k 位。
而删除也同样如此，如果要删除第 k 位的元素，为了内存的连续性，也需要搬移数据，否则中间就会出现空洞，内存就不连续了。
当然，我们也有办法优化数组的删除操作。
我们可以将多次删除操作集中在一起执行，先标记下已经删除的数据，然后在某些条件下（比如没有更多空间存储数据时），统一执行真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
这种标记清除思想在其他地方也有所应用，比如垃圾回收中的标记清除算法。
2.3 动态数组的扩容
先看一张数组的动态扩容图，如下：
如图所示，当我们的data数组原容量只有4，且里面已经有四个元素，无法再次添加，我们可以先定义一个新数组newData，他的容量是data的二倍，将data中的数据拷贝到newData中，再将data指向newData（引用转换），释放原数组的空间和newData引用，就完成了动态扩容。
链式存储结构——链表
在顺序存储结构中，数据元素的前驱和后继的这种逻辑关系，通过数据元素的存储位置就能够清晰得出，也就是说，在顺序存储结构中，每个数据元素只需要存储数据元素信息就可以了。
但是链式存储结构中，除了要存储数据元素信息以外，还要存储它的后继元素的存储地址。这是为什么呢？
首先，我们可以来看一张图片，如下：
我们可以看到，在链式存储结构中，数据元素的内存位置不是连续的，数据元素可以存储到内存的任意位置，那么作为一个有限的序列，链表中的一个数据元素如何指向下一个元素呢？
在图中A,B,C,D,E这五个元素，存储的位置都不是顺序的，但是A的下一个元素要指向B，B的下一个元素要指向C，等等这种顺序，要通过什么方式来表明呢？
所以，我们不仅仅要存储数据元素信息，而且还要存储它的后继元素的存储地址。所以真实的存储结构如下图：
而这种智能指向链表中的下一个元素，且元素之间不能互相指向的线性链表结构，我们一般称之为单向链表，除了单向链表还有双向链表，循环链表等等。
接下来，我们逐一来细细分析这些数据结构。
1. 单向链表
什么是单向链表呢？
其实刚刚我已经描述了一遍了，我现在再重新说一遍。单向链表 指的是链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向的线性链表。
单向链表的插入和删除都是特别简单的逻辑，在之前我讲述链式存储结构的时候，其实已经通过画图说明链式存储结构了，而那个时候的例子就是单向链表，下图就是当初那张图：
可以看出来，在单向链表中，数据插入或者删除的时候，不需要将插入数据后面的数据移动，只需要修改一下指针域的指向性就可以了。
2. 循环链表
我们知道，在一般线性表中，最后一个元素是没有后继元素的，而且在单向链表中，最后一个数据元素不但没有后继元素，而且它的指针域也没有指向下一个元素，因为不存在下一个元素。
那么，假如我们让单向链表的最后元素的指针域指向了单向链表的第一个元素，这种结构叫什么呢？这就是循环链表。如图所示：
3. 双向链表
在单向链表中，一个元素只有指向下一个元素的指针域，可是有时候，我们在使用链表的结构的时候，可能会感觉不是很方便，为什么呢？
先看一下单向链表的图：
当我们查询到一个元素B的时候，我们可能通过二分法查到了C，但是通过C我们能查到的下一个元素只可能是D，我们需要查询到B，但是C元素没有指向B的指针域。
如果一个数据元素，既有指向下一个元素的指针域，也有指向上一个元素的指针域，那么这种结构就是双向链表。如图所示：
4.双向循环链表
在单向链表的基础上，任意一个元素，既可以访问它的前驱节点，也可以访问它的后继节点，而且最后一个元素的后继节点指向第一个元素，第一个元素的前驱节点指向最后一个元素，那么这种数据结构，我们称之为双向循环链表结构，如图所示：
5. 静态链表
对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。
这种结构一般都是在C语言中比较常见，就多讲了。
6. java中的链表结构
在java这门语言中，不仅非常深入的应用了数组结构，当然也非常深入的使用了链表结构。
比较常见的链表结构，一个Node类，就是一个比较常见的单链表结构，一个是我们常见的HashMap等集合，底层使用的就是链表结构。
Node类的代码如下：
package com.algorithm.link;
/**
* 链表结点的实体类
* @author bjh
*
*/
public class Node {
Node next = null;//下一个结点
int data;//结点数据
public Node(int data){
this.data = data;
}
}
可以看出，是一个很明显的单链表结构。
而HashMap采用的是Entry数组来存储key-value键值对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构。
在HashMap内部有一个Entry类的静态内部类，代码如下：
//静态内部类 ，Entry用来存储键值对，HashMap中的Entry[]用来存储entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //键
V value; //值
Entry<K,V> next; //采用链表存储HashCode相同的键值对，next指向下一个entry
int hash; //entry的hash值
//构造方法， 负责初始化entry
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
通过这段代码可以看出，Entry类是一个单向链表结构。
7. 链表的性能分析
链表的性能，和数组是刚好相反的。
数组是查询快，但是插入和删除慢。链表就是查询慢，插入和删除快。
但是总的来说，链表的 优点 可以大概分为三个：
- 链表对内存的利用率比较高，无需连续的内存空间，即使有内存碎片，也不影响链表的创建；
- 链表的插入和删除的速度很快，无需像数组一样需要移动大量的元素，只需要改变指针指向即可。
- 链表大小不固定，不用事先开辟内存，可以很方便的进行动态扩展。
- 没有空间限制，存储元素无上限，只与内存空间大小有关。
缺点 就比较明显了，如下：
- 不能随机查找数据，必须从第一个开始遍历，查询效率比较低下。
- 占用额外的空间以存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多。
但是不同的链表结构，性能也有着很大的差别。
比如双向链表，由于一个数据元素有着两个指针域，那么相比较于单向链表来说，双向链表要占据更多的内存空间，但是它的查询速度要比单向链表要来得快，这是典型的通过空间换取时间。
数组和链表的对比
数组和链表作为一般线性表的两种经典结构，由于存储结构的不同，它们的性能也有着很大的不同，我们可以通过分析这两者的不同，对数组和链表有着更深的理解，也对一般线性表有着更深的理解。
我们可以通过多个点来分析数组和链表，如下：
1. 内存空间：
数组需要的内存空间是一块连续的区域，而且数组需要预留内存空间，在使用前要先申请占据内存的大小，这样可能会浪费内存空间，对内存空间的要求也相对较高。
链表可以保存在内存中的任何地方，也不要求连续，也不用事先申请内存，对内存的利用效率比较高。但是链表的每一个数据都保存了下一个数据的内存地址，这样对内存空间也造成了一定程度的浪费。
2. 查询速度
数组的随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
链表的查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。 要找到第三个人，必须从第一个人开始问起。
3. 删除和插入效率
数组的插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。
链表的增加数据和删除数据很容易。 再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
4. 扩展效率
数组的大小是固定的，不能动态扩展，也因此，当数组定义的空间不够时要重新定义数组。
链表不指定内存大小，所以扩展方便。链表大小不用定义，数据随意增删。
总结
对一般线性表的分析，就到这里了，我也只是浅尝辄止而已，对立面的很多细节没有进行足够的挖掘，但是如果只是为了对一般线性表的定义有一个明朗清晰的划分，我相信我的文章也足够了。
