Tóm tắt

Điểm lại trọng tâm

• Mảng và danh sách liên kết là hai cấu trúc dữ liệu cơ bản, đại diện cho hai cách lưu trữ dữ liệu khác nhau trong bộ nhớ máy tính: lưu trữ liên tục (contiguous storage) và lưu trữ phân tán (scattered storage). Ưu điểm và nhược điểm của chúng bổ sung cho nhau.
• Mảng hỗ trợ truy cập ngẫu nhiên và sử dụng ít bộ nhớ hơn; tuy nhiên, thao tác chèn và xóa phần tử kém hiệu quả, và độ dài là bất biến sau khi khởi tạo.
• Danh sách liên kết đạt được hiệu quả chèn và xóa nút bằng cách sửa đổi tham chiếu (con trỏ), và có thể điều chỉnh độ dài linh hoạt; tuy nhiên, truy cập nút kém hiệu quả và tiêu thụ bộ nhớ cao hơn. Các loại danh sách liên kết phổ biến bao gồm danh sách liên kết đơn, danh sách liên kết vòng và danh sách liên kết đôi.
• Danh sách là một tập hợp các phần tử có thứ tự hỗ trợ các thao tác chèn, xóa, tìm kiếm và sửa đổi, thường được triển khai dựa trên mảng động. Nó giữ lại các ưu điểm của mảng đồng thời cho phép điều chỉnh độ dài linh hoạt.
• Sự ra đời của danh sách đã cải thiện đáng kể tính thực tế của mảng, nhưng cũng có thể gây lãng phí một số không gian bộ nhớ.
• Trong quá trình chạy chương trình, dữ liệu chủ yếu được lưu trữ trong bộ nhớ. Mảng cung cấp hiệu quả không gian bộ nhớ cao hơn, trong khi danh sách liên kết mang lại tính linh hoạt cao hơn trong việc sử dụng bộ nhớ.
• Bộ nhớ đệm cung cấp khả năng truy cập dữ liệu nhanh chóng cho CPU thông qua các cơ chế như dòng bộ đệm, nạp trước, cùng với tính cục bộ không gian và tính cục bộ thời gian, cải thiện đáng kể hiệu quả thực thi chương trình.
• Vì mảng có tỷ lệ trúng bộ đệm cao hơn, chúng thường hiệu quả hơn danh sách liên kết. Khi chọn cấu trúc dữ liệu, nên đưa ra lựa chọn thích hợp dựa trên các yêu cầu và kịch bản cụ thể.

Q & A

Q: Việc lưu trữ mảng trên ngăn xếp (stack) so với trên đống (heap) có ảnh hưởng đến hiệu quả thời gian và hiệu quả không gian không?

Các mảng được lưu trữ trên ngăn xếp và trên đống đều được lưu trữ trong vùng nhớ liên tục, do đó hiệu quả hoạt động dữ liệu cơ bản là giống nhau. Tuy nhiên, ngăn xếp và đống có những đặc điểm riêng, dẫn đến những khác biệt sau.

1. Hiệu quả phân bổ và giải phóng: Ngăn xếp là một vùng nhớ tương đối nhỏ, với việc phân bổ được trình biên dịch xử lý tự động; đống tương đối lớn hơn và có thể được phân bổ động trong mã nguồn, dễ bị phân mảnh hơn. Do đó, các thao tác phân bổ và giải phóng trên đống thường chậm hơn trên ngăn xếp.
2. Giới hạn kích thước: Bộ nhớ ngăn xếp tương đối nhỏ, trong khi kích thước đống thường bị giới hạn bởi bộ nhớ khả dụng. Do đó, đống phù hợp hơn để lưu trữ các mảng lớn.
3. Tính linh hoạt: Kích thước của mảng trên ngăn xếp phải được xác định tại thời điểm biên dịch, trong khi kích thước của mảng trên đống có thể được xác định động tại thời điểm chạy (runtime).

Q: Tại sao mảng yêu cầu các phần tử phải cùng kiểu dữ liệu, trong khi danh sách liên kết không nhấn mạnh yêu cầu này?

Danh sách liên kết được cấu tạo từ các nút, với các nút được kết nối thông qua các tham chiếu (con trỏ), và mỗi nút có thể lưu trữ các kiểu dữ liệu khác nhau, chẳng hạn như int, double, string, object, v.v.

Ngược lại, các phần tử mảng phải cùng kiểu dữ liệu để có thể xác định vị trí của chúng thông qua tính toán độ lệch (offset). Ví dụ, nếu một mảng chứa cả kiểu int và long, với các phần tử riêng lẻ lần lượt chiếm 4 byte và 8 byte, thì công thức sau đây không thể dùng để tính toán độ lệch, vì mảng chứa hai "kích thước phần tử" khác nhau.

# địa chỉ phần tử = địa chỉ cơ sở của mảng (địa chỉ phần tử đầu tiên) + kích thước phần tử * chỉ số phần tử

Q: Sau khi xóa nút P, chúng ta có cần đặt P.next thành None không?

Không nhất thiết phải sửa đổi P.next. Đứng từ góc độ của danh sách liên kết, việc duyệt từ nút đầu đến nút cuối sẽ không còn gặp nút P. Điều này có nghĩa là nút P đã được loại bỏ khỏi danh sách liên kết, và việc nút P trỏ đến đâu vào lúc này không quan trọng—nó không ảnh hưởng đến danh sách liên kết.

Đứng từ góc độ thuật toán và giải quyết bài toán, việc để nguyên kết nối con trỏ là hoàn toàn ổn miễn là logic chương trình chính xác. Đứng từ góc độ triển khai thư viện chuẩn, việc ngắt kết nối rõ ràng sẽ an toàn và rõ ràng hơn. Nếu không ngắt kết nối và nút bị xóa không được thu hồi đúng cách, nó có thể ảnh hưởng đến việc thu hồi các nút kế tiếp.

Q: Trong danh sách liên kết, độ phức tạp thời gian của thao tác chèn và xóa là \(O(1)\). Tuy nhiên, cả chèn và xóa đều yêu cầu thời gian \(O(n)\) để tìm phần tử; tại sao độ phức tạp thời gian không phải là \(O(n)\)?

Nếu phần tử được tìm thấy trước rồi mới xóa, độ phức tạp thời gian thực sự là \(O(n)\). Tuy nhiên, ưu điểm chèn và xóa \(O(1)\) trong danh sách liên kết có thể được thể hiện trong các ứng dụng khác. Ví dụ, một hàng đợi hai đầu (deque) rất phù hợp để triển khai bằng danh sách liên kết, khi đó chúng ta duy trì các biến con trỏ luôn trỏ đến nút đầu và nút cuối, và mỗi thao tác chèn hoặc xóa sẽ là \(O(1)\).

Q: Trong sơ đồ "Định nghĩa danh sách liên kết và phương thức lưu trữ", nút con trỏ màu xanh dương nhạt chiếm một địa chỉ bộ nhớ duy nhất hay chia sẻ đồng đều với giá trị nút?

Sơ đồ này là một biểu diễn định tính; biểu diễn định lượng đòi hỏi phân tích dựa trên tình huống cụ thể.

• Các kiểu giá trị nút khác nhau chiếm lượng không gian khác nhau, chẳng hạn như int, long, double và các đối tượng thực thể (instance objects), v.v.
• Lượng không gian bộ nhớ mà các biến con trỏ chiếm dụng phụ thuộc vào hệ điều hành và môi trường biên dịch được sử dụng, thông thường là 8 byte hoặc 4 byte.

Q: Việc thêm một phần tử vào cuối danh sách có luôn là \(O(1)\) không?

Nếu việc thêm một phần tử vượt quá độ dài danh sách, danh sách trước tiên phải được mở rộng trước khi thêm. Hệ thống sẽ phân bổ một khối bộ nhớ mới và chuyển tất cả phần tử từ danh sách ban đầu sang đó, trong trường hợp đó độ phức tạp thời gian trở thành \(O(n)\).

Q: "Sự ra đời của danh sách đã cải thiện đáng kể tính thực tế của mảng, nhưng có thể gây lãng phí một số không gian bộ nhớ"—sự lãng phí không gian này có phải là bộ nhớ chiếm dụng bởi các biến bổ sung như dung lượng, chiều dài và hệ số mở rộng không?

Sự lãng phí không gian này chủ yếu có hai khía cạnh: một mặt, danh sách thường thiết lập một độ dài ban đầu mà chúng ta có thể không cần sử dụng hết; mặt khác, để tránh việc mở rộng thường xuyên, việc mở rộng thường nhân với một hệ số, chẳng hạn như \(\times 1.5\). Kết quả là sẽ có nhiều vị trí trống mà thông thường chúng ta không thể lấp đầy hoàn toàn.

Q: Trong Python, sau khi khởi tạo n = [1, 2, 3], địa chỉ của 3 phần tử này liên tục, nhưng khởi tạo m = [2, 1, 3] cho thấy id của mỗi phần tử không liên tục; thay vào đó, chúng giống như trong n. Vì địa chỉ của các phần tử này không liên tục, m có còn là một mảng không?

Nếu chúng ta thay thế các phần tử danh sách bằng các nút danh sách liên kết n = [n1, n2, n3, n4, n5], thông thường 5 đối tượng nút này cũng nằm rải rác trong bộ nhớ. Tuy nhiên, với một chỉ số danh sách được chỉ định, chúng ta vẫn có thể lấy địa chỉ bộ nhớ của nút trong thời gian \(O(1)\), qua đó truy cập nút tương ứng. Điều này là do mảng lưu trữ các tham chiếu đến nút chứ không phải bản thân các nút.

Không giống như nhiều ngôn ngữ, các con số trong Python được bao bọc dưới dạng các đối tượng, và danh sách không lưu trữ chính các con số mà lưu trữ các tham chiếu đến các con số đó. Do đó, chúng ta thấy rằng cùng các số trong hai mảng có cùng một id, và địa chỉ bộ nhớ của các số này không cần phải liên tục.

Q: C++ STL có std::list đã triển khai sẵn danh sách liên kết đôi, nhưng có vẻ như một số sách thuật toán không sử dụng trực tiếp nó. Có hạn chế nào không?

Một mặt, chúng ta thường thích sử dụng mảng để triển khai thuật toán và chỉ sử dụng danh sách liên kết khi cần thiết, chủ yếu vì hai lý do.

• Chi phí không gian: Vì mỗi phần tử yêu cầu hai con trỏ bổ sung (một cho phần tử trước đó và một cho phần tử tiếp theo), std::list thường tiêu tốn nhiều không gian hơn so với std::vector.
• Không thân thiện với bộ nhớ đệm (cache unfriendliness): Vì dữ liệu không được lưu trữ liên tục, std::list có hiệu suất sử dụng bộ nhớ đệm thấp hơn. Nhìn chung, std::vector có hiệu năng tốt hơn.

Mặt khác, các trường hợp bắt buộc phải dùng danh sách liên kết chủ yếu liên quan đến cây nhị phân và đồ thị. Ngăn xếp và hàng đợi thường sử dụng stack và queue do ngôn ngữ trình bày cung cấp, chứ không phải danh sách liên kết.

Q: Phép toán res = [[0]] * n có tạo ra một danh sách 2 chiều trong đó mỗi [0] là độc lập không?

Không, chúng không độc lập. Trong danh sách 2 chiều này, tất cả các [0] thực chất là các tham chiếu đến cùng một đối tượng. Nếu chúng ta sửa đổi một phần tử, chúng ta sẽ thấy tất cả các phần tử tương ứng đều thay đổi theo.

Nếu chúng ta muốn mỗi [0] trong danh sách 2 chiều là độc lập, chúng ta có thể sử dụng res = [[0] for _ in range(n)] để đạt được điều này. Nguyên lý của phương pháp này là khởi tạo \(n\) đối tượng danh sách [0] độc lập.

Q: Phép toán res = [0] * n có tạo ra một danh sách trong đó mỗi số nguyên 0 là độc lập không?

Trong danh sách này, tất cả các số nguyên 0 đều tham chiếu đến cùng một đối tượng. Điều này là do Python sử dụng cơ chế lưu trữ đệm cho các số nguyên nhỏ (thường từ -5 đến 256) để tối đa hóa việc tái sử dụng đối tượng và nâng cao hiệu năng.

Mặc dù tất cả chúng đều tham chiếu đến cùng một đối tượng, chúng ta vẫn có thể sửa đổi từng phần tử trong danh sách một cách độc lập. Điều này là do các số nguyên trong Python là các đối tượng bất biến (immutable objects). Khi sửa đổi một phần tử, thực chất chúng ta chuyển hướng phần tử đó tham chiếu đến một đối tượng khác, chứ không phải thay đổi bản thân đối tượng ban đầu.

Tuy nhiên, khi các phần tử danh sách là các đối tượng khả biến (mutable objects) (chẳng hạn như danh sách, từ điển hoặc các thực thể lớp), việc sửa đổi một phần tử sẽ trực tiếp thay đổi chính đối tượng đó, và tất cả phần tử tham chiếu đến đối tượng đó sẽ có cùng sự thay đổi.