1、数组(Array)
优点：因为数组中的元素在内存中是临安徐存储的，可以根据下标查询元素，因此查询和遍历元素速度很快。查询和遍历时间复杂度O(1).
缺点：大小确定无法扩容；一个数组只能存放一种类型数据；添加和删除数据需要操作数组中所有数据，很耗时。插入和删除时间复杂度O(n).
2、链表(LinkedList)
一种递归的数据结构，或为空，或指向一个节点(node)的引用，该节点还有一个元素值和一个指向另一条链表的引用。
双向链表：当前元素item既有pre也有next，但first的pre为null，last的next为null
单向链表：当前元素只有next
单向链表的缺点是只能从头到尾依次遍历。
链表中的数据“链式”存储，因此可以达到内存上的非连续(用引用来指向就行)。数组必须是一块连续的内存(数组在声明时就确定了大小)。
链表实现了内存的灵活动态管理，插入、删除复杂度为O(1)；但查找元素需遍历整个链表，复杂度为O(n).
优点：无需初始化容量，可添加任意元素；插入删除只需要更新引用。
缺点：含有大量引用，内存占用空间大；查找元素需遍历整个链表。
3、栈(Stack)
先进后出，后进先出。类似一个底部封口，上部开口的容器。
如图，a1最先进，但最后出。
4、队列(Queue)
先进先出，后进后出。队列会对两端定义，一端队头，一端队尾。队头只允许删除（出队）操作，队尾只允许插入（入队）操作。
栈和队列都是线性表，但规则不同
5、树(Tree)
典型的非线性结构，由n(n0)个有限节点组成的一个具有层次关系的集合。
树形结构的特点：
每个节点都只有有限个子节点或无节点；
无父节点的节点称为根节点；
每个非根节点有且仅有一个父节点；
除根节点外，每个子节点可分为多个不相交子树。
深度：对任意节点，n的深度为从根到n的唯一路径长，根的深度为0。
高度：对任意节点，n的高度为从n到一片树叶的最长路经长，所有叶的高度为0。
常见树的分类：
无序树：树中任意节点的子节点间无顺序关系。
二叉树：每个节点最多含有2个子树。
完全二叉树：除叶子节点外，每层都满2个节点。
满二叉树：每层都是2个节点。
二叉查找树(BinarySearchTree)：
a.任意节点的左子树不空，左子树上所有节点的值均小于它根节点的值；
b.任意节点的右子树不空，右子树上所有节点的值均大于它根节点的值；
c.任意节点的左右子树也是二叉查找树。
二叉查找树相较于其他数据结构优势在于查找、插入的复杂度较低，为(O(logn))。平衡二叉树：当且仅当任意节点的二个子树高度差不大于1的二叉树。本质也是二叉树，只是避免了树的左右两边差别过大
平衡二叉树难点在于插入或删除时如何左旋或右旋来平衡左右。
java中最常见的平二叉是红黑树：
每个节点只能是R或者B；
根节点为黑B色；
每个叶节点(NIL节点，空节点)是B；
如果一个节点是红的，那它的两个子节点就是黑的，即一条路径上不能出现相邻的两个节点是相同颜色；
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
6、堆(Heap)
可以看做是一棵树的数组对象。
堆中某个节点的值总是不大于或者不小于其父节点的值；
堆总是一个完全二叉树。
7、哈希表(HashTable)
也叫散列表，是一种可以通过K-V键值对直接访问的数据结构。最大的特点就是可以实现查找、插入和删除。结合了数组和链表的优点。java的hashmap在此基础上还加入了树的优点。
哈希函数在哈希表中起关键作用。对任一数据块，哈希函数为其生成一个哈希值存放在Key上。不同数据块哈希值相同的可能性很小，查询时无需遍历，通过K值访问即可。万一哈希值冲突，java的hashmap会在数组的同一位置增加链表，若链表长度大于8将转为红黑树(拉链法)。
8、图(Graph)
复杂的非线性结构，由顶点的有穷集合和顶点之间的边的集合组成。
G(V,E).G代表一个图，V代表顶点集，E代表边集。
总结：
在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素均有唯一的前驱和后继；
在树形结构中，数据元素之间有着明显的层级关系，且每个元素只与上一层和下一层元素有关；
图形结构中，节点间关系任意，图中任意两元素间均可能有关联。
HashTable和HashMap的区别：
HashTable不允许有空值，线程同步（安全）；
HashMap允许有空K和空V，线程不安全。
HashMap是HashTable的轻量级实现。
预览时标签不可点收录于话题#个上一篇下一篇