Wikipedia:Bàn tham khảo/Liên kết đơn và mảng trong lập trình

Cho tôi hỏi sự khác biệt của việc dùng danh sách liên kết đơn và dùng cấu trúc mảng . Ưu điểm và khuyết điểm của hai cách dùng trên.Xin cảm ơn nhiều.selecao338@yahoo.com.vn

Cấu trúc đơn và mảng khác nhau về kiến trúc cơ bản:

Ở đây tôi chỉ so sánh cho bạn hai khái niệm "cổ điển" đơn giản nhất vì trong cấu trúc liên kết đơn và khái niệm cấu trúc mảng ngày nay đã có nhiều đổi mới. (Thí dụ trong một số ngôn ngữ người ta đã mở rộng khái niệm mảng mới hơn như là dạng mảng động và dạng mảng có quản lý vùng nhớ; rất tiếc bạn phải cần nhiều kiến thức đặc trưng về ngôn ngữ lập trình chuyên biệt đó để hiểu thêm thí dụ như trong C# và C++ chuẩn mới.)

Liên kết đơn sử dụng khái niệm căn bản là "con trỏ" để tạo ra một mối liên kết kiểu liên tục từ "node" này đến "node" tới. Nghĩa là trong mỗi node tự nó có chứa 1 con trỏ chỉ tới node theo sau và một đơn vị nhớ (theo kiểu được định nghĩa của liên kết). Con trỏ ở node cuối sẽ là NULL, tức là không chỉ tới chỗ nào.

Trong khi đó, mảng là một vùng nhớ liên tục (tương đối) các điạ chỉ (được bắt đầu từ địa chỉ A₀ và kết thúc ở địa chỉ A_n chẳng hạn) và chỉ cần dùng đúng 1 con trỏ chỉ vào địa chỉ đầu tiên (tức là A₀).

Từ hai khác biệt mấu chốt trên bạn có thể suy ra nhiều khác biệt chỉ xin nêu vài khác biệt dễ thấy nhất:

Cách khai báo và gán dữ liệu khác nhau: Việc gán giá trị cho phần tử trong mảng chỉ cần cho địa chỉ (A[n] = dữ_liệu) hay phép toán cộng trên tên con trỏ (A+n = dữ_liệu, nếu kiểu dữ liệu là 1 byte) và dữ liệu có thể nằm ở bất vị trí nào (từ A[0] đến A[n] cho mảng n+1 phần tử). Trong khi đó, liên kết đơn bắt buộc bạn phải gán giá trị từ node đầu, kế là node thứ nhì, tới node thứ ba ... đến node cuối.
Cách truy cập dữ liệu khác nhau: Trong mảng bạn hoàn toàn biết rõ và có thể truy cập từ bất kì vị trí nào (A[i] với i=0,1,...n) mà không cần làm thêm động tác nào nếu như các phần tử này đã được gán dữ liệu. Trong khi đó, để đọc được dữ liệu trên liên kết đơn bạn bắt buộc phải di chuyển từ node đầu (hay node đang xử lí) một cách tăng dần cho đến chỗ mà bạn muốn tìm. Hậu quả sự khác nhau này là: dùng liên kết đơn thì máy chạy luôn luôn chậm hơn dùng mảng. Do đó, ảnh hưởng là việc xếp thứ tự các phần tử qua mảng lúc nào cũng tiện lợi hơn bằng liên kết đơn.
Việc trả về cho bộ nhớ khi không còn dùng nữa cũng vậy. Tùy theo ngôn ngữ để khai báo hủy nhưng lúc nào mảng cũng đơn giản hơn và thường chỉ 1 câu lệnh (toán tử delete trong C/C++). Nhưng trong liên kết bạn phải tiến hành hủy và trả về cho bộ nhớ từ node đầu đi dọc xuống cho đến node cuối.

Như vậy tại sao người ta lại hay dùng liên kết đơn? Đó là vì các lí do sau:

Dùng liên kết có thể tận dụng được kho nhớ khổng lồ của máy tính. Bạn có thể khai báo cho đến khi máy hoàn toàn kiệt quệ. Nghĩa là bạn không cần có một vùng nhớ liên tục như trong mảng mà chỉ cần con trỏ chỉ tới địa chỉ node kế. Như vậy dùng liên kết luôn luôn tối ưu hơn về việc quản lý bộ nhớ. Và đây là điểm cần yếu cho các dạng programming dùng cơ sở dữ liệu (vì lượng dữ liệu thường khổng lồ như danh sách từ điển bách khoa chẳng hạn!)
Lỗi "out-of-range" chỉ xảy ra đối với mảng (nghĩa là bạn đăng kí có 10 phần tử nhưng lại truy cập hay gán dữ liệu cho phần tử 11 trong mảng).
Ngoài ra, xin nói thêm ra ngoài câu hỏi, nếu dùng các cấu trúc dữ liệu phức tạp (như dữ liệu dùng cho gia phả chẳng hạn) thì liên kết phức sẽ giúp bạn tiến hành tổ chức quản lí dữ liệu dễ dàng không phí các chỗ nhớ hơn là dùng mảng đa chiều.

Cấu trúc đơn và mảng giống nhau: cả hai đều dùng để chứa và xử lí dữ liệu

Để tiện tham khảo thêm, cần ít hiểu biết Anh ngữ bạn có thể đọc thêm vài chi tiết so sánh từ đây

Chúc vui vẻ đầu năm

Làng Đậu