基于 Java 的数据结构和算法 (不定期更新）

JavaIsBestLang

数据结构

Collection 是 Java 中的接口，被多个泛型容器接口所实现。在这里，Collection 是指代存放对象类型的数据结构。

ArrayList

函数名	功能
size()	返回 this 的长度
add(Integer val)	在 this 尾部插入一个元素
add(int idx, Integer e)	在 this 指定位置插入一个元素
get(int idx)	返回 this 中第 idx 位置的值，若越界则抛出异常
set(int idx, Integer e)	修改 this 中第 idx 位置的值
clear()
isEmpty()
contains()
remove(int index) or remove(Object o)

初始化

List<Integer> list1 = new LinkedList<>();  // 创建一个名字为 list1 的双链表 
List<Integer> list2 = new LinkedList<>(list1);  // 创建一个名字为 list2 的双链表，将 list1 内所有元素加入进来 

// 二维数组
List<Integer>[] ans = new ArrayList[11];
Arrays.setAll(ans, i->new ArrayList<>());

Queue

Queue<Integer> q = new ArrayDeque<>();

操作	抛出异常	返回特殊值
插入	add()	offer()
删除	remove()	poll()
查询	element()	peek()

Deque

Deque 是 Java 中的双端队列，我们通常用其进行队列的操作以及栈的操作。

函数名	功能
push(Integer val)	将一个元素从队头加入this，等效于addFirst
pop()	将队头元素删除，等效于removeFirst
addFirst(Integer val)	将一个元素从队头加入this
removeFirst()	将队头元素删除，并返回该元素
addLast(Integer val)	将一个元素从队尾加入this
removeLast()	将队尾元素删除，并返回该元素
offerFirst(Integer val)	将一个元素从队头加入this
pollFirst()	将队头元素删除，并返回该元素
offerLast(Integer val)	将一个元素从队尾加入this
pollLast()	将队尾元素删除，并返回该元素
add(Integer val)	将一个元素从队尾加入this
offer(Integer val)	将一个元素从队尾加入this
poll()	将队头元素删除，并返回该元素
remove()	将队头元素删除，并返回该元素
peekFirst()	返回队头元素
peekLast()	返回队尾元素

add、remove 操作在遇到异常时会抛出异常，而offer、 poll 不会抛出异常。

栈的操作

import java.util.ArrayDeque;
import java.util.Deque;public class Main {static Deque<Integer> stack = new ArrayDeque<>();static int[] a = {1, 2, 3, 4, 5};public static void main(String[] args) {for (int v : a) {stack.push(v);}while (!stack.isEmpty()) { //输出 5 4 3 2 1System.out.println(stack.pop()); }}
}

双端队列的操作

import java.util.ArrayDeque;
import java.util.Deque;public class Main {static Deque<Integer> deque = new ArrayDeque<>();static void insert() {deque.addFirst(1);deque.addFirst(2);deque.addLast(3);deque.addLast(4);}public static void main(String[] args) {insert();while (!deque.isEmpty()) { //输出 2 1 3 4System.out.println(deque.poll());}insert();while (!deque.isEmpty()) { //输出 4 3 1 2System.out.println(deque.pollLast());}}
}

Arrays

• Arrays.sort()
• Arrays.fill()
• Arrays.binarySearch()

字符串

1.StringBuilder

可看作一个容器，创建之后里面内容可变，大大提高字符串操作效率

方法

• append()
• length()
• toString()
• reverse()

public class StringDemo {public static void main(String[] args) {StringBuilder sb = new StringBuilder("afaf");System.out.println(sb);// 添加sb.append("abab");sb.append(3.14);sb.append("aa").append("bb");System.out.println(sb);// 反转sb.reverse();System.out.println(sb);// 获取长度System.out.println(sb.length());// 变为 StringString str = sb.toString();System.out.println(str);}}