Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánJunior21 phút đọc

Cấu trúc dữ liệu tuyến tính: Array, Linked List, Stack và Queue

Ôn 16 thẻ
Trong bài này

Cụm bài Cấu trúc dữ liệu: 1. Array, Linked List, Stack, Queue · 2. List, Set, Map · 3. TreeMap, Comparator, Iterator · 4. Bên trong ArrayList, HashMap

Cấu trúc dữ liệu (data structure) là một cách tổ chức dữ liệu trong bộ nhớ kèm theo các thao tác trên nó (thêm, sửa, xoá, tìm kiếm). Chọn sai thì code vẫn chạy đúng, nhưng có thể chậm hơn hàng trăm lần khi dữ liệu lớn. Đọc xong, bạn giải thích được array, linked list, stack, queue nằm trong bộ nhớ ra sao, mỗi thao tác tốn bao nhiêu và khi nào chọn cái nào.

Chưa quen O(1), O(n) thì lướt Big-O trước. Phần 2 và 3 sang API của Java Collections Framework (List, Set, Map, rồi TreeMap, Comparator, Iterator); phần 4 mở JDK xem ArrayList, ArrayDeque, HashMap thực sự hoạt động thế nào.

1. Array (mảng)

Ý chính: mảng là một dãy phần tử cùng kiểu, có thứ tự, nằm ở các ô nhớ liền kề nhau. Vì liền kề nên truy cập theo index là O(1).

Cần tính tổng 10 số mà khai báo 10 biến a0, a1, … thì không ổn; một mảng là đủ. Địa chỉ phần tử thứ i tính được ngay: base + i * elementSize.

int[] scores = new int[10];          // 10 phần tử, mặc định = 0
for (int i = 0; i < scores.length; i++) {
    scores[i] = i * 10;
}
int sum = 0;
for (int s : scores) sum += s;

1.1. Mảng tĩnh và mảng động

Mảng tĩnh (static array) Mảng động (dynamic array)
Kích thước Cố định sau khi tạo Tự tăng khi đầy
Ví dụ Java int[], String[] ArrayList<E>
Cách hoạt động Một khối nhớ liền kề Bọc một mảng tĩnh, khi đầy thì tạo mảng lớn hơn và copy sang

2. Linked List (danh sách liên kết)

Ý chính: mỗi phần tử là một node riêng, nằm đâu trong bộ nhớ cũng được, nối với nhau bằng tham chiếu. Chèn/xoá chỉ là nối lại con trỏ, đổi lại mất truy cập theo index.

Nó vá hai điểm yếu của mảng:

  1. Mảng cần một khối nhớ liền kề đủ lớn. Với dữ liệu rất lớn, việc này có thể khó.
  2. Chèn/xoá ở giữa mảng phải dịch cả đoạn phía sau.

Mỗi node có hai phần: dữ liệu (data) và tham chiếu (next) tới node kế tiếp. Danh sách giữ head (node đầu), thường giữ thêm tail (node cuối) và size.

flowchart LR
  H([head]) --> A
  A["data: 10 | next"] --> B["data: 20 | next"]
  B --> C["data: 30 | next"]
  C --> N((null))
  T([tail]) --> C

2.1. Singly và doubly linked list

  • Singly linked list: mỗi node chỉ trỏ tới node sau. Chỉ duyệt được một chiều, từ đầu về cuối.
  • Doubly linked list: mỗi node trỏ tới cả node trước (prev) và node sau (next). Duyệt được hai chiều, xoá một node đã biết trong O(1), đổi lại tốn thêm một tham chiếu mỗi node.

java.util.LinkedList là doubly linked list.

Biến thể vòng: circular và circular doubly linked list
  • Circular linked list: node cuối trỏ về node đầu, hữu ích cho round-robin.
  • Circular doubly linked list: kết hợp cả hai. next của node cuối trỏ về node đầu, prev của node đầu trỏ về node cuối, nên đi vòng được theo cả hai chiều và từ bất kỳ node nào cũng tới được mọi node.
  • Dùng cho playlist (bài kế/bài trước, hết thì quay vòng), lập lịch round-robin, và cài LRU cache với một sentinel duy nhất: sentinel.next là phần tử mới nhất, sentinel.prev là phần tử cũ nhất cần loại.

2.2. Các thao tác cơ bản

  • get(index): phải đi từ head qua từng node, O(n).
  • insert(index, value): tìm node đứng trước vị trí đó (O(n)), rồi nối lại hai con trỏ (O(1)). Chèn vào đầu là O(1); chèn vào cuối là O(1) nếu có tail.
  • delete(index): tìm node đứng trước, cho nó trỏ “nhảy qua” node bị xoá. Xoá đầu O(1). Xoá cuối trên singly list vẫn O(n) vì phải tìm node áp chót, kể cả khi có tail.
flowchart LR
  subgraph "Chèn X vào giữa A và B"
    A1[A] -. "next cũ" .-> B1[B]
    A1 -- "1. A.next = X" --> X1[X]
    X1 -- "2. X.next = B" --> B1
  end

Thứ tự gán quan trọng: phải lưu A.next (tức B) trước khi ghi đè nó, nếu không sẽ mất phần còn lại của danh sách.

2.3. So sánh Array và Linked List

2.4. Sentinel node và các thao tác trên doubly linked list

Khi tự cài linked list, phần lớn bug nằm ở trường hợp biên (danh sách rỗng, chèn vào đầu, xoá phần tử cuối), mỗi chỗ một câu if (head == null).

Sentinel node (còn gọi là dummy node) là một node giả không chứa dữ liệu thật và luôn tồn tại, kể cả khi danh sách rỗng. Với hai sentinel head và tail, mọi phần tử thật nằm giữa chúng, nên node nào cũng có prev và next khác null. Chèn/xoá dùng cùng một đoạn code. Giống hai tấm chặn sách ở hai đầu kệ: cuốn nào cũng có hàng xóm hai bên.

Ví dụ trong slide: danh sách có hai phần tử 2 (index 0) và 3 (index 1), hai đầu là hai sentinel giá trị 0 (giá trị gì cũng được, không ai đọc nó).

flowchart LR
  H["head (sentinel)"] <--> A["2 (index 0)"]
  A <--> B["3 (index 1)"]
  B <--> T["tail (sentinel)"]

Ba thao tác trên doubly linked list có sentinel:

  • get(i): i < size/2 thì đi xuôi từ head.next, ngược lại đi ngược từ tail.prev. Tối đa size/2 bước, vẫn O(n) nhưng nhanh gấp đôi.
  • insert(i, v): succ là node đang ở vị trí i (hoặc sentinel tail nếu i == size), pred = succ.prev. Tạo node mới rồi gán bốn con trỏ: node.prev, node.next, pred.next, succ.prev.
  • delete(i): lấy node ở vị trí i, pred = node.prev, succ = node.next, rồi pred.next = succ; succ.prev = pred;. Đã cầm node trong tay thì chỉ là O(1), không cần tìm node đứng trước như singly list.
Code đầy đủ MyDoublyLinkedList với hai sentinel, ví dụ từng thao tác và kết quả chạy thử

Ví dụ trên danh sách 2 ⇄ 3 của slide:

  • get(1): đi từ sentinel tail lùi một bước là tới.
  • insert(1, 5): pred là 2, succ là 3, kết quả 2 ⇄ 5 ⇄ 3.
  • delete(1) (node 3) ở danh sách 2 ⇄ 3: node 2 nối thẳng vào sentinel tail.
public class MyDoublyLinkedList {
    private static final class Node {
        int val;
        Node prev, next;
        Node(int val) { this.val = val; }
    }

    private final Node head = new Node(0); // sentinel, không chứa dữ liệu thật
    private final Node tail = new Node(0); // sentinel
    private int size;

    public MyDoublyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    // Đi từ đầu gần hơn: tối đa size/2 bước.
    private Node node(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index " + index + ", size " + size);
        }
        if (index < size / 2) {
            Node cur = head.next;
            for (int i = 0; i < index; i++) cur = cur.next;
            return cur;
        }
        Node cur = tail.prev;
        for (int i = size - 1; i > index; i--) cur = cur.prev;
        return cur;
    }

    public int get(int index) { return node(index).val; }

    // index == size nghĩa là thêm vào cuối. Không có nhánh riêng cho list rỗng/đầu/cuối.
    public void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index " + index + ", size " + size);
        }
        Node succ = (index == size) ? tail : node(index);
        Node pred = succ.prev;
        Node n = new Node(value);
        n.prev = pred;
        n.next = succ;
        pred.next = n;
        succ.prev = n;
        size++;
    }

    public int delete(int index) {
        Node n = node(index);
        Node pred = n.prev, succ = n.next;
        pred.next = succ;
        succ.prev = pred;
        n.prev = n.next = null; // cắt liên kết cũ, giúp GC và tránh dùng nhầm
        size--;
        return n.val;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (Node cur = head.next; cur != tail; cur = cur.next) {
            if (cur != head.next) sb.append(", ");
            sb.append(cur.val);
        }
        return sb.append(']').toString();
    }
}

Chạy thử: insert(0, 2); insert(1, 3) cho [2, 3], get(1) trả 3; insert(1, 5) cho [2, 5, 3]; delete(2) trả 3 và còn [2, 5]; xoá hết rồi insert(0, 7) vẫn chạy đúng mà không cần nhánh “list rỗng”.

Sentinel so với null, và java.util.LinkedList bên trong

3. Stack (ngăn xếp)

Ý chính: stack là LIFO (Last In, First Out): phần tử vào sau cùng được lấy ra đầu tiên, giống chồng đĩa. Chỉ được đụng vào đỉnh (top).

Thao tác Ý nghĩa Độ phức tạp
push(x) Đặt x lên đỉnh O(1)
pop() Lấy và xoá phần tử ở đỉnh O(1)
peek() Xem phần tử ở đỉnh, không xoá O(1)
isEmpty() Stack có rỗng không O(1)
isFull() Stack đầy chưa (chỉ có nghĩa với stack có giới hạn) O(1)
size() Số phần tử hiện có O(1)

Ứng dụng: call stack khi gọi hàm, undo/redo, kiểm tra ngoặc hợp lệ, đổi biểu thức trung tố sang hậu tố, DFS, nút “Back” của trình duyệt.

Hạn chế: không có truy cập ngẫu nhiên. Về khái niệm không có “phần tử thứ i” để lặp bằng for theo index; muốn xem hết thì phải lấy ra lần lượt đến khi rỗng:

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.push("c");
while (!stack.isEmpty()) {
    System.out.println(stack.pop());   // c, b, a
}

Lưu ý: java.util.Stack vì kế thừa Vector nên lại có get(i). Đây chính là một lỗi thiết kế, xem phần 4 của cụm bài.

4. Queue (hàng đợi)

Ý chính: queue là FIFO (First In, First Out): ai đến trước được phục vụ trước, như xếp hàng mua vé. Thêm vào cuối (rear), lấy ra ở đầu (front).

Thao tác Ý nghĩa Độ phức tạp
enqueue(x) Thêm x vào cuối O(1)
dequeue() Lấy và xoá phần tử ở đầu O(1)
peek() Xem phần tử ở đầu, không xoá O(1)
size() Số phần tử O(1)

Ứng dụng: BFS, hàng đợi job, buffer giữa producer và consumer, message queue (Kafka, RabbitMQ là “queue” ở mức hệ thống), thread pool (ThreadPoolExecutor dùng một BlockingQueue).

Giống stack, queue không có truy cập ngẫu nhiên: phải xử lý lần lượt từng phần tử.

Xem minh hoạ trực quan

Ý chính: các trang animation dưới đây (từ sách của Y. Daniel Liang) cho thấy rõ từng bước; nên mở ra bấm thử khi ôn.

Bài tập

Bài 1 và 2: Quiz stack và queue

Stack: tạo stack rỗng, push 18, 2, 6; pop và in; push 17; pop và in; in peek; in size.

Queue: enqueue 11, 2, 16; dequeue và in; enqueue 17; dequeue và in; in peek; in size.

Lời giải Bài 1 và 2: lần theo từng bước

Stack:

  • Sau 3 lần push: [18, 2, 6] (đỉnh là 6). Pop → 6.
  • Push 17: [18, 2, 17]. Pop → 17.
  • Peek → 2. Size → 2.
  • Đáp án: 6, 17, 2, 2, tức là phương án B.

Queue:

  • Sau 3 lần enqueue: [11, 2, 16] (đầu là 11). Dequeue → 11.
  • Enqueue 17: [2, 16, 17]. Dequeue → 2.
  • Peek → 16. Size → 2.
  • Đáp án: 11, 2, 16, 2, tức là phương án C.

Mình đã chạy lại cả hai bằng ArrayDeque để chắc chắn.

Bài 3: Dùng Stack đảo ngược chuỗi

Viết hàm reverse(String s) đảo ngược chuỗi bằng một stack. Bài này để luyện LIFO; trong code thật thì dùng new StringBuilder(s).reverse().

Lời giải Bài 3 và bẫy emoji
static String reverse(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) stack.push(c);
    StringBuilder sb = new StringBuilder(s.length());
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.toString();
}

Bài 4: Dùng Queue in dãy số theo đúng thứ tự nhập

Đọc n rồi n số nguyên, dùng một queue để in lại đúng thứ tự đã nhập.

Lời giải Bài 4
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) queue.offer(in.nextInt());
while (!queue.isEmpty()) System.out.print(queue.poll() + " ");

FIFO nên thứ tự in ra trùng với thứ tự nhập vào.

Bài 5: Kiểm tra dãy ngoặc hợp lệ

Đề: cho một chuỗi chứa các loại ngoặc (), [], {} lẫn ký tự khác, kiểm tra mọi ngoặc có được đóng đúng loại và đúng thứ tự không. Ví dụ "([]{})" hợp lệ; "(]", "(()", "())", "}{" không hợp lệ. Đây là bài stack kinh điển trong phỏng vấn.

Lời giải Bài 5: isBalanced bằng stack, độ phức tạp và biến thể một loại ngoặc

Ý tưởng: ngoặc mở thì push; ngoặc đóng thì phải khớp với ngoặc mở gần nhất chưa đóng, đúng là phần tử ở đỉnh stack (LIFO).

static boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        switch (c) {
            case '(', '[', '{' -> stack.push(c);
            case ')', ']', '}' -> {
                if (stack.isEmpty()) return false;            // đóng mà chưa mở: "())"
                if (stack.pop() != matching(c)) return false; // sai loại: "(]"
            }
            default -> { }                                     // bỏ qua ký tự khác
        }
    }
    return stack.isEmpty();                                    // còn ngoặc mở chưa đóng: "(()"
}

private static char matching(char close) {
    return switch (close) {
        case ')' -> '(';
        case ']' -> '[';
        default -> '{';
    };
}
// "" -> true, "([]{})" -> true, "if (a[i] == b) { x(); }" -> true
// "(]" -> false, "(()" -> false, "())" -> false, "}{" -> false
  • O(n) thời gian, O(n) bộ nhớ trong trường hợp xấu nhất (toàn ngoặc mở).
  • Ba nhánh trả về false ứng với ba kiểu sai khác nhau, nên khi phỏng vấn hãy nói rõ từng nhánh bắt lỗi gì.
  • Nếu chỉ có một loại ngoặc thì không cần stack: một biến đếm depth là đủ (gặp ( thì tăng, gặp ) thì giảm, âm là sai).

Mình đã chạy lời giải với 8 chuỗi ở trên.

Ghi nhớ

  • Giải thích được vì sao đọc phần tử thứ i của mảng là O(1) còn của linked list là O(n).
  • Biết khi nào chèn/xoá trên linked list thật sự là O(1), và vì sao xoá cuối trên singly list vẫn O(n).
  • Giải thích được vì sao ArrayList thường thắng LinkedList dù cùng Big-O.
  • Kể được bốn con trỏ phải gán khi chèn vào doubly linked list, và sentinel bỏ nhánh nào.
  • Biết chọn stack hay queue cho một bài toán (ngoặc, DFS, BFS, hàng đợi job).

Câu hỏi phỏng vấn

Junior

Array và ArrayList khác nhau thế nào?

Array có kích thước cố định và chứa được primitive; ArrayList là mảng động tự tăng kích thước, chỉ chứa object.

ArrayList bọc một Object[], nên int bị boxing thành Integer. Bù lại nó có sẵn nhiều method tiện ích và generic.

Stack và Queue khác nhau thế nào? Cho ví dụ ứng dụng.

Stack là LIFO, chỉ thao tác ở đỉnh; queue là FIFO, thêm ở cuối lấy ở đầu.

Stack: call stack, undo, kiểm tra ngoặc, DFS. Queue: BFS, hàng đợi job, buffer producer/consumer.

Tại sao truy cập phần tử thứ i của mảng là O(1), còn của linked list là O(n)?

Mảng nằm liền kề nên địa chỉ tính thẳng bằng base + i * size; linked list không có công thức địa chỉ.

Với linked list phải đi theo next từ head qua i node.

Singly linked list và doubly linked list khác nhau thế nào?

Node của singly list chỉ có next; node của doubly list có thêm prev, nên duyệt được hai chiều và xoá một node đang cầm là O(1).

Singly list chỉ duyệt một chiều, muốn xoá một node phải biết node đứng trước nó; xoá phần tử cuối vẫn O(n) dù có tail. Doubly list xoá cuối O(1), đổi lại mỗi node tốn thêm một tham chiếu. java.util.LinkedList là doubly linked list.

Mid

offer/poll/peek khác add/remove/element thế nào?

Nhóm offer/poll/peek báo lỗi bằng giá trị trả về (false/null); nhóm add/remove/element ném exception.

Exception là IllegalStateException (đầy) và NoSuchElementException (rỗng). Với queue có giới hạn hoặc khi rỗng là chuyện bình thường, dùng nhóm đầu.

Cài đặt queue bằng hai stack thế nào? Độ phức tạp ra sao?

Dùng stack in để nhận và stack out để trả; khi out rỗng thì đổ hết in sang out. Chi phí amortized O(1) mỗi thao tác.

offer = push vào in. Khi poll mà out rỗng thì đổ toàn bộ in sang out; việc đổ làm đảo thứ tự nên đỉnh out chính là phần tử vào sớm nhất. Một lần poll có thể tốn O(n), nhưng mỗi phần tử chỉ được chuyển từ in sang out đúng một lần. Câu hỏi này kiểm tra hiểu LIFO/FIFO và phân tích amortized.

Sentinel (dummy) node là gì và vì sao nó làm code linked list gọn hơn?

Sentinel là một node giả không chứa dữ liệu thật và luôn tồn tại, nên mọi node thật đều có prev và next khác null, chèn/xoá chỉ còn một đường code.

Chèn là pred.next = node; succ.prev = node, xoá là pred.next = succ; succ.prev = pred. Không còn nhánh riêng cho list rỗng, phần tử đầu, phần tử cuối. Cái giá là một hai node thừa và phải nhớ dừng duyệt ở cur != tail. Ví dụ thực tế: LRU cache tự cài bằng HashMap + doubly linked list có sentinel.

Senior

Vì sao cache locality có thể quan trọng hơn Big-O?

Vì Big-O bỏ qua hằng số, mà một cache miss tốn ~100 ns so với ~1 ns khi đọc từ L1.

Duyệt mảng liền kề tận dụng cache line 64 byte và prefetcher; duyệt linked list là pointer chasing, mỗi bước có thể miss. Vì vậy chèn giữa O(n) của ArrayList (một lần arraycopy liền khối) thường nhanh hơn việc tìm tới vị trí O(n) trên LinkedList, dù cả hai đều O(n).

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu trong phỏng vấn
contiguous memory /kənˈtɪɡjuəs/ bộ nhớ liền kề “Arrays store elements in contiguous memory, so index access is constant time.”
LIFO / FIFO /ˈlaɪfoʊ/ /ˈfaɪfoʊ/ vào sau ra trước / vào trước ra trước “A stack is LIFO, while a queue is FIFO.”
push / pop / peek /pʊʃ/ /pɑːp/ /piːk/ đẩy vào / lấy ra / xem đỉnh “Peek returns the top element without removing it.”
enqueue / dequeue /ɛnˈkjuː/ /diːˈkjuː/ thêm vào hàng đợi / lấy khỏi hàng đợi “We enqueue at the tail and dequeue from the head.”
cache locality /kæʃ loʊˈkæləti/ tính cục bộ bộ nhớ đệm “ArrayList usually wins because of better cache locality.”
doubly linked list /ˈdʌbli lɪŋkt lɪst/ danh sách liên kết đôi “A doubly linked list lets me remove a node in constant time once I have it.”
sentinel node /ˈsɛntɪnəl noʊd/ node giả canh hai đầu danh sách “With sentinel head and tail nodes, insert and delete never need a null check.”
balanced brackets /ˈbælənst ˈbrækɪts/ dãy ngoặc hợp lệ “Checking balanced brackets is a classic stack problem.”

Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer) và tài liệu Java Core của Hỏi Dân IT, cộng thêm kiến thức tự tìm hiểu, viết lại theo cách hiểu của mình.