Java 自學筆記 04 - List & Queue

發表於 分類於 閱讀次數： 文章字數： 888 所需閱讀時間 ≈ 4 分鐘

Collection

Collection 是 Java 中用來存儲、操作數據結構的一種框架，在此之下提供了許多實用的 Interface，包括 List、Queue 以及 Set (Map 是分開的)。

Java Collection

List

List 基本上就是動態數組，其下有 ArrayList、LinkedList、Vector 等不同的實現。

Java List Interface

  • ArrayList: 透過索引訪問的動態陣列，查尋的時間複雜度為 O(1)，然而插入時會將後面的元素全部往右移 (刪除時則是全部往左移)，因此時間複雜度最差為 O(n)。適合用在隨機查找、頻繁訪問及更新的資料上。
  • LinkedList: 透過雙向鏈結實現的動態陣列，插入與刪除的效率高，操作本身的時間複雜度為 O(1)，但查找時需要遍歷整個鏈表，因此時間複雜度最差為 O(n)。適用於需要大量插入和刪除操作的情況。

Vector 是老舊的語法，透過 synchronized 同步以實現線程安全，性能不佳，大多時候都可以被 ArrayList 取代掉，兩者的用法幾乎一模一樣。

Array to ArrayList

Arrays.asList() 可以將 Array 轉換為 java.util.Arrays.ArrayList，與 collections 中所指的 ArrayList 並不一樣，轉換而成的 ArrayList 並不能進行添加或刪除的操作。

1
2
List<String> names = Arrays.asList("Sandy", "Jack");
// names.add("Frank"); // 還是可以 compile，但執行會報錯

Basic Usage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<String> list = new ArrayList<>(); // Interface<Object>
// List<String> list = new LinkedList<>(); 
list.add("Jack");
list.add("Emma");
list.add("Jack");
list.addAll(names);
System.out.println(list); // [Jack, Emma, Jack, Sandy, Jack]

list.get(0); // Jack
list.indexOf("Jack"); // 0
list.size(); // 5
list.isEmpty(); // false

list.set(0, "Timmy");
System.out.println(list);  // [Timmy, Emma, Jack, Sandy, Jack]

list.remove(0); // remove(index): return element or throw exception
list.remove("Jack"); // remove(Object): return True or False
System.out.println(list);  // [Emma, Sandy, Jack]

list.removeIf(x->x.contains("J"));
System.out.println(list);  // [Emma, Sandy]

list.clear();

Queue

Queue 是一個先進先出 (FIFO) 的資料集合，其下大致上可以分為 Deque 及 Priority Queue 兩類，Deque 有 ArrayDeque、LinkedList 等實現，Priority Queue 的實現則是 PriorityQueue。
Java Queue Interface

  • LinkedList: 前面就提到過了，雙向鏈結的特性使其能夠快速地對頭尾元素進行操作。
  • ArrayDeque: 同時有 Deque 以及 Array 的性質，能快速地訪問元素，也可以快速地對頭尾元素進行操作。
  • PriorityQueue: 其實就是 Min Heap。

Deque

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
Deque<Integer> deque = new LinkedList<>();
// Deque<Integer> deque = new ArrayDeque<>();

// add from first
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);

// add from last
deque.addLast(4);
deque.addLast(5);
deque.addLast(6);

System.out.println(deque);  // [3, 2, 1, 4, 5, 6]

// get from first
deque.getFirst();           // return 3
System.out.println(deque);  // [3, 2, 1, 4, 5, 6]

// get from last
deque.getLast();            // return 6
System.out.println(deque);  // [3, 2, 1, 4, 5, 6]

// remove from first
deque.removeFirst();        // return 3
System.out.println(deque);  // [2, 1, 4, 5, 6]

// remove from last
deque.removeLast();         // return 6
System.out.println(deque);  // [2, 1, 4, 5]

Priority Queue

將 pq 印出來會發現最小值永遠在第一個，後面順序則不一定，有興趣可以自己去看 heap 的規則。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Queue<Integer> pq = new PriorityQueue<>();

for (int i=7; i>0; i--){
    pq.offer(i);        // similar to pq.add()
}
System.out.println(pq); // [1, 4, 2, 7, 5, 6, 3]

// get first one
pq.peek();
System.out.println(pq); // [1, 4, 2, 7, 5, 6, 3]

// remove first one
pq.poll();
System.out.println(pq); // [2, 4, 3, 7, 5, 6]

But！都用到 PriorityQueue 了，肯定不只是拿來處理這麼簡單的任務，通常會儲存一組資料，例如 "apple", 2、"banana", 3 等，這時候 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
37
38
// Self-defined Class
class Pair{
    String first;
    int second;

    Pair(String first, int second){
        this.first = first;
        this.second = second;
    }
}

// Self-defined Comparator
Comparator<Pair> customComparator = new Comparator<>() {
    @Override
    public int compare(Pair p1, Pair p2) {
        // compare with second element
        return Integer.compare(p1.second, p2.second);
    }
};

// initialize PriorityQueue with Comparator
PriorityQueue<Pair> pq2 = new PriorityQueue<>(customComparator);

// offer
pq2.offer(new Pair("apple", 2));
pq2.offer(new Pair("banana", 3));
pq2.offer(new Pair("cherry", 1));

// poll
while (!pq2.isEmpty()) {
    Pair pair = pq2.poll();
    System.out.println("(" + pair.first + ", " + pair.second + ")");
}

// result
// (cherry, 1)
// (apple, 2)
// (banana, 3)