𝗖𝘁𝗿𝘂̛́𝗰 𝘁𝗿𝗶̀𝗻𝗵 𝗱ữ 𝗹𝗶ệ𝘂 𝘁ｕ𝐲𝗲̂́𝗻 𝘁𝗶́𝗻𝗵 𝘁𝗿𝗼𝗻𝗴 𝗙𝗿𝗼𝗻𝘁𝗲𝗻𝗱
Các cấu trúc dữ liệu tuyến tính sắp xếp các phần tử theo một trình tự. Mỗi phần tử có một phần tử đứng trước và một phần tử đứng sau.
Arrays Mảng (Arrays) là công cụ chính trong JavaScript. Chúng sử dụng bộ nhớ liên tục. Điều này cho phép bạn truy cập bất kỳ phần tử nào thông qua chỉ số (index) của nó một cách tức thì.
- push: Thêm một phần tử vào cuối.
- unshift: Thêm một phần tử vào đầu. Thao tác này chậm vì mọi phần tử khác đều phải dịch chuyển sang phải một vị trí.
- splice: Thêm hoặc xóa các phần tử tại bất kỳ vị trí nào. Phương thức này làm thay đổi mảng ban đầu. Nó không phải là một hàm thuần túy (pure function).
Lưu ý: Khi một mảng trở nên quá lớn, JavaScript phải cấp phát một khối bộ nhớ lớn hơn và sao chép mọi thứ sang đó. Điều này gây ảnh hưởng đến hiệu năng.
Stacks Ngăn xếp (Stack) tuân theo quy tắc LIFO: Vào sau, Ra trước (Last In, First Out). Hãy tưởng tượng một chồng đĩa. Bạn chỉ có thể thêm hoặc lấy ra từ phía trên cùng.
- push: Thêm vào đỉnh.
- pop: Lấy ra từ đỉnh.
- peek: Xem phần tử ở đỉnh mà không lấy nó ra.
Queues Hàng đợi (Queue) tuân theo quy tắc FIFO: Vào trước, Ra trước (First In, First Out). Hãy tưởng tượng một hàng người đang đợi tại cửa hàng.
- push: Thêm vào cuối.
- shift: Lấy ra từ đầu.
Cảnh báo: Sử dụng shift trên một mảng sẽ rất chậm đối với các tập dữ liệu lớn. Mọi phần tử đều phải dịch chuyển sang trái để lấp đầy khoảng trống. Đối với dữ liệu có khối lượng lớn, hãy sử dụng danh sách liên kết (linked list) để thay thế.
Linked Lists Danh sách liên kết (Linked List) bao gồm các nút (nodes). Mỗi nút chứa dữ liệu và một con trỏ (pointer) trỏ đến nút tiếp theo.
- Ưu điểm: Việc thêm hoặc xóa các nút diễn ra nhanh chóng sau khi bạn tìm thấy vị trí cần thiết. Bạn chỉ cần thay đổi các con trỏ.
- Nhược điểm: Bạn không thể nhảy trực tiếp đến một chỉ số (index). Bạn phải bắt đầu từ đầu danh sách (head) và lần theo các con trỏ từng bước một. Điều này rất chậm.
Tóm tắt so sánh:
- Arrays: Tốt nhất cho việc đọc thường xuyên và dữ liệu nhỏ. Truy cập có độ phức tạp O(1).
- Linked Lists: Tốt nhất cho việc ghi thường xuyên và dữ liệu lớn. Việc chèn có độ phức tạp O(1) nếu bạn đã có sẵn nút đó.
Mẹo chuyên nghiệp cho JavaScript:
- Đừng trộn lẫn các kiểu dữ liệu trong một mảng. Việc giữ cho các kiểu dữ liệu đồng nhất sẽ giúp engine sử dụng bộ nhớ liên tục.
- Luôn sử dụng một hàm so sánh (comparator function) khi sắp xếp số.
[10, 2].sort()sẽ cho kết quả là[10, 2]vì nó sắp xếp theo kiểu chuỗi (string). - Hãy nhớ rằng hầu hết các phương thức mảng gốc (native array methods) đều làm thay đổi mảng ban đầu.