线性结构

• 线性结构作为最常用的数据结构，其特点是数据元之间存在一对一的线性关系
• 线性结构有2种不同的存储结构，即顺序存储结构和链式存储结构
• 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的（指元素地址是连续的）
• 链式存储线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放元数据以及相邻元数据的地址信息
• 线性结构常见的有：数组（最经典的一维数组），队列，链表和栈

非线性结构

• 非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

队列

队列是一个有序列表，可以用数组或者链表来实现，遵循先入先出原则（简称FIFO结构），即先存入队列的数据，要先取出来，后存入的数据，要后取出来。在队尾添加元素，在队头删除元素。

队列的相关概念

队头与队尾：允许元素插入的一端称为队尾，允许元素删除的一端称为队头

入队：队列的插入操作

出队：队列的删除操作

入队示意图：

添加元素时，元素只能从队尾一端进入队列，也即是2只能跟在1后面，3只能跟在2后面

出队示意图：

元素只能从队首出队列，出队列的顺序为：1、2、3，与入队时的顺序一致，这就是所谓的“先进先出”

基于数组的循环队列实现

以数组作为底层数据结构时，一般将队列实现为循环队列，这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作。

队列顺序存储图：

循环队列

所谓的循环队列，可以把数组看作一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。

循环队列图：

链表

链表是一种数据结构，和数组同级，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高（原因：随机访问数据时，无法像数组那样直接通过下标找到特定的数据项），但是插入和删除时优势明显，（原因：插入和删除操作时，不需要移动数据）。

单向链表

单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head）。

链表示意图：

head为头节点，它不存放任何的数据，只是充当一个指向链表中真正存放数据的第一个节点的作用，而每个节点中都有一个 next 引用，指向下一个节点，就这样一节一节往下面记录，直到最后一个节点，最后一个节点的next 指向 null。

删除节点示意图：

双向链表

节点类保留上一节点、下一节点的引用。链表类保留头节点、尾节点的引用，可以从尾节点插入和删除

双端链表

节点类保留下一节点的引用。链表类保留头节点、尾节点的引用，可以从尾节点插入，但只能从头节点删除 (双端链表不能删除尾节点原因是只能知道下个节点，不知道上个节点，故无法删除)。

双端链表示意图：

有序链表

递增，递减或者其他满足一定条件的规则，插入数据时，从头结点开始遍历每个节点，在满足规则的地方插入新节点。

栈

栈的概念介绍

栈是一种只允许在一端进行插入或删除的线性表，栈的操作端通常被称为栈顶，另一端被称为栈底，栈的插入操作称为进栈（压栈|push）；栈删除操作称为出栈（弹栈|pop）。栈中的元素是“先进后出”的特点。顺序存储的栈称为顺序栈（一般用数组来实现）；链式存储的栈称为链式栈。

顺序栈示意图：

链式栈示意图：

递归

递归就是方法自己调用自己，每次调用传递不同参数，递归有助于开发者解决问题，同时代码也很简洁。递归调用规则是当程序调用到一个方法时，在栈中开辟一份独立的方法栈空间，每个空间的数据（局部变量）是独立的。使用递归时，要注意防止死循环。递归的方法调用内存分布图：

排序

排序也称排序算法，是将一组数据根据指定的顺序进行排序。

排序分类：

• 内部排序：将需要处理的所有数据加载到内存进行排序

常见的内部排序算法：

插入排序：直接插入排序，希尔排序

选择排序：简单选择排序，堆排序

交换排序：冒泡排序，快速排序

归并排序

基数排序

• 外部排序：由于数据量太大无法全部加载到内存，需要借助外部存储进行排序

算法的时间复杂度

一个算法花费的时间和算法中语句执行的次数成正比，哪个算法中语句执行的次数多，它花费的时间就多，记为T(n)