Lý thuyết Tin học 11 (Cánh diều) Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

Lý thuyết Tin học 11 Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

A. Lý thuyết Cấu trúc dữ liệu danh sách liên kết và ứng dụng

1. Cấu trúc danh sách liên kết

- Danh sách liên kết (linked list) gồm các nút (node) với phần Data chứa dữ liệu và phần liên kết Next trỏ đến nút liền kề sau.

- Phần Next được gọi là con trỏ Next, được thể hiện bằng kí hiệu mũi tên “→” và là kiểu dữ liệu đặc biệt, gọi là kiểu con trỏ.

- Đuôi danh sách là nút cuối cùng trong danh sách, được thể hiện bằng hình vẽ Next trỏ đến Null.

- Con trỏ Tail trỏ đến nút đuôi của danh sách.

- Đầu danh sách được minh hoạ bằng mũi tên Head trỏ đến nút đầu tiên trong danh sách.

- Phân biệt nút với phần Data: Nên phân biệt rõ ràng giữa một nút và phần Data chứa dữ liệu trong nút. - - Trên hình minh hoạ, dữ liệu được thể hiện bằng các chữ cái A, B, C, D.

- Sử dụng tên nút: Để đơn giản, ta gọi nút A, nút B, nút C, nút D để thể hiện sự liên kết giữa các nút.

- Sử dụng A.Next: Để thể hiện con trỏ từ nút A đến nút đứng sau nó, ta sử dụng A.Next.

a) Sự khác nhau giữa danh sách liên kết và mảng 

- So với mảng, danh sách liên kết có những điểm khác biệt sau:

+ Ghi lưu con trỏ để truy cập nút C: tmp = B.Next, tức là tmp →C.

+ Cho B.Next trỏ đến nút đứng sau C (là nút D): B.Next =C.Next.

+ Sử dụng tmp để giải phóng phần bộ nhớ dành cho C.

+ Gỡ bỏ nút đầu hay cuối danh sách chỉ mất thời gian O(1),  không phụ thuộc vào độ dài danh sách

- Danh sách nối kép có thêm con trỏ Prev trỏ đến nút trước đó.

b) Thời gian thực hiện các phép toán của danh sách liên kết

- Phép tìm kiếm: Tìm nút chứa dữ liệu X để xử lí, phải tìm kiếm tuần tự từ đầu danh sách, độ phức tạp O(n) với n là số nút của danh sách.

- Thêm và gỡ bỏ nút ở bất cứ vị trí nào đều có thời gian thực hiện là O(1), ưu điểm so với danh sách mảng.

- Danh sách liên kết tốn thêm chỗ để lưu trữ con trỏ Next, là nhược điểm so với danh sách mảng.

2. Ứng dụng của danh sách liên kết

- Sử dụng cấu trúc móc nối để liên kết các nút thành một dãy tuần tự tạo ra kiểu danh sách rất linh hoạt. 

- Danh sách liên kết phát huy ưu điểm trong những trường hợp thường xuyên phải:

+ Thêm phần tử, gỡ bỏ phần tử ở bất cứ vị trí nào trong danh sách;

+ Độ dài danh sách thay đổi nhanh và nhiều trong quá trình sử dụng. 

Một số ví dụ ứng dụng danh sách liên kết

- Danh sách nhóm top N là danh sách các phần tử đứng đầu được sắp xếp theo thứ tự giảm dần.

- Các thao tác cập nhật danh sách top N bao gồm: gỡ bỏ phần tử ở vị trí bất kì và chèn phần tử vào vị trí bất kì.

- Độ dài N của danh sách có thể thay đổi và được chọn là 5, 10, 20,...

- Danh sách top N thường được sử dụng để phát lại các phần tử theo nhiều cách khác nhau như trình tự ngược lại, trình tự ngẫu nhiên, vv.

- Một số bài toán thực tế cần mô hình hoá một mạng lưới hay cấu trúc phân cấp hình cây, không thể dùng danh sách.

– Danh sách liên kết phù hợp cho việc thể hiện mối liên kết giữa các nút linh hoạt và cập nhật được các thay đổi.

Danh sách liên kết trong Python

- Python hỗ trợ cấu trúc danh sách liên kết với đầy đủ các phép toán danh sách, phù hợp cho các ứng dụng đơn giản.

- Tuy nhiên, lập trình danh sách liên kết phức tạp đòi hỏi kiến thức về lập trình hướng đối tượng, không được đào tạo trong chương trình bậc phổ thông.

- Để biểu diễn một hàng đợi thông thường (queue) trong thực tế, chỉ cần dùng append và popleft.

- Python có các kiểu dữ liệu sẵn trong thư viện collections, hỗ trợ thực hiện các kiểu danh sách đặc thù tốt hơn so với kiểu danh sách tổng quát.

- Kiểu deque trong thư viện collections là kiểu danh sách được tối ưu cho việc thêm và lấy ra phần tử ở vị trí cuối hoặc đầu danh sách. Các phép thêm vào và lấy ra đều có độ phức tạp thời gian O(1), hiệu quả hơn kiểu list.

- Trong Python, có thể sử dụng kiểu từ điển để thể hiện cây phân cấp hay đồ thị.

- Có các gói thư viện bên ngoài cho Python đã làm sẵn danh sách liên kết để sử dụng khi cần thiết.

B. Bài tập Cấu trúc dữ liệu danh sách liên kết và ứng dụng

Đang cập nhật…

Xem thêm các bài lý thuyết Tin học 11 sách Cánh diều hay, chi tiết tại: 

Lý thuyết Bài 6: Kiểm thử và sửa lỗi chương trình

Lý thuyết Bài 7: Lập trình giải bài toán tìm kiếm

Lý thuyết Bài 8: Lập trình một số thuật toán sắp xếp

Lý thuyết Bài 9: Lập trình thuật toán sắp xếp nhanh

Lý thuyết Bài 10: Thiết kế và chương trình từ trên xuống và phương pháp Mô đun hóa