数据结构（数据结构与算法）

Java常用的数据结构

栈：先进后出(后进先出) First In Last Out(FILO)

队列：先进先出 First In First Out(FIFO)

数组：

增删慢：每次增删元素时需要创建新的数组，需要拷贝大量的数组元素。

查询快：可以直接根据索引获得对应的元素。

链表

增删快：每次增删元素不需要移动元素位置，只需要修改上一个元素记住下一个元素的地址值

查询慢：每次查询元素都需要从链表头或链表尾部开始遍历查询。

索引决定了是从链表头还是链表尾部开始查询

如果索引大于等于元素个数的一半，从链表尾部开始查询，否则从链表头开始查询

红黑树 ==> 树 ==> 二叉树

红黑树

二叉树：binary tree ,是每个结点不超过2的有序树（tree）

简单的理解，就是一种类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点

二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”

我们要说的是二叉树的一种比较有意思的叫做红黑树，红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的