Cấu trúc tuyến tính — Array, Linked List, Stack, Queue

Trong buổi phỏng vấn system design tại một Big Tech, ứng viên đề xuất dùng Linked List để lưu trữ cache entries. Interviewer hỏi: "Tại sao không dùng Array?" Ứng viên không trả lời được vì chưa bao giờ nghĩ về cache locality và memory layout. Bốn cấu trúc dữ liệu tuyến tính này — Array, Linked List, Stack, Queue — là nền tảng mà mọi kỹ sư phải nắm vững, không chỉ API mà còn trade-offs bên trong.

Phần lớn lập trình viên dừng ở mức "biết xài" — gọi .push(), .pop(), .append(). Nhưng khi interviewer hỏi "tại sao ArrayList nhanh hơn LinkedList trong 99% trường hợp?" hoặc "khi nào deque thắng cả stack lẫn queue?" — câu trả lời nằm ở memory layout, cache behavior, và amortized analysis. Đó là những thứ bài viết này sẽ trang bị cho bạn.

🎯 Mục tiêu

Sau bài này, bạn sẽ:

Hiểu memory layout: contiguous (Array) vs scattered (Linked List)
Biết khi nào Linked List thực sự thắng Array (hiếm hơn bạn nghĩ)
Thành thạo Stack pattern: monotonic stack, valid parentheses
Hiểu Queue variants: circular buffer, deque, priority queue
Phân tích amortized complexity của dynamic array

Bảng so sánh tổng quan

Trước khi đi sâu, hãy có bức tranh toàn cảnh về bốn cấu trúc:

Thao tác	Array	Linked List	Stack	Queue
Access[i]	O(1) ✅	O(n) ❌	N/A	N/A
Search	O(n)	O(n)	N/A	N/A
Insert đầu	O(n)	O(1) ✅	—	—
Insert cuối	O(1)*	O(1)**	O(1)	O(1)
Delete đầu	O(n)	O(1) ✅	—	O(1)
Delete cuối	O(1)	O(n)***	O(1)	—
Push / Pop	—	—	O(1)	—
Enqueue / Dequeue	—	—	—	O(1)

*amortized **with tail pointer ***singly linked list

Đọc bảng này như thế nào

Đừng học thuộc bảng — hãy hiểu tại sao. Array access O(1) vì địa chỉ = base + index × sizeof(element). Linked List insert đầu O(1) vì chỉ cần rewire 1 pointer. Khi hiểu cơ chế, complexity tự suy ra được.

Array — Nền tảng của mọi thứ

Memory Layout

Array lưu các phần tử liên tiếp trong bộ nhớ. Đây là đặc điểm quan trọng nhất, quyết định mọi ưu/nhược điểm.

text

Contiguous Memory (Array):
┌─────┬─────┬─────┬─────┬─────┐
│  10 │  20 │  30 │  40 │  50 │
└─────┴─────┴─────┴─────┴─────┘
0x100  0x104  0x108  0x10C  0x110
   ▲ 4 bytes apart (int) → CPU cache line loads ALL at once

Random access O(1): address = base + index × sizeof(element) — phép tính số học đơn giản, không cần duyệt
Cache-friendly: các phần tử nằm kề nhau → CPU prefetcher load sẵn dữ liệu vào cache → ít cache miss
Spatial locality: khi truy cập arr[i], rất có thể arr[i+1], arr[i+2] đã nằm sẵn trong cache line (thường 64 bytes)

Dynamic Array — Amortized O(1) Append

Mảng tĩnh (fixed array) có kích thước cố định tại compile time. Trong thực tế, hầu hết ngôn ngữ cung cấp dynamic array: std::vector (C++), ArrayList (Java), list (Python). Cơ chế hoạt động:

Cấp phát mảng có capacity ban đầu (ví dụ 4)
Khi đầy, tạo mảng mới gấp đôi capacity → copy toàn bộ phần tử sang
Geometric growth: 1 → 2 → 4 → 8 → 16 → ...

text

Dynamic Array Growth:
[1]         capacity=1, size=1
[1, 2]      capacity=2, size=2 → FULL, resize!
[1, 2, 3, _]     capacity=4, size=3
[1, 2, 3, 4]     capacity=4, size=4 → FULL, resize!
[1, 2, 3, 4, 5, _, _, _]  capacity=8, size=5

Total copies after n appends: n + n/2 + n/4 + ... ≈ 2n → amortized O(1)

📌 Tại sao gấp đôi, không phải cộng thêm k?

Nếu mỗi lần đầy ta chỉ thêm k slot (additive growth), tổng copies = n + (n-k) + (n-2k) + ... ≈ O(n²/k). Geometric growth đảm bảo tổng copies luôn là O(n), cho amortized O(1) mỗi append.

Cài đặt cơ bản

C++PythonJava

cpp

#include <vector>
using namespace std;

vector<int> arr = {1, 2, 3};
arr.push_back(4);           // O(1) amortized
arr[2];                     // O(1) random access
arr.insert(arr.begin(), 0); // O(n) — shift everything right
arr.erase(arr.begin() + 1); // O(n) — shift everything left
// arr.size() → 4
// arr.capacity() → có thể > 4 (implementation-defined)

python

arr = [1, 2, 3]
arr.append(4)       # O(1) amortized
arr[2]              # O(1) random access
arr.insert(0, 0)    # O(n) — shift everything right
arr.pop(1)          # O(n) — shift everything left (pop from middle)
arr.pop()           # O(1) — pop from end

java

import java.util.ArrayList;

ArrayList<Integer> arr = new ArrayList<>(List.of(1, 2, 3));
arr.add(4);            // O(1) amortized
arr.get(2);            // O(1) random access
arr.add(0, 0);         // O(n) — shift everything right
arr.remove(1);         // O(n) — shift everything left

Khi nào Array thất bại

⚠️ Cạm bẫy

Array KHÔNG phù hợp khi:

Insert/delete thường xuyên ở đầu hoặc giữa — mỗi thao tác O(n) do phải shift phần tử
Kích thước không đoán được + cần guarantee O(1) mọi append — occasional resize gây latency spike (dù amortized O(1))
Cần merge/split nhanh — nối 2 array là O(n), không thể nhanh hơn

Workaround thực tế: cần xóa ở giữa nhưng không cần thứ tự → swap với phần tử cuối rồi pop() → O(1). Hoặc mark-as-deleted + compact định kỳ (pattern dùng trong database engines).

text

VISUALIZER STATES — Array:
State 1: ACCESS — index i highlights instantly (O(1) demo)
State 2: INSERT_END — new element slides in at tail, capacity may double
State 3: INSERT_FRONT — all elements shift right, new element enters at [0]
State 4: DELETE — element fades, remaining elements shift left
State 5: RESIZE — array doubles, elements copy one-by-one to new block

Linked List — Khi nào thực sự cần?

Memory Layout

Trái ngược hoàn toàn với Array, Linked List lưu các node rải rác trong bộ nhớ, kết nối bằng pointer.

text

Scattered Memory (Linked List):
┌──────────┐    ┌──────────┐    ┌──────────┐
│ val: 10  │    │ val: 20  │    │ val: 30  │
│ next: ─────►  │ next: ─────►  │ next:NULL│
└──────────┘    └──────────┘    └──────────┘
   0x200           0x500           0x120
     ▲ Scattered! CPU cache misses on every hop

Mỗi lần truy cập node tiếp theo, CPU phải theo pointer đến vị trí ngẫu nhiên trong RAM. Cache line vừa load xong trở nên vô dụng. Đây là lý do Linked List chậm hơn Array trong thực tế cho hầu hết thao tác duyệt.

Singly vs Doubly Linked List

Đặc điểm	Singly	Doubly
Pointer / node	1 (`next`)	2 (`next` + `prev`)
Memory / node	Ít hơn 8 bytes	Thêm 8 bytes (64-bit pointer)
Traverse ngược	❌ Không thể	✅ O(n)
Delete given node	O(n) — cần tìm prev	O(1) — có sẵn prev
Use case điển hình	Stack, simple queue	LRU Cache, browser history

Cài đặt Node và thao tác cơ bản

C++PythonJava

cpp

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// Insert at head: O(1)
void insertHead(Node*& head, int val) {
    Node* newNode = new Node(val);
    newNode->next = head;
    head = newNode;
}

// Delete at head: O(1)
void deleteHead(Node*& head) {
    if (!head) return;
    Node* temp = head;
    head = head->next;
    delete temp;
}

// Search: O(n)
Node* search(Node* head, int target) {
    Node* curr = head;
    while (curr) {
        if (curr->val == target) return curr;
        curr = curr->next;
    }
    return nullptr;
}

python

class Node:
    def __init__(self, val: int, next_node=None):
        self.val = val
        self.next = next_node

# Insert at head: O(1)
def insert_head(head: Node | None, val: int) -> Node:
    return Node(val, head)

# Delete at head: O(1)
def delete_head(head: Node | None) -> Node | None:
    if not head:
        return None
    return head.next

# Search: O(n)
def search(head: Node | None, target: int) -> Node | None:
    curr = head
    while curr:
        if curr.val == target:
            return curr
        curr = curr.next
    return None

java

class Node {
    int val;
    Node next;
    Node(int v) { val = v; next = null; }
}

// Insert at head: O(1)
static Node insertHead(Node head, int val) {
    Node newNode = new Node(val);
    newNode.next = head;
    return newNode;
}

// Delete at head: O(1)
static Node deleteHead(Node head) {
    if (head == null) return null;
    return head.next;
}

// Search: O(n)
static Node search(Node head, int target) {
    Node curr = head;
    while (curr != null) {
        if (curr.val == target) return curr;
        curr = curr.next;
    }
    return null;
}

Sự thật không thoải mái

Linked List thua Array trong hầu hết trường hợp

Trong thực tế, Linked List chậm hơn Array cho hầu hết use cases vì:

Cache misses: mỗi node ở vị trí random trong RAM → CPU cache thrashing
Pointer overhead: mỗi node cần 8 bytes (64-bit) cho mỗi pointer
No random access: truy cập node thứ k cần duyệt k bước
Allocation overhead: mỗi node cần malloc/new riêng → memory allocator overhead

Khi nào Linked List thắng:

Insert/delete tại vị trí đã biết (có sẵn node reference): O(1) vs O(n)
LRU Cache: doubly linked list + hash map = O(1) access + O(1) eviction
Implement undo history: mỗi action là 1 node, undo = move pointer back
Khi không được phép di chuyển phần tử (ví dụ: OS memory page management)

Bjarne Stroustrup — cha đẻ C++ — từng làm benchmark chứng minh std::vector nhanh hơn std::list cho cả insert ở giữa khi n < 500,000 phần tử. Cache locality thắng algorithmic complexity trong thực tế.

text

VISUALIZER STATES — Linked List:
State 1: TRAVERSE — current pointer moves node by node (arrow animation)
State 2: INSERT — new node appears, pointers rewire (animation)
State 3: DELETE — node fades, surrounding pointers reconnect
State 4: HIGHLIGHT — found node glows green

Stack — LIFO và Monotonic Stack Pattern

Mô hình tư duy: Call Stack

Stack (ngăn xếp) hoạt động theo nguyên tắc LIFO — Last In, First Out. Hình dung chồng đĩa: bạn chỉ có thể lấy đĩa trên cùng.

Ứng dụng quen thuộc nhất: call stack của chương trình. Mỗi khi hàm được gọi, một stack frame mới được push. Khi hàm return, frame bị pop.

text

Call Stack (function calls):
┌─────────────┐
│ factorial(1) │  ← top (executing now)
├─────────────┤
│ factorial(2) │
├─────────────┤
│ factorial(3) │
├─────────────┤
│    main()    │  ← bottom
└─────────────┘

factorial(3) gọi factorial(2) gọi factorial(1)
→ factorial(1) return trước → rồi factorial(2) → rồi factorial(3)

📌 Stack Overflow

Khi recursion quá sâu (không có base case, hoặc input quá lớn), call stack hết bộ nhớ → Stack Overflow. Đây cũng là lý do tại sao competitive programming thường prefer iterative over recursive cho input lớn.

Thao tác cơ bản

C++PythonJava

cpp

#include <stack>
using namespace std;

stack<int> st;
st.push(42);        // push: O(1)
st.push(17);        // push: O(1)
int top = st.top(); // peek: O(1) → 17
st.pop();           // pop: O(1) → removes 17
bool empty = st.empty(); // O(1)

python

stack = []
stack.append(42)     # push: O(1)
stack.append(17)     # push: O(1)
top = stack[-1]      # peek: O(1) → 17
stack.pop()          # pop: O(1) → 17
is_empty = len(stack) == 0  # O(1)

java

import java.util.ArrayDeque;

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(42);             // push: O(1)
stack.push(17);             // push: O(1)
int top = stack.peek();     // peek: O(1) → 17
stack.pop();                // pop: O(1) → 17
boolean empty = stack.isEmpty(); // O(1)
// Lưu ý: KHÔNG dùng java.util.Stack (legacy, synchronized, chậm)

Valid Parentheses — Bài kinh điển

Cho string chứa (), {}, []. Kiểm tra xem mọi bracket có được đóng đúng không.

Ý tưởng: Gặp bracket mở → push. Gặp bracket đóng → pop và kiểm tra có match không.

C++PythonJava

cpp

bool isValid(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top(); st.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '['))
                return false;
        }
    }
    return st.empty(); // quan trọng: stack phải rỗng cuối cùng
}

python

def is_valid(s: str) -> bool:
    stack = []
    match = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in '({[':
            stack.append(c)
        else:
            if not stack or stack[-1] != match[c]:
                return False
            stack.pop()
    return len(stack) == 0  # stack phải rỗng cuối cùng

java

public boolean isValid(String s) {
    ArrayDeque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '['))
                return false;
        }
    }
    return stack.isEmpty();
}

Monotonic Stack — Interview Gold Mine

Next Greater Element: Cho mảng, tìm phần tử lớn hơn tiếp theo bên phải cho mỗi phần tử.

text

Input:  [4, 5, 2, 10, 8]
Output: [5, 10, 10, -1, -1]

Giải thích: 4 → next greater = 5
            5 → next greater = 10
            2 → next greater = 10
           10 → không có → -1
            8 → không có → -1

Brute force: hai vòng lặp lồng nhau → O(n²)
Monotonic stack: duyệt 1 lần, stack giữ index theo thứ tự giá trị giảm dần → O(n) 🔥

C++PythonJava

cpp

vector<int> nextGreaterElement(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st; // stores indices, values are decreasing

    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] < arr[i]) {
            result[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

python

def next_greater_element(arr: list[int]) -> list[int]:
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices, values are decreasing

    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    return result

# Trace:  [4, 5, 2, 10, 8]
# i=0: stack=[]       → push 0       stack=[0]
# i=1: arr[0]=4 < 5   → pop 0, result[0]=5, push 1  stack=[1]
# i=2: arr[1]=5 > 2   → push 2       stack=[1,2]
# i=3: arr[2]=2 < 10  → pop 2, result[2]=10
#       arr[1]=5 < 10  → pop 1, result[1]=10, push 3  stack=[3]
# i=4: arr[3]=10 > 8  → push 4       stack=[3,4]
# result = [5, 10, 10, -1, -1] ✓

java

public int[] nextGreaterElement(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    ArrayDeque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            result[stack.pop()] = arr[i];
        }
        stack.push(i);
    }
    return result;
}

Khi nào dùng Monotonic Stack?

Nhận dạng pattern: "tìm phần tử lớn/nhỏ hơn tiếp theo (next/previous greater/smaller)" → monotonic stack. Các biến thể phổ biến:

Next Greater Element (NGE) — duyệt trái → phải, stack giảm dần
Previous Greater Element (PGE) — duyệt trái → phải, pop khi ≤
Largest Rectangle in Histogram — kết hợp NGE + PGE
Stock Span Problem — PGE variant

text

VISUALIZER STATES — Stack:
State 1: PUSH — new element slides in from top
State 2: POP — top element slides out
State 3: PEEK — top element highlights yellow
State 4: EMPTY_CHECK — stack outline pulses if empty
State 5: MONOTONIC — stack maintains decreasing order, elements pop when violated

Queue — FIFO, BFS, và Deque

Queue Basics

Queue (hàng đợi) hoạt động theo nguyên tắc FIFO — First In, First Out. Hình dung hàng đợi mua vé: người đến trước được phục vụ trước.

text

Queue:
  FRONT                          REAR
   ↓                              ↓
┌─────┬─────┬─────┬─────┬─────┐
│  A  │  B  │  C  │  D  │  E  │
└─────┴─────┴─────┴─────┴─────┘
  dequeue ←                  ← enqueue

Enqueue(F): thêm F vào REAR
Dequeue():  lấy A từ FRONT

Ứng dụng quan trọng nhất: BFS (Breadth-First Search) — duyệt đồ thị theo từng level. Mỗi node được enqueue khi phát hiện, dequeue khi xử lý.

Cài đặt cơ bản

C++PythonJava

cpp

#include <queue>
using namespace std;

queue<int> q;
q.push(10);         // enqueue: O(1)
q.push(20);         // enqueue: O(1)
int front = q.front(); // peek: O(1) → 10
q.pop();             // dequeue: O(1) → removes 10
bool empty = q.empty(); // O(1)

python

from collections import deque

q = deque()
q.append(10)         # enqueue (right): O(1)
q.append(20)         # enqueue (right): O(1)
front = q[0]         # peek: O(1) → 10
q.popleft()          # dequeue (left): O(1) → 10
is_empty = len(q) == 0  # O(1)
# KHÔNG dùng list cho queue: list.pop(0) là O(n)!

java

import java.util.ArrayDeque;

ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(10);            // enqueue: O(1)
queue.offer(20);            // enqueue: O(1)
int front = queue.peek();   // peek: O(1) → 10
queue.poll();               // dequeue: O(1) → 10
boolean empty = queue.isEmpty(); // O(1)
// KHÔNG dùng LinkedList cho queue khi có ArrayDeque

⚠️ Cạm bẫy

Queue implementation: chọn đúng backing structure!

Python: PHẢI dùng collections.deque, KHÔNG dùng list. list.pop(0) là O(n) vì shift toàn bộ mảng.
Java: Dùng ArrayDeque, KHÔNG dùng LinkedList (cache-unfriendly) hoặc java.util.Queue interface với LinkedList.
C++: std::queue mặc định dùng std::deque bên dưới — hợp lý.

Circular Buffer — Queue trên mảng cố định

Khi biết trước kích thước tối đa (ví dụ: message buffer, connection pool), circular buffer là lựa chọn hiệu quả nhất — không cần allocation, không cần shift.

text

Circular Buffer (size=5):
     head           tail
      ↓               ↓
  ┌───┬───┬───┬───┬───┐
  │ _ │ A │ B │ C │ _ │
  └───┴───┴───┴───┴───┘
   [0] [1] [2] [3] [4]

After enqueue(D):
     head               tail
      ↓                   ↓
  ┌───┬───┬───┬───┬───┐
  │ _ │ A │ B │ C │ D │
  └───┴───┴───┴───┴───┘

After dequeue() → returns A:
         head        tail
          ↓           ↓
  ┌───┬───┬───┬───┬───┐
  │ _ │ _ │ B │ C │ D │
  └───┴───┴───┴───┴───┘

After enqueue(E) — tail wraps around!:
  tail   head
   ↓      ↓
  ┌───┬───┬───┬───┬───┐
  │ E │ _ │ B │ C │ D │
  └───┴───┴───┴───┴───┘

Kỹ thuật wrap-around: next_index = (current_index + 1) % capacity

C++PythonJava

cpp

class CircularQueue {
    vector<int> buf;
    int head, tail, size, cap;
public:
    CircularQueue(int k) : buf(k), head(0), tail(0), size(0), cap(k) {}

    bool enqueue(int val) {
        if (size == cap) return false; // full
        buf[tail] = val;
        tail = (tail + 1) % cap;
        size++;
        return true;
    }

    int dequeue() {
        if (size == 0) return -1; // empty
        int val = buf[head];
        head = (head + 1) % cap;
        size--;
        return val;
    }
};

python

class CircularQueue:
    def __init__(self, k: int):
        self.buf = [0] * k
        self.head = self.tail = self.size = 0
        self.cap = k

    def enqueue(self, val: int) -> bool:
        if self.size == self.cap:
            return False  # full
        self.buf[self.tail] = val
        self.tail = (self.tail + 1) % self.cap
        self.size += 1
        return True

    def dequeue(self) -> int:
        if self.size == 0:
            return -1  # empty
        val = self.buf[self.head]
        self.head = (self.head + 1) % self.cap
        self.size -= 1
        return val

java

class CircularQueue {
    private int[] buf;
    private int head, tail, size, cap;

    public CircularQueue(int k) {
        buf = new int[k];
        head = tail = size = 0;
        cap = k;
    }

    public boolean enqueue(int val) {
        if (size == cap) return false;
        buf[tail] = val;
        tail = (tail + 1) % cap;
        size++;
        return true;
    }

    public int dequeue() {
        if (size == 0) return -1;
        int val = buf[head];
        head = (head + 1) % cap;
        size--;
        return val;
    }
}

Deque — Swiss Army Knife

Double-ended queue: push/pop từ CẢ HAI ĐẦU trong O(1). Deque có thể thay thế cả Stack lẫn Queue.

Thao tác	Deque	Stack	Queue
Push front	✅ O(1)	❌	❌
Push back	✅ O(1)	✅ O(1)	✅ O(1)
Pop front	✅ O(1)	❌	✅ O(1)
Pop back	✅ O(1)	✅ O(1)	❌

C++PythonJava

cpp

#include <deque>
using namespace std;

deque<int> dq;
dq.push_back(1);   // [1]
dq.push_front(0);  // [0, 1]
dq.push_back(2);   // [0, 1, 2]
dq.pop_front();    // [1, 2] → removed 0
dq.pop_back();     // [1] → removed 2
// Random access: dq[0] → O(1)

python

from collections import deque

dq = deque()
dq.append(1)        # right: [1]
dq.appendleft(0)    # left:  [0, 1]
dq.append(2)        # right: [0, 1, 2]
dq.popleft()        # left:  [1, 2] → removed 0
dq.pop()            # right: [1] → removed 2

# Bonus: deque with maxlen → sliding window!
window = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    window.append(x)
# window = deque([3, 4, 5]) — auto-evicts oldest

java

import java.util.ArrayDeque;

ArrayDeque<Integer> dq = new ArrayDeque<>();
dq.addLast(1);      // [1]
dq.addFirst(0);     // [0, 1]
dq.addLast(2);      // [0, 1, 2]
dq.pollFirst();     // [1, 2] → removed 0
dq.pollLast();      // [1] → removed 2

Khi nào dùng Deque?

Sliding Window Maximum — deque giữ index của candidates theo thứ tự giảm dần
Palindrome check — so sánh front và back, pop cả hai
Work-stealing scheduler — thread lấy task từ front của queue mình, steal từ back của queue khác
Khi không chắc cần Stack hay Queue — dùng deque cho linh hoạt

text

VISUALIZER STATES — Queue:
State 1: ENQUEUE — element slides in from right
State 2: DEQUEUE — element slides out from left
State 3: FRONT — front element highlights
State 4: CIRCULAR_WRAP — tail wraps to beginning of array (animation)
State 5: DEQUE_BOTH — elements can enter/exit from both ends

Memory Battle: Array vs Linked List

Đây là cuộc so sánh mà mọi kỹ sư phải hiểu rõ, không chỉ ở mức Big-O mà ở mức hardware.

text

Array traversal:
┌──┬──┬──┬──┬──┬──┬──┬──┐
│ 1│ 2│ 3│ 4│ 5│ 6│ 7│ 8│  ← 1 cache line (64 bytes = 16 ints)
└──┴──┴──┴──┴──┴──┴──┴──┘
  → → → → → → → →  Sequential! Prefetcher loves this.

Linked List traversal:
 [1]──→ [2]──→ [3]──→ [4]──→ [5]
0x200  0x800  0x150  0x600  0x350
  ↗      ↘      ↗      ↘      ↗   Random jumps! Cache miss every hop.

Tiêu chí	Array	Linked List	Thắng
Cache hits	Cao (sequential access)	Thấp (random access)	Array
Random access	O(1)	O(n)	Array
Insert at front	O(n)	O(1)	Linked List
Insert at known position	O(n)	O(1) với node ref	Linked List
Memory per element	sizeof(element)	sizeof(element) + 8-16 bytes	Array
Resize	O(n) occasional	Không cần	Linked List
Merge two lists	O(n + m)	O(1) pointer rewire	Linked List

Kết luận thực tế

Default to Array. Dùng Linked List chỉ khi bạn có lý do cụ thể:

Cần O(1) insert/delete tại vị trí đã biết (LRU Cache)
Cần merge/split O(1)
Memory allocation pattern không cho phép contiguous block lớn

Trong 15 năm viết production code, số lần tôi dùng raw Linked List có thể đếm trên hai bàn tay. Hầu hết "Linked List" trong production thực ra nằm bên trong các abstraction: LRU Cache, allocator free list, OS scheduler queue.

Bài tập luyện tập

🧠 Quiz

Câu 1: Implement Queue using two Stacks — amortized time cho dequeue?

Cho 2 stack, implement queue. Push vào stack1. Khi dequeue, nếu stack2 rỗng → đổ hết stack1 sang stack2 rồi pop stack2.

[x] A) O(1) amortized
[ ] B) O(n) mỗi lần
[ ] C) O(log n)
[ ] D) O(n²)

💡 Giải thích: Mỗi phần tử được move từ stack1 sang stack2 đúng 1 lần trong toàn bộ vòng đời. n phần tử → n lần move tổng cộng. Chia đều cho n thao tác dequeue → amortized O(1). Tương tự cách phân tích dynamic array resize.

Câu 2: Tại sao `std::vector` (C++) nhanh hơn `std::list` cho insert ở giữa khi n nhỏ?

[ ] A) vector::insert có complexity tốt hơn
[x] B) Cache locality: shift O(n) phần tử contiguous nhanh hơn traverse O(n) pointer scattered
[ ] C) list cần lock khi insert
[ ] D) vector dùng binary search để tìm vị trí insert

💡 Giải thích: Cả hai đều O(n), nhưng vector shift liên tiếp trong memory → CPU dùng memcpy/SIMD, cache line hit. List phải chase pointer qua RAM → cache miss mỗi hop. Với n < 500K, overhead cache miss > overhead copy.

Câu 3: Khi nào dùng Circular Buffer thay vì Dynamic Queue?

[ ] A) Khi queue có thể grow vô hạn
[x] B) Khi biết trước max size và cần tránh dynamic allocation
[ ] C) Khi cần random access vào queue
[ ] D) Khi cần deque (double-ended)

💡 Giải thích: Circular buffer phù hợp khi max size cố định: network buffer, connection pool, producer-consumer với bounded capacity. Không cần malloc/realloc → predictable latency, ít fragmentation.

🐛 Spot the Bug

Tìm bug trong đoạn code kiểm tra ngoặc hợp lệ:

python

def is_valid_brackets(s: str) -> bool:
    stack = []
    match = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in '({[':
            stack.append(c)
        elif c in ')}]':
            if stack[-1] != match[c]:   # BUG ở đây!
                return False
            stack.pop()
    return True                          # BUG ở đây!

💡 Gợi ý

Chuyện gì xảy ra khi input là ")(" hoặc "(("?
Kiểm tra 2 edge case: (1) stack rỗng khi gặp bracket đóng, (2) stack còn dư phần tử khi hết string

✅ Lời giải

Bug 1: stack[-1] khi stack rỗng → IndexError. Input ")" sẽ crash.

Bug 2: Return True thay vì len(stack) == 0. Input "((" sẽ trả True sai.

python

def is_valid_brackets(s: str) -> bool:
    stack = []
    match = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in '({[':
            stack.append(c)
        elif c in ')}]':
            if not stack or stack[-1] != match[c]:  # FIX 1: check empty
                return False
            stack.pop()
    return len(stack) == 0  # FIX 2: stack must be empty

Bài học: Luôn xử lý edge case stack rỗng trước khi peek/pop. Và kiểm tra trạng thái cuối cùng sau vòng lặp.

🧩 Parsons Problem

Sắp xếp các dòng code sau thành thuật toán Next Greater Element sử dụng monotonic stack:

text

# Các dòng bị xáo trộn — sắp xếp lại đúng thứ tự:

A)  result[idx] = arr[i]
B)  return result
C)  stack = []
D)  for i in range(n):
E)  result = [-1] * n
F)  while stack and arr[stack[-1]] < arr[i]:
G)  n = len(arr)
H)  idx = stack.pop()
I)  stack.append(i)
J)  def next_greater_element(arr):

✅ Đáp án

Thứ tự đúng: J → G → E → C → D → F → H → A → I → B

python

def next_greater_element(arr):       # J
    n = len(arr)                     # G
    result = [-1] * n                # E
    stack = []                       # C
    for i in range(n):               # D
        while stack and arr[stack[-1]] < arr[i]:  # F
            idx = stack.pop()        # H
            result[idx] = arr[i]     # A
        stack.append(i)              # I
    return result                    # B

Logic: Khởi tạo → duyệt mảng → với mỗi phần tử, pop stack khi phần tử hiện tại lớn hơn → cập nhật result → push index hiện tại → return.

Checklist ghi nhớ

✅ Checklist triển khai

Array

[ ] Hiểu random access O(1): address = base + index × sizeof(element)
[ ] Hiểu amortized O(1) append của dynamic array (geometric growth)
[ ] Biết insert/delete ở đầu/giữa là O(n) và workaround (swap-with-last)

Linked List

[ ] Phân biệt Singly vs Doubly: khi nào cần doubly (LRU Cache, delete given node)
[ ] Hiểu tại sao Array thường nhanh hơn trong thực tế (cache locality)
[ ] Biết khi nào Linked List thực sự cần (O(1) insert/delete at known position)

Stack

[ ] Cài đặt được Valid Parentheses bằng Stack
[ ] Hiểu Monotonic Stack pattern cho Next Greater Element
[ ] Biết call stack và Stack Overflow

Queue

[ ] Phân biệt Queue, Circular Buffer, Deque
[ ] Biết dùng đúng implementation (Python: deque, Java: ArrayDeque)
[ ] Hiểu circular buffer wrap-around: (index + 1) % capacity

Tổng hợp

[ ] Default to Array, dùng Linked List chỉ khi có lý do cụ thể
[ ] Implement được Queue bằng 2 Stacks (amortized O(1))
[ ] Hiểu cache locality ảnh hưởng performance thực tế như thế nào

📍 Trang tiếp theo

Bạn đã nắm vững 4 cấu trúc tuyến tính — nền tảng cho mọi thứ phía trước. Trong bài tiếp theo, chúng ta sẽ bước vào thế giới phi tuyến tính: Tree, Heap, và Graph — nơi dữ liệu không còn nằm trên một hàng mà phân nhánh, lồng nhau, và kết nối chằng chịt. Monotonic stack bạn vừa học sẽ xuất hiện lại khi giải bài trên tree. Queue sẽ là trái tim của BFS trên graph.

→ Trees, Heaps & Graphs

Cấu trúc tuyến tính — Array, Linked List, Stack, Queue ​

Bảng so sánh tổng quan ​

Array — Nền tảng của mọi thứ ​

Memory Layout ​

Dynamic Array — Amortized O(1) Append ​

Cài đặt cơ bản ​

Khi nào Array thất bại ​

Linked List — Khi nào thực sự cần? ​

Memory Layout ​

Singly vs Doubly Linked List ​

Cài đặt Node và thao tác cơ bản ​

Sự thật không thoải mái ​

Stack — LIFO và Monotonic Stack Pattern ​

Mô hình tư duy: Call Stack ​

Thao tác cơ bản ​

Valid Parentheses — Bài kinh điển ​

Monotonic Stack — Interview Gold Mine ​

Queue — FIFO, BFS, và Deque ​

Queue Basics ​

Cài đặt cơ bản ​

Circular Buffer — Queue trên mảng cố định ​

Deque — Swiss Army Knife ​

Memory Battle: Array vs Linked List ​

Bài tập luyện tập ​

🧠 Quiz ​

Câu 1: Implement Queue using two Stacks — amortized time cho dequeue? ​

Câu 2: Tại sao std::vector (C++) nhanh hơn std::list cho insert ở giữa khi n nhỏ? ​

Câu 3: Khi nào dùng Circular Buffer thay vì Dynamic Queue? ​

🐛 Spot the Bug ​

🧩 Parsons Problem ​

Checklist ghi nhớ ​

📍 Trang tiếp theo ​

Cấu trúc tuyến tính — Array, Linked List, Stack, Queue

Bảng so sánh tổng quan

Array — Nền tảng của mọi thứ

Memory Layout

Dynamic Array — Amortized O(1) Append

Cài đặt cơ bản

Khi nào Array thất bại

Linked List — Khi nào thực sự cần?

Memory Layout

Singly vs Doubly Linked List

Cài đặt Node và thao tác cơ bản

Sự thật không thoải mái

Stack — LIFO và Monotonic Stack Pattern

Mô hình tư duy: Call Stack

Thao tác cơ bản

Valid Parentheses — Bài kinh điển

Monotonic Stack — Interview Gold Mine

Queue — FIFO, BFS, và Deque

Queue Basics

Cài đặt cơ bản

Circular Buffer — Queue trên mảng cố định

Deque — Swiss Army Knife

Memory Battle: Array vs Linked List

Bài tập luyện tập

🧠 Quiz

Câu 1: Implement Queue using two Stacks — amortized time cho dequeue?

Câu 2: Tại sao `std::vector` (C++) nhanh hơn `std::list` cho insert ở giữa khi n nhỏ?

Câu 3: Khi nào dùng Circular Buffer thay vì Dynamic Queue?

🐛 Spot the Bug

🧩 Parsons Problem

Checklist ghi nhớ

📍 Trang tiếp theo