前言

这里会结合自己去年看的数据结构内容，用Java语言写包括数组，栈，链表，队列，树，图，堆，散列表等基本操作，会给出时间和空间复杂度。

一、线性表

线性表是具有相同特性的数据元素的一个有限序列，其元素在位置上是有序的，这种位置上有序性（逻辑有序）就是一种线性关系。在Java中，List就是我们经常用到的线性表接口，里面定义了一些抽象的方法，其目的就是对线性表的抽象，其中的方法就是线性表的一些常用基本运算。根据不同存储结构对应实现方式也不同，可以分为顺序结构（ArrayList）和链式结构（LinkedList）。

1、顺序表

数组即我们常用的顺序表，他把表中的所有元素按照其逻辑顺序依次存储在计算机存储器中指定存储位置开始的一块连续的存储空间中（顺序表元素物理空间上连续）。在Java中创建一个数组对象就是分配了一块可供用户使用的连续的存储空间，该存储空间的起始位置就是由数组名表示的地址常量。
通常我们使用基本数组使用，如下：
int[] list= new int[]{1,2,3}; //创建一个数组
Array.getInt(list, 0); //获取数组中序列为0的元素
Array.set(list, 0, 1); //设置序列为0的元素值为1
上述代码创建的是固定长度的数组，其容量无法修改，当list被创建出来的时候，系统只为其分配3个存储空间，所以我们无法对其进行添加和删除操作。Array类是一个用于操作数组的工具类，这个类提供的方法只有两种：get和set，所以只能获取和设置数组中的元素。对于这两种操作，我们通常使用array[i]、array[i] = 0的简化方式。
数组优点：
1、按照索引查询元素速度快（时间复杂度为O(1)）
2、按照索引遍历数组方便
数组缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素（如100个元素的数组，删除第50个，那么他后面50个元素都要往前移动，故时间复杂度为O(n)）
另一种动态长度的数组是ArrayList，如果是无参构造时（即new ArrayList()），默认初始化容量为0，但是当在第一次添加元素时容量扩大至 10 。ArrayList中的数组长度是大于等于其元素个数的，当执行add()操作时首先会检查数组长度是否够用，只有当数组长度不够用时才会创建新的数组，由于创建新数组意味着老数据的搬迁，所以这个机制也算是利用空间换取时间上的效率。

2、链表

顺序表必须分配一块固定大小的连续内存，不便于存储空间的管理，故提出了可以实现动态空间管理的链式存储结构-链表（即逻辑上连续的两个元素，物理空间不连续）。
在链表中，每个存储结点不仅包含元素本事的信息（即数据域），还需包括元素之间的逻辑关系（前后结点的地址信息，即指针域）。这样通过一个结点方便找到其后继结点的位置。
由于链表中每个元素至多包含一个前驱结点和一个后继结点，故当采用链式存储时，可以选择单链表和双向链表。
单链表：每个结点中，除了包含数据域外，只包含一个指向后继结点的指针域。
public class LNode {
protected LNode next; //指针域，指向直接后继结点
protected Object data; //数据域
}
双向链表：每个结点中，除了包含数据域外，设置两个指针域，分别用以指向直接前驱结点和直接后继结点。
public class DNode {
protected DNode prior; //指针域，指向直接前驱结点
protected DNode next; //指针域，指向直接后继结点
protected Object data; //数据域
}
单链表当访问一个结点后，只能接着访问它的直接后继结点，而无法访问他的直接前驱结点。双链表则既可以依次向后访问每个结点，也可以依次向前访问每个结点。
相比于顺序表，
单链表的优点：
1、添加、删除的操作快，因为只需修改指针即可（时间复杂度为O(1)）
2、方便动态增加长度
单链表缺点：
1、因为要存储多余的指针域，需要牺牲存储空间
2、查找元素较慢，因为要从头开始一个个查找（时间复杂度为O(n)）
3、查找前驱元素在单链表中很慢，双向链表较快
Java中LinkedList属于双向链表。

二、栈和队列

栈和队列，本质上也是线性表，只是在逻辑上做了限制，根据我们操作的需求，人为地在线性表上加上限制，形成了两种具有独特功能的数据结构。

1、栈