Trong thế giới lập trình, việc quản lý bộ nhớ và cấu trúc dữ liệu hiệu quả là yếu tố then chốt để xây dựng các ứng dụng mạnh mẽ và tối ưu. Danh Sách Móc Nối (linked list) nổi lên như một cấu trúc dữ liệu linh hoạt, cho phép thao tác dữ liệu một cách động, khác biệt với các mảng có kích thước cố định. Bài viết này sẽ đi sâu vào khái niệm, các loại danh sách móc nối, cách chúng được cài đặt và ứng dụng thực tế, đặc biệt là trong việc triển khai các cấu trúc dữ liệu trừu tượng như ngăn xếp (stack) và hàng đợi (queue).
I. Con Trỏ và Cấp Phát Bộ Nhớ Động: Nền Tảng Của Danh Sách Móc Nối
Nội dung
Để hiểu về danh sách móc nối, trước tiên cần nắm vững khái niệm về con trỏ và cấp phát bộ nhớ động.
Con Trỏ (Pointer)
Con trỏ là một biến đặc biệt, có giá trị là địa chỉ của một biến khác trong bộ nhớ. Nó cho phép chúng ta truy cập và thao tác trực tiếp với dữ liệu tại địa chỉ đó.
Các thao tác cơ bản với con trỏ:
- Khởi tạo (khai báo):
int *P;– Khai báo một con trỏ kiểu số nguyên. - Lấy địa chỉ của một đối tượng:
int A = 20; P = &A;– Con trỏPbây giờ trỏ đến biếnA. - Truy cập vào đối tượng được trỏ:
*P = 20;– Gán giá trị 20 cho biến màPđang trỏ tới (tức là biếnA). - Cấp phát bộ nhớ động:
P = new int;– Cấp phát một vùng nhớ đủ cho một số nguyên và gán địa chỉ của vùng nhớ đó cho con trỏP. - Giải phóng bộ nhớ động:
delete P;– Giải phóng vùng nhớ mà con trỏPđang trỏ tới, tránh rò rỉ bộ nhớ.
Cấp Phát Bộ Nhớ Động
Khác với cấp phát bộ nhớ tĩnh (khi khai báo biến thông thường), cấp phát bộ nhớ động cho phép chương trình yêu cầu một lượng bộ nhớ cần thiết trong quá trình chạy. Điều này đặc biệt hữu ích khi chúng ta không biết trước kích thước của dữ liệu cần lưu trữ, như trong trường hợp của danh sách móc nối.
II. Cấu Trúc Lưu Trữ Móc Nối: Tổ Chức Dữ Liệu Linh Hoạt
Danh sách móc nối là một cấu trúc dữ liệu bao gồm một tập hợp các phần tử dữ liệu không nhất thiết phải liền kề nhau trong bộ nhớ. Thay vào đó, mỗi phần tử (gọi là nút – node) chứa cả dữ liệu và một hoặc nhiều con trỏ để liên kết đến các nút khác.
Mô Tả Cấu Trúc Nút
Tại mỗi nút trong danh sách móc nối, thường có hai thành phần chính:
- Dữ liệu (info): Chứa giá trị hoặc thông tin của phần tử đó.
- Con trỏ (next): Trỏ đến nút kế tiếp trong danh sách.
Cấu trúc này cho phép quản lý bộ nhớ một cách linh động, dễ dàng chèn hoặc xóa phần tử mà không cần di chuyển toàn bộ cấu trúc dữ liệu như mảng.
Phân Loại Danh Sách Móc Nối
Danh sách móc nối có thể được phân loại dựa trên hai tiêu chí chính:
1. Theo Hướng Con Trỏ (Số Lượng Con Trỏ Trong Một Nút)
-
Danh sách nối đơn (Single Linked List): Mỗi nút chỉ chứa một con trỏ
next, cho phép duyệt danh sách theo một hướng duy nhất (từ đầu đến cuối).- Danh sách nối đơn thẳng: Nút cuối cùng có con trỏ
nextlàNULL. - Danh sách nối đơn vòng (Circularly Linked List): Con trỏ
nextcủa nút cuối cùng trỏ ngược về nút đầu tiên, tạo thành một vòng lặp.
- Danh sách nối đơn thẳng: Nút cuối cùng có con trỏ
-
Danh sách nối kép (Double Linked List): Mỗi nút chứa hai con trỏ:
nextL(hoặcprev): Trỏ tới nút đứng trước nó.nextR(hoặcnext): Trỏ tới nút đứng sau nó.
Điều này cho phép duyệt danh sách theo cả hai chiều (từ đầu đến cuối và ngược lại), nhưng tốn bộ nhớ hơn so với danh sách nối đơn.
2. Theo Cách Móc Nối (Vòng hoặc Thẳng)
- Danh sách nối thẳng: Truy cập vào danh sách thông qua một điểm truy nhập duy nhất (thường là con trỏ trỏ đến nút đầu tiên).
- Danh sách nối vòng: Bất kỳ nút nào trong danh sách cũng có thể được xem là điểm bắt đầu hoặc điểm truy nhập, vì tính chất vòng lặp của nó.
III. Cài Đặt Danh Sách Nối Đơn Thẳng
Danh sách nối đơn thẳng là dạng cơ bản nhất, với mỗi nút chứa dữ liệu và một con trỏ next trỏ đến nút tiếp theo. Nút cuối cùng có next là NULL.