一、概述
数据结构是指相互之间存在着一种或多种关系的数据元素的集合。
程序 = 数据结构 + 算法 。数据结构和算法两个概念间的逻辑关系贯穿了整个程序世界，首先二者表现为不可分割的关系。
数据结构与算法关系：数据结构是底层，算法是高层。数据结构为算法提供服务，算法围绕数据结构操作。
数据结构看分为逻辑结构和物理结构（存储结构）。逻辑结构是指数据对象中数据元素之间的相互关系。物理结构：是指数据的逻辑结构在计算机中的存储形式。逻辑结构分为：集合结构、线性结构、树形结构和图形结构。物理结构分为顺序存储和链式存储。
常用的数据结构有：
- 数组（Array）
- 链表（Linked List）
- 栈（Stack）
- 队列（Queue）
- 树（Tree）
- 堆（Heap）
- 图（Graph）
- 散列表（哈希表）（Hash）
二、数组和链表
线性表（线性的数据结构）是最常用且最简单的一种数据结构，它是n个数据元素的有限序列。实现线性表的方式有两种：数组和链表（有时也称列表）。
数组（顺序存储结构）
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。
数组的空间是从栈中分配的。
优点：
- 随机访问效率很高，时间复杂度可以达到O(1)。数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问。
缺点：
- 数组只能存储一种类型的数据
- 数组需要预留空间，数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小。导致数组空间的利用率低
- 在数组头部插入数据和删除数据效率低。后面的元素都需要向前或向后搬移，时间复杂度为O(N) 。
- 当数组空间不够使用的时候需要扩容，由于创建后大小不能改变，因此只能创建一个新的大的数组来替换当前数组。
适用场景：
频繁查询，对存储空间要求不大，较少进行增删操作。
链表（链式存储结构）
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。
链表的空间是从堆中分配的。
根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
优点：
- 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
- 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加删除操作很快，时间复杂度为O(1) 。
缺点：
- 含有大量的指针域，占用空间较大；
- 查找元素需要遍历链表来查找，非常耗时，时间复杂度为O(N)。
适用场景：
数据量较小，需要频繁增加，删除操作的场景。
java
- Vector、Array、ArrayList都是以数组的形式存储在内存中，所以查询效率高，新增和删除效率不高，但是Vector被Synchronized修饰，所以线程是安全的，ArraryList线程不安全。
- LinkedList则以链表的形式进行存储，所以查询效率底，新增和删除效率高，并且线程不安全。
三、栈和队列
通常称，栈和队列是限定插入和删除只能在表的”端点”进行的线性表。
栈
栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构。
栈有自己的结构特性：栈是后进先出的线性表，栈的插入和删除操作只能在这个线性表的表尾进行。对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。
队列
队列的本质也是一个线性表，则队列也可以用数组和链表两种方式来实现。
队列有自己的结构特性：队列是先进先出的线性表，它同时维护表的两端，但只能在表尾进行插入，在表头进行删除操作。
java
- Stack
- Queue
四、树
树不在是一对一的数据结构，而是一对多的非线性连接。其中常用的包括二叉树、二叉搜索树、2-3树、红黑树等等。
more >>
