Các thao tác cơ bản trong danh sách gồm thao tác gì
Danh sách liên kết là một cấu trúc dữ liệu gồm các node và các liên kết giữa các node đó. Mỗi node được kết nối với một node khác (trong trường hợp danh sách liên kết đơn) hoặc hai node (trong trường hợp danh sách liên kết kép) bằng con trỏ. Các node gồm hai phần chính là phần dữ liệu và phần liên kết (các con trỏ để trỏ tới node khác), và phần bộ nhớ dánh cho chúng có thể được cấp phát bằng phương thức cấp phát động. Trong thực tế chúng ta không nhất thiết phải dùng cấp phát động để xây dựng danh sách liên kết, còn có một cách khác nữa đó là dùng mảng. Nhưng cách dùng cấp phát động hay được sử dụng hơn và có nhiều ưu điểm hơn. Một node trong danh sách liên kết đơn được cấu thành từ hai thành phần là dữ liệu và phần kết nối.
Xây dựng danh sách liên kết bởi liên kết các node với nhau.
Các điểm mạnh và điểm yếu của danh sách liên kết so với mảng: Cả danh sách liên kết và mảng đều có thể được sử dụng để chứa các dữ liệu cùng kiểu.Nhưng chúng lại có những đặc điểm riêng, và ưu điểm của cái này lại là nhược điểm của cái còn lại. Điểm mạnh:
Trước khi chèn:
Sau khi chèn:
Điểm yếu:
Xây dựng danh sách liên kết đơn với C/C++Để xây dựng một danh sách sách liên kết trước hết ta cần biết được danh sách liên kết cần bao gồm những thành phần nào và các thao tác mà ta có thể thực hiện với danh sách liên kết: Các thành phần của danh sách liên kết đơn bao gồm:
Các thao tác chính với danh sách liên kết đơn:
Ứng dụng của danh sách liên kết đơn trong thực tế: Danh sách liên kết đơn chủ yếu được dùng để xây dựng các loại cấu trúc dữ liệu khác như ngăn xếp hoặc hàng đợi hoặc đồ thị ... Đôi khi ta cần biết node ở vị trí trước. Nhưng với danh sách liên kết đơn thì không làm được. Để biết được vị trí của cả các node trước và sau node hiện tại, ta phải lưu cả vị trí của node trước và node sau. Lúc này cấu trúc của một node sẽ có dạng như sau. struct node { int data; struct node* next; struct node* prev; };Cấu trúc trên chính là cấu trúc của danh sách liên kết kép. Để hiểu hơn về danh sách liên kết kép mời bạn đọc bài tiếp theo. Bạn cũng có thể đọc thêm các bài toán về danh sách liên kết đơn tại các đường dẫn sau:
|