Java算法中常用的数据结构

1.1 写在前面的话

大家好，我是技术宅星云，这篇文章给大家分享下java算法中常用的数据结构。

我们都知道,Java 是一个面向对象的高级语言, 它内置了几种常用的数据结构类型，像我们大学C语言基础课程中所学到的 数组(array), 链表（list）, 队列（Queue ），栈（stack）等。

但在Java中，万事万物皆为对象，为了更方便，更简单容易地使用这些数据结构，Java 又将这几种内置的数据结构封装成了类（比如ArrayList,HashMap,LinkedList 等），屏蔽了底层实现的复杂性。

也许对于初级和中级工程师来说，只需要会调用这些封装好的数据结构类即可，但是对于高级工程师来说，却应该去了解下这些内置的数据结构，这样的好处是可以知其然并知其所以然。

在一些比较复杂的业务场景下，如果我们对这些数据结构类的底层实现有所了解，将有助于我们更好更恰当地使用这些数据结构。

1.2 Java算法中常用的数据结构

1.2.1 数组

1.2.2 字符串

1.2.3 动态数组

1.2.4 双向链表 LinkedList

1.2.5 哈希表 HashMap

1.2.6 哈希集合 HashSet

1.2.7 队列 Queue

1.2.8 堆栈 Stack

1.2.9 二叉树

1.2.10 单链表

1.2.1  数组

初始化方法

Java中的这种数组类似C语言中的数组，在有的题目中会以函数参数的形式传，一般来说要在函数开头做一个非空检查，然后用索引下标访问其中的元素。

1.2.2 字符串 String

Java的字符串处理起来很麻烦，因为它不支持用[]直接访问其中的字符，而且不能直接修改，要转换成char[]类型后才能修改。

字符串可以用加号进行拼接

Java的字符串不能直接修改，要用toCharArray 转化成char[]类型的数组后进行修改，然后转换回String类型。

另外，虽然字符串支持用+进行拼接，但是效率并不高，不建议在for循环中使用。如果需要进行频繁的字符串拼接，推荐单线程环境下使用`StringBuilder`，多线程环境下使用`StringBuffer`.

1.2.3 动态数组ArrayList

类似C++ 的vector 容器，ArrayList 相当于把Java内置的数组类型做了包装初始化方法：

值得注意的是，如果我们看过源码了解ArrayList 使用内置数据结构的代码封装逻辑，就会明白，在初始化的时候如果知道会存多少条数据，那么最好指定下初始化扩容大小，避免代码运行过程中频繁调整数组大小，造成额外开销。

上面代码优化后就变成了这样：

ArrayList 默认初始化大小是16, 这个值最好根据实际情况设值。

常用方法（E 代表元素类型):

1.2.4 双向链表 LinkedList

ArrayList 列表底层是用数组实现的，而LinkedList 底层是用双链表实现的，初始化方法也是类似的，初始化方法也是类似的。

其中只有contains 方法的时间复杂度是O(N),因为必须遍历整个链表才能判断元素是否存在。

1.2.5 哈希表 HashMap

初始化方法

K 代表键的类型，V代表值的类型。

1.2.6 哈希集合 HashSet

1.2.7 队列 Queue

Queue 是一个接口,比如新建一个存储String的队列如下：

1.2.8 堆栈 Stack

1.2.9 二叉树

在Java中，如果想定义一个二叉树，那么需要编码如下：

一般的使用方法是：

以上操作图形化示意图如下：

注意：其中2 是根节点存储的值，4 是左子树节点的值，6 是右子树节点的值。

根据node1.val=10; 命令执行后便将根结点的值从2 变成了10.

1.2.10 单链表

ListNode 是单链表节点类型，其结构定义如下：

一般的使用用法是：

以上代码图形化示意图如下：

node1.val=9; 将 根结点的值从1 变成了9