数据结构(Data Structure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构定义
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：
Data_Structure=(D,R)
其中 D 是数据元素的集合，R 是该集合中所有元素之间的关系的有限集合。
数据结构具体指同一类数据元素中各元素之间的相互关系，包括三个组成成分，数据的逻辑结构、存储结构和数据运算结构。
数据的逻辑结构
数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构分为以下几种：
集合结构：数据元素同属一个集合，单个数据元素之间没有任何关系。线性结构：数据结构中的元素存在一对一的相互关系。树形结构：数据结构中的元素存在一对多的相互关系。图形结构：数据结构中的元素存在多对多的相互关系。
数据的物理结构
数据的物理结构是指数据的逻辑结构在计算机存储空间的存放形式，它包括数据元素的机内表示和关系的机内表示。物理结构又叫存储结构，分为以下几种：
顺序存储结构：一段连续的内存空间。优点：随机访问；缺点：插入删除效率低，大小固定。链式存储结构：不连续的内存空间。优点：大小动态扩展，插入删除效率高；缺点：不能随机访问。索引存储结构：为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。优点：对顺序查找的一种改进，查找效率高；缺点：需额外空间存储索引。散列存储结构：选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置，引起地址冲。优点：查找基于数据本身即可找到，查找效率高，存取效率高；缺点：存取随机，不便于顺序查找。
由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
数据结构算法
数据结构算法的设计取决于数据的逻辑结构，而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现，为了全面的反映一个数据的逻辑结构，它在存储器中的映象包括两方面内容，即数据元素之间的信息和数据元素之间的关系。不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序等。
数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开对该结构上的数据运算及其实现算法的讨论。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。
对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。不同的数据结构其操作集不同，但下列操作必不可缺：
- 结构的生成；
- 结构的销毁；
- 在结构中查找满足规定条件的数据元素；
- 在结构中插入新的数据元素；
- 删除结构中已经存在的数据元素；
- 遍历。
数据结构分类
每一种数据结构都有着独特的数据存储方式，常用的数据结构有：数组、栈、链表、队列、树、图、堆、散列表等，如图所示：
数组
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。
优点：
- 按照索引查询元素速度快
- 按照索引遍历数组方便
缺点：
- 数组的大小固定后就无法扩容了
- 数组只能存储一种类型的数据
- 添加，删除的操作慢，因为要移动其他的元素。
适用场景：查询频繁，对存储空间要求不大，很少增加和删除的情况。
栈
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
队列
队列与栈一样也是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。队列的特点是先进先出，或者说是后进后出，进行插入操作的端称为队尾，进行删除操作的端称为队头，从一端放入元素的操作称为入队，取出元素为出队。队列中没有元素时，称为空队列。
使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
链表
链表是物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表的指针地址实现。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
链表的优点：
- 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
- 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
缺点：
- 因为含有大量的指针域，占用空间较大；
- 查找元素需要遍历链表来查找，非常耗时。
适用场景：数据量较小，需要频繁增加，删除操作的场景。
树
树是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 有且仅有一个根结点(没有父节点的节点称为根节点)；
- 每个节点有零个或多个子节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。二叉树是树的特殊一种，具有如下特点：
- 每个结点最多有两颗子树，结点的度最大为2。
- 左子树和右子树是有顺序的，次序不能颠倒。
- 即使某结点只有一个子树，也要区分左右子树。
二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
堆
堆是一种特殊的树形数据结构，每个结点都有一个值。堆的特点是根结点的值最小或最大，且根结点的两个子树也是一个堆。它具有以下的特点：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
图
图是由结点的有穷集合 V 和边的集合 E 组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
按照顶点指向的方向可分为无向图和有向图。图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。
散列表
散列表也叫哈希表，是根据键和值(key 和 value)直接进行访问的数据结构，通过 key 和 value 来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
f(key) 称为散列函数或哈希函数，用来记录数据的存储位置，若结构中存在键和 key 相等的记录，则必定在 f(K) 的存储位置上。而散列表就是把 key 通过一个固定的算法函数(哈希函数)转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将 value 存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
哈希表在应用中也是比较常见的，就如 Java 中有些集合类就是借鉴了哈希原理构造的，例如 HashMap、Hashtable 等，利用哈希表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的 HashMap 底层的存储就是采用这种结构，直到 JDK 1.8 之后才换成了数组加红黑树的结构。
