干货：Java数据结构与算法汇总学习

一、数据结构概述

当你用着java里面的容器类很爽的时候，你有没有想过，怎么ArrayList就像一个无限扩充的数组，也好像链表之类的，好用吗？很好用，这就是数据结构的好处，只不过你在不知不觉中使用了。

现实世界的存储，我们使用的工具和建模，每种数据结构有自己的优点和缺点，想想如果Google的数据用的是数组的存储，我们还能方便的查询到所需要的数据吗？而算法在这么多的数据中如何做到最快的插入、查找、删除，也是在追求更快

Java是面向对象的语言，就好比自动档轿车，C语言好比手动档吉普，数据结构呢？是变速箱的工作原理，你完全可以不知道变速箱是怎样工作的，就把自动档的车子从A点开到B点，而且未必就比懂得人慢，写程序这件事，和开车一样，经验可以起到很大的作用，但是如果你不知道底层是怎样工作的，就永远只能开车，既不会修车，也不会造车，所以我们还是要学一些常见的数据结构：堆栈、队列、数组、链表和红黑树。

二、数据结构：栈

栈：stack，又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

简单地说，采用该结构的集合，对元素的存取有以下特点：

先进后出（即，存进去的元素，要在它的元素依次取出后，才能取出该元素）

栈的出口和入口都是栈的顶端位置【栈顶】

三、数据结构：队列

队列：queue。简称队，它和堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

简单地说，采用该结构的集合，对元素的存取有如下的特点：

先进先出（即，存进去的元素，要在它的元素依次取出后，才能取出该元素）

队列的入口、出口各占一侧

三、数据结构：数组

数组：Array，是有序的元素序列，数组是在内存中开辟一片连续的空间，并在此空间存放元素，并且每一个空间都有对应的编号【下标】。

简单的说，采用该结构的集合，对元素的存取有以下的特点：

查找元素快：通过索引，可以快速访问指定位置的元素

增删元素慢：数组的长度是固定的，想要增加/删除一个元素，必须创建一个新数组，把源数组的数据复制过来

四、数据结构：链表

链表：LinkedList，由一系列节点node【链表中每一个元素】组成，节点可以在运行时动态生成，每个节点包括两部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域，我们常说的链表结构有单向链表和双向链表

单向链表：

双向链表：

简单地说，采用该数据结构的集合，对元素的存取有以下的特点：

多个节点之间，通过地址进行连接

查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素

增删元素快：增删元素，只需要修改连接下个元素的地址即可

五、二叉树

1、二叉树概述

二叉树：binary tree，是每个节点不超过2的有序树简单的理解就是一种类似于我们生活中树的结构，只不过每个节点上都最多只能有两个子节点

二叉树是每个节点最多有两个子树的树结构，顶上的叫根节点，两边被称之为和

2、排序树

左子树数据比右子树数据小，

比如，查询以下数字3，4为中间值，3小于4，舍去右子树6，3大于2，舍去左子树1，获取3

3、平衡树

平衡树：左子树和右子树相等

4、不平衡树

不平衡树：左子树不等于右子树

5、红黑树

红黑树：趋近于平衡树，查询的速度非常快，查询叶子节点最大次数和最小次数不能超过2倍

特点：

节点可以是红色或者黑色

根节点是黑色

空节点是黑色

每个红色节点的子节点是黑色

任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同