Java常见的数据结构有哪些?

数据存储的常用结构有：栈、队列、数组、链表和红黑树

集合是基于数据结构设计的，了解数据结构深入了解集合。

队列(queue )

先进先出，后进后出。场景：各种排队。有很多集合可以实现队列。

栈(stack)

后进先出，先进后出压栈==入栈弹栈==出栈例如：手枪的弹夹。

线性表(数组)

数组是内存中的连续存储区域。分成若干等分的小区域(每个区域大小是-一样的)元素存在索引 特点：查询元素快(根据索引快速计算出元素的地址，然后立即去定位) 增删元素慢(创建新数组，迁移元素)

链表

元素不是内存中的连续区域存储。元素是游离存储的。每个元素会记录下个元素的地址。特点：查询元素慢增删元素快(针对于首尾元素，速度极快，Java一般是双链表)

红黑树

二叉树： binary tree

永远只有一个根节点，是每个结点不超过2个节点的树(tree)

查找二叉树，排序二叉树： 小的左边，大的右边，但是可能树很高，性能变差。 为了做排序和搜索会进行左旋和右旋实现平衡查找二叉树，让树的高度差不大于1。

二叉查找树\二叉排序树：

二又查找树的特点:

左子树上所有的节点的值均小于等于他的根节点的值右子树上所有的节点值均大于或者等于他的根节点的值每一个子节点最多有两个子树

缺点：如果数的大小是的递增的，就会形成“瘸子”现象，只有“右腿”。树的高度就会很高。

Java底层做的是平衡二叉树

平衡二叉树：给予查找二叉树

为了避免瘸子现象，平衡二叉树：左右子树的高度差绝对值不大于1，并且左右两个子树都是一颗平衡二叉树。

当有新的数据插入二叉树，破坏了平衡，二叉树就要做旋转。左边高，右旋；右边高，左旋；如果不行继续旋转；

红黑树(就是基于红黑规则实现了自平衡的排序二叉树) :

树尽量的保证到了很矮小，但是又排好序了，性能最高的树。

每一个节点或是红色或是黑色根节点必须是黑色每个叶节点NIL是黑色如果某个节点是红色，它的子节点必须是黑色对于每一个节点，从 该节点到其所有子节点的路径上，黑节点的个数要一样

做插入时，如果不满足规则，则需要做旋转或变色，来满足规则