JAVA常用数据结构
pu Lv999
  2022-04-03 18:32:25 2022-04-03 18:32   2023-06-04 15:31:20      1.5k 字  7 分钟  

本文整理了Java语言的常用数据结构，方便刷题/面试时使用。

image
容器 对应数据结构
List 变长数组
Queue 队列
PriorityQueue 堆
Stack 栈
Deque 双端队列
Set 集合
Map 键值表
Pair 元素对

List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void testArrayList() {
        System.out.println("------ArrayList Start------");
        // 定义 ArrayList
        // 定义一个空 ArrayList
        List<Integer> a = new ArrayList<>();
        // 定义一个空 ArrayList，初始容量为3
        List<Integer> b = new ArrayList<>(3);
        // 定义一个包含元素1,2,3 的 ArrayList
        ArrayList<Integer> c = new ArrayList<>(Arrays.asList(1, 2, 3));

        // 遍历 ArrayList
        for (int i = 0; i < c.size(); i++)
            System.out.print(c.get(i) + " ");
        System.out.println();
        for (int x : c)
            System.out.print(x + " ");
        System.out.println();

        // 获取 ArrayList 第一个和最后一个元素
        System.out.println(c.get(0)); // 第一个元素：c[0]常用
        System.out.println(c.get(c.size() - 1)); // 最后一个元素

        // 在 ArrayList 尾部添加、删除元素
        c.add(4);
        c.remove(c.size() - 1);
        c.remove(c.size() - 1);
        System.out.println(c.size()); // 2

        // 清空 ArrayList
        c.clear();
        System.out.println(c.size()); // 0

        // ArrayList 之间的比较需要自己实现
        System.out.println("------ArrayList End------");

    }

Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void testQueue() {
    System.out.println("------Queue Start------");
    // 定义q 不是new Queue, 而是LinkedList
    Queue<Integer> q = new LinkedList<>();
    // 入队、出队 不建议使用add/remove(插入失败会报异常) 建议使用offer/poll
    q.offer(1); // 1
    q.offer(2); // 1 2
    q.offer(3); // 1 2 3
    q.offer(4); // 1 2 3 4
    q.poll(); // 2 3 4
    // 获取队头元素 不建议使用element 建议使用peek
    System.out.println(q.peek());
    System.out.println(q.size());
    // 遍历队列
    for (int i : q) {
        System.out.println(i);
    }
    // 清空队列
    q.clear();
    System.out.println(q.isEmpty());
    System.out.println("------Queue End------");
}

PriorityQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void testPriorityQueue() {
    System.out.println("------PriorityQueue Start------");
    // 注意声明的方式
    Queue<Integer> q1 = new PriorityQueue<>(); // 小根堆
    Queue<Integer> q2 = new PriorityQueue<>(((o1, o2) -> o2 - o1)); // 大根堆
    class Rec implements Comparable<Rec> {
        int x, y;

        Rec(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Rec o) {
            return this.x - o.x;
        }

        @Override
        public String toString() {
            return "Rec{" + "x=" + x + ", y=" + y + '}';
        }
    }
    Queue<Rec> q3 = new PriorityQueue<>();
    q3.offer(new Rec(1, 2));
    q3.offer(new Rec(6, 7));
    q3.offer(new Rec(5, 4));
    q3.offer(new Rec(3, 9));
    // 删除堆顶元素
    q3.poll();
    System.out.println("堆顶: " + q3.peek());
    for (Rec i : q3) {
        System.out.println(i);
    }
    System.out.println("------PriorityQueue End------");
}

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void testStack() {
    System.out.println("------Stack Start------");
    // Stack 推荐使用Deque实现 两者API完全一致
    Deque<Integer> stk = new ArrayDeque<>();
    stk.push(1); // 1
    stk.push(2); // 1 2
    stk.push(3); // 1 2 3
    stk.push(4); // 1 2 3 4
    stk.pop(); // 1 2 3
    // 栈顶元素 此时为3
    System.out.println(stk.peek());
    System.out.println(stk.size());
    // 从栈顶向栈底遍历
    for (int i : stk) {
        System.out.println(i);
    }
    stk.clear();
    System.out.println(stk.isEmpty());
    System.out.println("------Stack End------");
}

Deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void testDeque() {
    System.out.println("------Deque Start------");
    // Stack 推荐使用Deque实现 两者API完全一致
    Deque<Integer> d = new ArrayDeque<>();
    d.addLast(1); // 1
    d.addLast(2); // 1 2
    d.addFirst(3); // 3 1 2
    d.addFirst(4); // 4 3 1 2
    d.removeFirst(); // 3 1 2
    // 返回队头元素
    System.out.println(d.getFirst());
    // 返回队尾元素
    System.out.println(d.getLast());
    System.out.println(d.size());
    d.clear();
    System.out.println(d.isEmpty());
    System.out.println("------Deque End------");
}

Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public static void testSet() {
    System.out.println("------Set Start------");

    /**
     * LinkedHashSet 按照插入顺序 
     * TreeSet 按照元素自然顺序 要求元素具备Comparator方法 
     * HashSet 无序
     */

    /**
     * LinkedHashSet 链表实现
     */
    LinkedHashSet<Integer> ls = new LinkedHashSet<>();
    ls.add(4);
    ls.add(5);
    ls.add(1);
    for (int i : ls) {
        System.out.print(i + " ");
    }
    System.out.println();

    /**
     * TreeSet 红黑树实现
     */
    TreeSet<Integer> ts = new TreeSet<>();
    ts.add(4);
    ts.add(5);
    ts.add(1);
    // 自动排序
    for (int i : ts) {
        System.out.print(i + " ");
    }
    System.out.println();
    // 排序后的第一个元素
    System.out.println(ts.first());
    // 排序后的最后一个元素
    System.out.println(ts.last());
    // 判断存在某个元素
    System.out.println(ts.contains(3));
    // ceiling/higher
    System.out.println(ts.ceiling(4)); // 返回大于等于4的最小元素: 4
    System.out.println(ts.higher(4)); // 返回大于4的最小元素: 5
    // floor/lower
    System.out.println(ts.floor(4)); // 返回小于等于4的最大元素: 4
    System.out.println(ts.lower(4)); // 返回小于4的最大元素: 1

    /**
     * HashSet 哈希表实现
     */
    HashSet<Integer> hs = new HashSet<>();
    hs.add(12);
    hs.add(4);
    hs.add(5);
    hs.add(69);
    hs.add(9);
    // 移除元素     
    hs.remove(5); 
    // 可以看出其输出是无序的
    for (int i : hs) {
        System.out.print(i + " ");
    }
    System.out.println();

    System.out.println("------Set End------");
}

Map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void testMap() {
    System.out.println("------Map Start------");
    /**
     * TreeMap 有序的Map
     */
    TreeMap<String, Integer> tm = new TreeMap<>();
    tm.put("tm4", 4);
    tm.put("tm3", 3);
    tm.put("tm2", 2);
    tm.put("tm1", 1);
    tm.remove("tm2");
    // 自动排序
    for (String key : tm.keySet()) {
        System.out.println(tm.get(key));
    }
    System.out.println(tm.firstEntry());
    System.out.println(tm.lastEntry());
    System.out.println(tm.containsKey("tm1"));
    System.out.println(tm.containsValue(1));
    System.out.println();

    /**
     * HashMap 无序的Map
     */
    HashMap<String, Integer> hm = new HashMap<>();
    hm.put("hm4", 4);
    hm.put("hm3", 3);
    hm.put("hm2", 2);
    hm.put("hm1", 1);
    hm.remove("hm2");
    for (String key : hm.keySet()) {
        System.out.println(hm.get(key));
    }
    System.out.println(hm.containsKey("hm1"));
    System.out.println("------Map End------");
}

Pair

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void testPair() {
    System.out.println("------Pair Start------");
    // 通常建议自己手写一个Pair类

    class Pair implements Comparable<Pair> {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Pair o) {
            if (x != o.x) return x - o.x;
            else return y - o.y;
        }
        @Override
        public String toString() {
            return "x: " + x + " y: " + y;
        }
    }

    Pair a = new Pair(1, 2);
    Pair b = new Pair(1, 3);
    Pair c = new Pair(2, 4);
    List<Pair> pairList = new ArrayList<>();
    pairList.add(c); pairList.add(b); pairList.add(a);
    for (Pair p : pairList) {
        System.out.println(p);
    }
    Collections.sort(pairList);
    System.out.println();
    for (Pair p : pairList) {
        System.out.println(p);
    }

    System.out.println("------Pair End------");

}
  • 本文标题：JAVA常用数据结构
  • 本文作者：pu
  • 创建时间：2022-04-03 18:32:25
  • 本文链接：2022/04/03/JAVA常用数据结构/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  1. 1. List
  2. 2. Queue
  3. 3. PriorityQueue
  4. 4. Stack
  5. 5. Deque
  6. 6. Set
  7. 7. Map
  8. 8. Pair