Tin học 11 Cánh diều Chủ đề FCS Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

- 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.

Minh hoạ một danh sách liên kết có 4 nút

- 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.

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 đó.

Mô hình một danh sách nối kép có 4 nút

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.

- 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.

Em hãy cho biết danh sách mảng có nhược điểm gì?

Hướng dẫn giải:

Danh sách mảng có nhược điểm sau: Không thể thay đổi kích thước của mảng khi chương trình đang thực hiện.

Học xong bài này, em sẽ: Trình bày được cấu trúc dữ liệu danh sách liên kết và một số ứng dụng của nó.

Như vậy là các em đã xem qua bài giảng Bài 15 Chủ đề FCS SGK Tin học 11 Cánh diều Khoa học máy tính. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Cánh diều Chủ đề FCS Bài 15.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Cánh diều Chủ đề FCS Bài 15 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 146 SGK Tin học 11 Cánh diều - CD

Vận dụng trang 149 SGK Tin học 11 Cánh diều - CD

Câu hỏi 1 trang 149 SGK Tin học 11 Cánh diều - CD

Câu hỏi 2 trang 149 SGK Tin học 11 Cánh diều - CD

Câu hỏi 3 trang 149 SGK Tin học 11 Cánh diều - CD

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!