[DSA] Danh sách liên kết (Linked List)

Nguồn: Click here

1. Danh sách liên kết là gì?

Danh sách liên kết (Linked list) là một cấu trúc dữ liệu lưu trữ các đối tượng dữ liệu có thể thay đổi kích thước một cách linh hoạt. Nó được cấu thành bởi một tập hợp các nút (node) được liên kết với nhau theo một cách nhất định.

Mỗi nút trong danh sách liên kết chứa dữ liệu cần lưu trữ cùng với một tham chiếu đến nút tiếp theo trong danh sách (nếu có). Điều này tạo ra một chuỗi các nút được liên kết với nhau để tạo thành danh sách.

Danh sách liên kết có thể được sử dụng để giải quyết các vấn đề liên quan đến việc lưu trữ và truy xuất các dữ liệu một cách hiệu quả hơn, so với một mảng (array) vì danh sách liên kết cho phép chèn hoặc xóa các nút một cách dễ dàng và không cần phải di chuyển các nút khác trong danh sách.

2. Các loại danh sách liên kết:

• Danh sách liên kết đơn (Singly linked list): Đây là loại danh sách liên kết phổ biến nhất, mỗi nút trong danh sách liên kết đơn chứa dữ liệu cần lưu trữ cùng với một tham chiếu đến nút tiếp theo trong danh sách. Đây là loại danh sách đơn giản nhất và dễ dàng triển khai.
• Danh sách liên kết kép (Doubly linked list): Đây là loại danh sách liên kết có tính năng tương tự như danh sách liên kết đơn, nhưng mỗi nút chứa thêm một tham chiếu đến nút trước đó trong danh sách. Do đó, danh sách liên kết kép cho phép truy cập đến cả nút trước và nút sau nút hiện tại. Tuy nhiên, danh sách liên kết kép tốn nhiều bộ nhớ hơn so với danh sách liên kết đơn.
• Danh sách liên kết vòng (Circular linked list): Đây là loại danh sách liên kết trong đó nút cuối cùng trong danh sách liên kết đơn được liên kết với nút đầu tiên, tạo thành một vòng lặp liên kết. Do đó, các phép toán trên danh sách liên kết vòng được thực hiện trên một vòng lặp, nghĩa là việc duyệt danh sách có thể tiếp tục lặp lại vô hạn nếu không có điều kiện dừng rõ ràng.

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

Danh sách liên kết là một cấu trúc dữ liệu linh hoạt và được sử dụng trong rất nhiều ứng dụng khác nhau. Dưới đây là một số ví dụ phổ biến về việc sử dụng danh sách liên kết:

• Danh sách sinh viên trong một lớp học: Danh sách liên kết có thể được sử dụng để lưu trữ thông tin của tất cả sinh viên trong một lớp học, với mỗi sinh viên tương ứng với một nút trong danh sách. Thông tin của mỗi sinh viên bao gồm tên, tuổi, mã sinh viên, điểm số, v.v...
• Stack (ngăn xếp): Danh sách liên kết có thể được sử dụng để triển khai stack (ngăn xếp). Trong stack, các phần tử được thêm và xóa theo nguyên tắc LIFO (Last In First Out).
• Queue (hàng đợi): Danh sách liên kết cũng có thể được sử dụng để triển khai queue (hàng đợi). Trong queue, các phần tử được thêm vào theo nguyên tắc FIFO (First In First Out).
• Danh sách liên kết trong các trò chơi: Các game đòi hỏi sử dụng danh sách liên kết để lưu trữ các đối tượng, nhân vật, vật phẩm trong game. Ví dụ, danh sách liên kết có thể được sử dụng để lưu trữ các vật phẩm mà người chơi có thể thu thập trong game.
• Danh sách các thư mục và tập tin trong hệ điều hành: Các hệ điều hành sử dụng danh sách liên kết để lưu trữ thông tin về các thư mục và tập tin trong hệ thống tệp của máy tính.
• Danh sách lịch sử trình duyệt: Các trình duyệt web sử dụng danh sách liên kết để lưu trữ lịch sử các trang web mà người dùng đã truy cập.

 3. Ưu điểm và nhược điểm của danh sách liên kết

Danh sách liên kết (Linked List) là một cấu trúc dữ liệu dùng để lưu trữ một tập hợp các phần tử trong đó mỗi phần tử được gọi là nút (node) và chứa dữ liệu cùng với một liên kết (link) đến phần tử tiếp theo trong danh sách.

3.1. Ưu điểm của danh sách liên kết:

• Có thể thêm và xóa phần tử ở bất kỳ vị trí nào trong danh sách với độ phức tạp O(1) (đối với danh sách liên kết đơn).
• Kích thước của danh sách không cần được khai báo trước và có thể thay đổi theo thời gian.
• Sử dụng địa chỉ con trỏ để trỏ đến các phần tử trong danh sách giúp tiết kiệm không gian bộ nhớ, đặc biệt là đối với các danh sách có số lượng phần tử lớn.
  

3.2. Nhược điểm của danh sách liên kết:

• Không có cách để truy cập ngẫu nhiên vào một phần tử bất kỳ trong danh sách. Ta phải duyệt từ đầu danh sách đến phần tử cần truy cập, đây là một hoạt động đòi hỏi độ phức tạp tuyến tính và không hiệu quả đối với các danh sách có số lượng phần tử lớn.
• Tốc độ truy cập vào các phần tử của danh sách liên kết chậm hơn so với mảng vì cần phải truy cập thông qua con trỏ.
• Các chuỗi nút (sequence) trong danh sách liên kết không được cấp phát liên tục trong bộ nhớ, điều này có thể dẫn đến tình trạng "fragmentation" và ảnh hưởng đến hiệu năng của hệ thống.
  

4. Ví dụ về danh sách liên kết

1. Việc lưu trữ và quản lý danh sách các tài liệu trong thư viện. Mỗi tài liệu được lưu trữ dưới dạng một nút trong danh sách liên kết, với các trường thông tin như tên tài liệu, tác giả, ngày xuất bản, số lượng bản in, v.v... Các tài liệu được thêm vào danh sách bằng cách thêm một nút vào đầu danh sách, và có thể được tìm kiếm và truy xuất thông tin từ danh sách. Việc sử dụng danh sách liên kết giúp cho việc thêm, xóa và sửa thông tin của các tài liệu trở nên dễ dàng và hiệu quả hơn.
2. Việc lưu trữ và quản lý các phần tử trong một danh sách câu hỏi trắc nghiệm. Mỗi câu hỏi trắc nghiệm được lưu trữ dưới dạng một nút trong danh sách liên kết, với các trường thông tin như nội dung câu hỏi, các lựa chọn đáp án và đáp án đúng. Các câu hỏi có thể được thêm vào danh sách bằng cách thêm một nút vào cuối danh sách, và các câu hỏi có thể được truy xuất và xử lý thông qua danh sách. Việc sử dụng danh sách liên kết trong trường hợp này giúp cho việc thêm, xóa và sửa thông tin của các câu hỏi trở nên dễ dàng và linh hoạt hơn.