Java LinkedList

LinkedList 是雙向鏈結串列的實作，同時實作了 List 和 Deque 介面，適合頻繁的插入和刪除操作。

引入套件

import java.util.LinkedList;

建立 LinkedList

// 空的 LinkedList
LinkedList<String> list1 = new LinkedList<>();

// 從其他集合建立
List<String> source = Arrays.asList("A", "B", "C");
LinkedList<String> list2 = new LinkedList<>(source);

基本操作

新增元素

LinkedList<String> list = new LinkedList<>();

// 尾端新增
list.add("A");
list.addLast("B");
list.offer("C");

// 頭端新增
list.addFirst("Z");
list.offerFirst("Y");

// 指定位置新增
list.add(2, "M");

System.out.println(list);  // [Y, Z, A, M, B, C]

取得元素

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));

// 取得頭尾
String first = list.getFirst();  // A
String last = list.getLast();    // C

// peek 不會拋例外（空時回傳 null）
String peekFirst = list.peekFirst();  // A
String peekLast = list.peekLast();    // C

// 取得指定位置
String item = list.get(1);  // B

移除元素

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// 移除頭尾
String first = list.removeFirst();  // A
String last = list.removeLast();    // D

// poll 不會拋例外
String pollFirst = list.pollFirst();
String pollLast = list.pollLast();

// 移除指定元素
list.remove("B");
list.remove(0);  // 移除索引 0

當作堆疊（Stack）使用

LinkedList<String> stack = new LinkedList<>();

// push（加到頭端）
stack.push("A");
stack.push("B");
stack.push("C");

// pop（移除頭端）
String top = stack.pop();    // C
String peek = stack.peek();  // B（不移除）

System.out.println(stack);   // [B, A]

當作佇列（Queue）使用

LinkedList<String> queue = new LinkedList<>();

// 入列（加到尾端）
queue.offer("A");
queue.offer("B");
queue.offer("C");

// 出列（移除頭端）
String first = queue.poll();  // A

System.out.println(queue);    // [B, C]

迭代

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));

// for-each
for (String item : list) {
    System.out.println(item);
}

// Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// 反向迭代
Iterator<String> desc = list.descendingIterator();
while (desc.hasNext()) {
    System.out.println(desc.next());  // C, B, A
}

ArrayList vs LinkedList

實用範例

實作 LRU 快取

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> map;
    private final LinkedList<K> order;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.order = new LinkedList<>();
    }
    
    public V get(K key) {
        if (!map.containsKey(key)) return null;
        order.remove(key);
        order.addFirst(key);
        return map.get(key);
    }
    
    public void put(K key, V value) {
        if (map.containsKey(key)) {
            order.remove(key);
        } else if (map.size() >= capacity) {
            K oldest = order.removeLast();
            map.remove(oldest);
        }
        order.addFirst(key);
        map.put(key, value);
    }
}

重點整理

• LinkedList 是雙向鏈結串列
• 頭尾插入/刪除效率高 O(1)
• 隨機存取效率低 O(n)
• 可當作 Stack、Queue、Deque 使用
• 頻繁隨機存取建議用 ArrayList