Data Structures in JS/TS

JS là một ngôn ngữ bậc cao, nên nhiều cấu trúc dữ liệu được tích hợp sẵn (Built-in) rất tiện lợi, nhưng cũng có những thứ bạn phải tự xây dựng (Custom).

1. Built-in Data Structures

Array (Mảng)

Mảng trong JS là dynamic array (có thể co giãn).

• push/pop (cuối): $O(1)$.
• shift/unshift (đầu): $O(n)$ -> Cực kỳ tốn kém vì phải đánh lại index toàn bộ mảng. Tránh dùng unshift trong vòng lặp lớn.

Hash Map (Object & Map)

• Object {}: Key luôn là chuỗi. Không đảm bảo thứ tự key (mặc dù các trình duyệt hiện đại hầu như giữ thứ tự insert).
• Map: Key có thể là bất cứ kiểu gì (số, object, function). Hiệu năng thêm/xóa tốt hơn Object khi số lượng lớn. Giữ thứ tự insert.
• Set: Chỉ chứa giá trị duy nhất (Unique values). Dùng để khử trùng (deduplicate).

const seen = new Set([1, 2, 2, 3]); // Set(3) {1, 2, 3}
const hasOne = seen.has(1); // O(1)

2. Custom Data Structures (Tự xây dựng)

Stack (Ngăn xếp) - LIFO (Last In, First Out)

Dùng mảng JS là đủ.

• Push: arr.push()
• Pop: arr.pop()
• Peek: arr[arr.length - 1]

Queue (Hàng đợi) - FIFO (First In, First Out)

Dùng mảng JS với push và shift là cách đơn giản nhất, nhưng shift là $O(n)$. Nếu cần hiệu năng cao ($O(1)$) cho hàng đợi lớn, hãy xây dựng Linked List hoặc dùng 2 con trỏ (một con trỏ đầu, một con trỏ cuối).

Linked List (Danh sách liên kết)

Ít dùng trực tiếp trong làm app, nhưng quan trọng trong phỏng vấn.

class ListNode {
    val: number;
    next: ListNode | null = null;
    constructor(val: number) { this.val = val; }
}

Tree (Cây) & Graph (Đồ thị)

JSON bản chất là một Tree. DOM bản chất là một Tree. Dependency Network (các package phụ thuộc nhau) là một Graph (DAG).

3. Khi nào dùng cái gì?