本文总结java中常见的数据结构实现以及相关常用API，不再介绍各种结构的基础用法(栈后进先出、队列先进先出等等)，直接总结常用API
在写算法时，选用合适的数据结构和API可以大大降低计算工序，不知道相关数据结构怎么用，就算有思路也不知道怎么用代码写出来
数组
数组可以说是常用的一种数据结构了，Java提供了一些常用的API方法来操作数组。
以下是一些常用的数组API
Arrays类
Java中的Arrays类提供了一系列静态方法来操作数组，包括排序、搜索、比较等功能
Arrays.sort();
Arrays.sort()方法使用的是经过优化的快速排序算法，平均时间复杂度为O(nlogn)，最坏情况下是数组已经有序，时间复杂度为O(n^2)
作为比较常用的API，一定对平均复杂度有所了解，API不是万能的，要根据场景使用
int[] arr = new int[]{2, 6, 8, 7, 10};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr)); // [2, 6, 7, 8, 10]
Arrays.binarySearch()
Arrays.binarySearch()方法使用的是二分查找算法。这个算法要求被搜索的数组必须是有序的
时间复杂度为O(logn)
数组一定是排好序的，否则会出错
int[] arr = new int[]{2, 6, 8, 7, 10};
int index = Arrays.binarySearch(arr, 6);
System.out.println(index); // 1
如果找到要搜索的元素，则返回该元素的索引
如果找不到要搜索的元素，则返回一个负数值，表示该元素应该插入的位置的负数值减一
Arrays.equals()
Arrays.equals()方法用于比较两个数组是否相等，数组是地址传递，不能用==判断
boolean result = Arrays.equals(array1, array2);
如果两个数组在相同位置上的元素都相等，并且两个数组的长度也相等，则返回true，否则返回false
在最坏情况下，时间复杂度为O(n)，其中n是要比较的数组的长度。因为在比较两个数组时，需要逐个比较它们的元素
Arrays.fill()
Arrays.fill()方法用于将数组中的所有元素都设置为指定的值
Arrays.fill(array, value);
array是要填充的数组，value是要设置的值。调用该方法后，数组中的所有元素都会被设置为指定的value
时间复杂度为O(n)，其中n是数组的长度，需要遍历整个数组，并将每个元素设置为指定的值
Arrays.copyOf()
Arrays.copyOf()方法用于将一个数组复制到一个新的数组中，并可以指定新数组的长度
int[] newArray = Arrays.copyOf(originalArray, newLength);
originalArray：要复制的原始数组newLength：新数组的长度调用该方法后，将原始数组中的元素复制到一个新数组中，并返回这个新数组。如果新数组的长度大于原始数组的长度，则新数组的末尾会用默认值填充
时间复杂度取决于新数组的长度，即为O(n)
Arrays.copyOfRange()
Arrays.copyOfRange()方法用于将一个数组的指定范围内的元素复制到一个新的数组中
int[] newArray = Arrays.copyOfRange(originalArray, from, to);
originalArray：要复制的原始数组from：要复制的起始索引（包含）to：要复制的结束索引（不包含）调用该方法后，将原始数组中从起始索引from（包含）到结束索引to（不包含）的元素复制到一个新数组中，并返回这个新数组
时间复杂度取决于要复制的元素数量，即为O(to−from)
Arrays.toString()
Arrays.toString()方法用于将数组转换为字符串形式，以便于打印或输出
String arrayString = Arrays.toString(array);
调用该方法后，数组中的元素会以逗号分隔的形式转换为一个字符串，并返回这个字符串
时间复杂度O(n)
Arrays.asList()
Arrays.asList()方法用于将数组转换为List集合
List
调用该方法后，数组中的元素会被转换为一个List集合，并返回这个List
时间复杂度为O(n)，n是数组的长度，需要遍历数组中的每个元素，并将其添加到List集合中
链表
Java中链表用LinkedList集合类来实现
LinkedList是双向链表实现的列表，适用于频繁插入和删除元素的场景
插入和删除元素的效率高，但随机访问元素效率较低（链表通病）
实现了List和Deque接口，支持队列和栈操作（可以当栈和队列使用）
添加元素
linkedList.add("A"); // 在链表末尾添加元素
linkedList.addFirst("B"); // 在链表开头添加元素
linkedList.addLast("C"); // 在链表末尾添加元素
linkedList.add(index, "D"); // 在指定位置添加元素
获取元素
String firstElement = linkedList.getFirst(); // 获取第一个元素
String lastElement = linkedList.getLast(); // 获取最后一个元素
String element = linkedList.get(index); // 获取指定位置的元素
删除元素
linkedList.removeFirst(); // 删除第一个元素
linkedList.removeLast(); // 删除最后一个元素
linkedList.remove(element); // 删除指定元素
linkedList.remove(index); // 删除指定位置的元素
其他常用操作
int size = linkedList.size(); // 获取链表大小
boolean isEmpty = linkedList.isEmpty(); // 判断链表是否为空
boolean contains = linkedList.contains("A"); // 判断链表是否包含指定元素
int index = linkedList.indexOf("B"); // 获取指定元素的索引
链表没有什么花里胡哨的API，只要熟悉常用操作就能解题
哈希表
哈希表都是用来快速判断一个元素是否出现集合里，数组也算一个哈希表
其他常用的有HashSet(集合)、ArrayList(动态数组)、HashMap(映射)
HashSet
HashSet是基于哈希表实现的Set集合，特点有元素唯一、无序、基于哈希表
常见的应用场景有：去重、快速查找、缓存数据
代码实现
// 用HashSet得导包
import java.util.HashSet;
// T是泛型，替换为想要保存的值类型 不能保存不同类型的值
HashSet
常用API
HashSet没有什么花哨的API，合适的场景选用可以大幅度提高效率
add(element)：向集合中添加元素remove(element)：从集合中移除指定元素contains(element)：判断集合中是否包含指定元素size()：返回集合中元素的个数isEmpty()：判断集合是否为空clear()：清空集合中的所有元素iterator()：返回集合的迭代器，可以用于遍历集合中的元素HashMap
HashMap实现了Map接口，提供了键值对的存储和检索
应用场景有：
缓存： 将数据以键值对的形式缓存起来，方便快速检索和访问数据索引： 可以根据键值对结构快速查找数据数据映射： 把不同类型的数据进行映射存储常用API
put(key, value): 将指定的键值对存储到HashMap中get(key): 返回与指定键关联的值getOrDefault(key, defaultValue): 获取指定键对应的值 如果该键不存在则返回一个默认值containsKey(key): 判断HashMap中是否包含指定的键containsValue(value): 判断HashMap中是否包含指定的值remove(key): 从HashMap中移除指定键及其关联的值size(): 返回HashMap中键值对的个数isEmpty(): 判断HashMap是否为空clear(): 清空HashMap中的所有键值对keySet(): 返回HashMap中所有键的集合values(): 返回HashMap中所有值的集合entrySet(): 返回HashMap中所有键值对的集合ArrayList
ArrayList是Java中常用的动态数组实现，实现了List接口，可以根据需要动态增加或减少元素的大小
应用场景：
需要动态调整大小的数组需要按索引访问元素需要保持元素插入顺序：ArrayList会按照元素插入的顺序进行存储常用API
add(element): 向ArrayList末尾添加元素add(index, element): 在指定位置插入元素get(index): 获取指定位置的元素set(index, element): 替换指定位置的元素remove(index): 移除指定位置的元素remove(element): 移除指定元素size(): 返回ArrayList中元素的个数isEmpty(): 判断ArrayList是否为空contains(element): 判断ArrayList是否包含指定元素indexOf(element): 返回指定元素在ArrayList中第一次出现的位置clear(): 清空ArrayList中的所有元素字符串
字符串是最常用的类型之一了，Java中有不少字符串的处理方法和API
但是也有很多场景需要用到专门用来处理字符串的类StringBuilder
简单提一句StringBuilder和StringBuffer的区别，StringBuffer是线程安全的、StringBuilder是非线程安全的。不需要深入了解线程安全是什么，只需要知道在写算法题时使用StringBuilder速度更快，选它就对了！
字符串常用方法
在算法题中要尽量避免频繁切割字符串，字符串是不可变类型，每一次操作都会生成新的字符串，造成性能浪费
length(): 返回字符串的长度charAt(int index): 返回指定位置的字符indexOf(String str): 返回指定子字符串第一次出现的位置lastIndexOf(String str): 返回指定子字符串最后一次出现的位置substring(int beginIndex): 返回从指定位置开始到末尾的子字符串substring(int beginIndex, int endIndex): 返回指定范围内的子字符串toUpperCase(): 将字符串转换为大写toLowerCase(): 将字符串转换为小写equals(Object obj): 比较字符串内容是否相同equalsIgnoreCase(String anotherString): 忽略大小写比较字符串内容是否相同contains(CharSequence s): 判断字符串是否包含指定字符序列replace(char oldChar, char newChar): 替换字符串中指定字符replaceAll(String regex, String replacement): 使用给定的字符串替换此字符串所有匹配给定的正则表达式的子字符串split(String regex): 根据给定正则表达式拆分字符串为字符串数组StringBuilder
StringBuilder是专门用来操作字符串的类，通常在需要频繁进行字符串拼接或修改的情况下使用，不同于String类型的不可变，StringBuilder是可变的字符串，可以在原字符串基础上进行修改，避免频繁创建新的String对象，提高了性能
所以，当需要进行大量的字符串拼接、插入、删除等操作(尤其是在循环中)时 可以考虑使用StringBuilder
常用API
append(String str): 在字符串末尾追加指定字符串insert(int offset, String str): 在指定位置插入字符串delete(int start, int end): 删除指定范围内的字符deleteCharAt(int index): 删除指定位置的字符replace(int start, int end, String str): 替换指定范围内的字符substring(int start): 返回从指定位置开始到末尾的子字符串substring(int start, int end): 返回指定范围内的子字符串reverse(): 反转字符串length(): 返回字符串的长度charAt(int index): 返回指定位置的字符indexOf(String str): 返回指定字符串第一次出现的位置lastIndexOf(String str): 返回指定字符串最后一次出现的位置栈
可以使用java.util.Stack类或者java.util.Deque接口的实现类java.util.ArrayDeque来实现栈
两者核心API上没有什么区别，java.util.Stack是线程安全的，因为它继承了Vector类
java.util.ArrayDeque不是线程安全的，还是一样 写算法题无脑用ArrayDeque就行了
栈的相关API都很简单，要在合适的场景去使用
java.util.Stack类
push(E item): 将元素压入栈顶pop(): 弹出栈顶元素peek(): 查看栈顶元素但不移除empty(): 判断栈是否为空search(Object o): 查找元素在栈中的位置Stack
stack.push(1);
stack.push(2);
int topElement = stack.pop();
int peekElement = stack.peek();
boolean isEmpty = stack.empty();
int index = stack.search(1);
java.util.ArrayDeque
ArrayDeque是一个双端队列，通过其丰富的API，可以实现栈
作为栈时，常用操作：
push(E e): 压栈，将元素压入栈顶，等效于addFirst(E e)pop(): 弹栈，弹出栈顶元素并移除，等效于removeFirst()peek(): 查看栈顶元素但不移除，等效于peekFirst()isEmpty(): 判断栈是否为空添加元素：
addFirst(E e): 在双端队列的开头添加元素addLast(E e): 在双端队列的末尾添加元素offerFirst(E e): 在双端队列的开头添加元素，如果成功返回true，否则返回falseofferLast(E e): 在双端队列的末尾添加元素，如果成功返回true，否则返回false获取并移除元素：
removeFirst(): 获取并移除双端队列的第一个元素removeLast(): 获取并移除双端队列的最后一个元素pollFirst(): 获取并移除双端队列的第一个元素，如果双端队列为空返回nullpollLast(): 获取并移除双端队列的最后一个元素，如果双端队列为空返回null获取但不移除元素：
getFirst(): 获取但不移除双端队列的第一个元素getLast(): 获取但不移除双端队列的最后一个元素peekFirst(): 获取但不移除双端队列的第一个元素，如果双端队列为空返回nullpeekLast(): 获取但不移除双端队列的最后一个元素，如果双端队列为空返回null队列
队列可以通过使用java.util.Queue接口的实现类来实现
常用的队列实现类包括java.util.LinkedList和java.util.ArrayDeque
java.util.LinkedList是基于双向链表实现的，每个元素都包含对前一个和后一个元素的引用
java.util.ArrayDeque是基于数组实现的双端队列，可以在队列的两端进行高效的插入和删除操作
在大多数情况下，java.util.ArrayDeque的性能比java.util.LinkedList更好，因为数组结构的访问速度更快。
java.util.LinkedList在插入和删除元素时可能会更慢，因为需要调整链表中的指针
java.util.LinkedList
添加元素：
add(E e): 将元素添加到链表的末尾addFirst(E e): 将元素添加到链表的开头addLast(E e): 将元素添加到链表的末尾offer(E e): 将元素添加到链表的末尾，如果成功返回true，否则返回false获取并移除元素
remove(): 获取并移除链表的第一个元素removeFirst(): 获取并移除链表的第一个元素removeLast(): 获取并移除链表的最后一个元素poll(): 获取并移除链表的第一个元素，如果链表为空返回null获取但不移除元素：
getFirst(): 获取链表的第一个元素getLast(): 获取链表的最后一个元素peek(): 获取链表的第一个元素，如果链表为空返回null其他常用方法：
size(): 返回链表中的元素个数isEmpty(): 判断链表是否为空clear(): 清空链表中的所有元素iterator(): 返回链表的迭代器，可以用来遍历链表中的元素java.util.ArrayDeque
添加元素：
add(E e): 将元素添加到队列的末尾，等效于offerLast(E e)offer(E e): 将元素添加到队列的末尾，如果成功返回true，否则返回falseofferLast(E e): 将元素添加到队列的末尾，如果成功返回true，否则返回false获取并移除元素：
remove(): 获取并移除队列的头部元素，等效于pollFirst()poll(): 获取并移除队列的头部元素，如果队列为空返回nullpollFirst(): 获取并移除队列的头部元素，如果队列为空返回null获取但不移除元素：
element(): 获取但不移除队列的头部元素，如果队列为空则抛出异常，等效于peekFirst()peek(): 获取但不移除队列的头部元素，如果队列为空返回nullpeekFirst(): 获取但不移除队列的头部元素，如果队列为空返回null其他常用方法：
size(): 返回队列中的元素个数isEmpty(): 判断队列是否为空clear(): 清空队列中的所有元素