JAVA常见的数据结构（java 常见的数据结构）

JAVA提供了比较常见的数据结构包括数组、链表、栈、队列、树、哈希表、堆、图等。

数组

在java中，数组（Array）是在内存中存储相同数据类型的连续的空间。数组的大小在创建之后就确定了，无法扩容。数组按照索引查询元素，速度很快，时间复杂度为O(1) 。添加、删除元素的操作很耗时间，因为要移动其他元素，时间复杂度为O(n)。

链表

与数组不同的是，链表（Link）是一种物理存储单元上非连续空间的存储结构。每一个链表都包含多个节点元素，链表的节点元素的逻辑顺序是通过链表中的指针连接次序实现的。节点元素包含两个信息，一个是元素节点含有的数据信息，一个是元素节点指向地址信息（该元素节点的下一节点或者上一节点的地址）。链表在插入、删除的时候可以达到 O(1) 的时间复杂度（只需要重新指向引用即可，不需要像数组那样移动其他元素）。链表查询需要遍历整个链表，耗时，时间复杂度为O(n) 。链表有单向链表和双向链表两类。

栈

栈（Stack）是限制线性表中元素的插入和删除只能在同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。栈按照“后进先出”、“先进后出”的原则来存储数据，先插入的数据被压入栈底，后插入的数据在栈顶，读出数据的时候，从栈顶开始依次读出。

队列

队列（Queue）是一种只允许在一端进行插入，在另一端进行删除的线性表结构。允许插入的一端叫队尾，允许删除的一端叫队头。队列在生活中很常见，例如：食堂排队打饭、车站进站排队等。栈按照“先进先出”、“后进后出”的原则来存储数据。

树

树（Tree）是一种典型的非线性结构，它是由 n（n>0）个有限节点组成的一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树的种类有很多，我们接触到的树有二叉树、平衡二叉树、二叉查找树、B树、B+树、哈夫曼树、红黑树等。

树形数据结构有以下这些特点：

• 有且只有一个根节点，没有父节点的节点称为根节点（如图节点12）；
• 每个节点都只有有限个子节点或无子节点；
• 每一个非根节点有且只有一个父节点。

哈希表

哈希表（Hash Table），也叫散列表，是一种可以通过关键码值（key-value）直接访问的数据结构，也就是说它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数。它最大的特点就是可以快速实现查找、插入和删除。我们知道，数组的最大特点就是查找容易，插入和删除困难；而链表正好相反，查找困难，而插入和删除容易。哈希表很完美地结合了两者的优点， Java 的 HashMap 在此基础上还加入了树的优点。由于存储空间有限，hash计算以后可能不同的关键字映射到同一个哈希地址上，这种现象称之为哈希冲突，例如：h(16)=16%11=5，h(27)=27%11=5，两个哈希地址就冲突了。

堆

堆（Heap）就是将一个集合的数据按照完全二叉树的顺序结构存储在一个一维数组中,堆在逻辑上是一棵完全二叉树,在物理结构上是一个一维数组。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

图

图（Graph）是一种复杂的非线性结构，是一种以网络形式相互连接的节点，与树有些相像，。在线性结构中，数据元素之间有唯一的线性关系，每个数据元素（除第一个和最后一个外）均有唯一的“前驱”和“后继”。在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素（父节点）及下一层的多个元素（子节点）相关。而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。