Một cấu trúc danh sách đơn giản nhất mà ta đã từng biết đó chính là phương pháp cài đặt danh sách liên kết kề sử dụng mảng. Việc cài đặt danh sách bằng mảng cho thấy sự kém hiệu quả trong nhiều vấn đề như: kích thước cố định, thừa (hoặc thiếu) vùng nhớ, các phần tử tuần tự không linh động. Vì vậy, cần có một cấu trúc dữ liệu đáp ứng được yêu cầu: linh động hơn, có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống. Thế nên cấu trúc danh sách liên kết được ra đời để khắc phục các nhược điểm trên!
1.Danh sách liên kết đơn là gì?
Danh sách liên kết đơn (Single linked list) là chuỗi các Node (nút) được tổ chức theo thứ tự tuyến tính, các phần tử thuộc danh sách liên kết đơn được gọi là các Node và chúng nằm dải rác trong bộ nhớ.
Trong danh sách liên kết đơn mỗi phần tử đều liên kết với phần tử đứng sau nó trong danh sách:
Trong đó:
- Phần hình tròn màu xanh đầu tiên là bắt đầu danh sách
- Phần hình tròn màu đỏ ở cuối là địa chỉ NULL cũng là phần kết thúc danh sách
- Các hình chữ nhật được chia thành hai vùng được coi là một NODE
- A, B, C, D được coi là dữ liệu (data) của một NODE
- Các con trỏ được trỏ tới các vị trí của node tiếp theo trong danh sách liên kết đơn
2.Node trong danh sách liên kết đơn
Mỗi Node trong danh sách liên kết đơn được chia thành hai thành phần chính đó là:
- Phần data: lưu trữ dữ liệu của node
- Phần liên kết: Lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối cùng trong danh sách.
Cách khai báo một Node trong danh sách liên kết đơn bằng C/C++:
struct Node
{
//khai bao thanh phan du lieu co kieu int
int data;
//khai bao con tro next co kieu Node
Node *next;
};
typedef struct Node NODE;
Trong đó:
- int data: là dữ liệu của mỗi Node (ở đây dữ liệu này mang kiểu int, ta hoàn toàn có thể thay đổi thành float hay kiểu SinhVien tùy vào mục đích khác nhau)
- Node *next: Là con trỏ mang chính kiểu dữ liệu Node và có chức năng trỏ đến địa chỉ của Node tiếp theo trong danh sách
- Từ khóa typedef struct để dễ dàng trong việc gọi và sử dụng NODE sau này!
3.Cài đặt danh sách liên kết đơn
Các thư viện cần thiết cho việc cài đặt danh sách liên kết đơn là:
#include <stdio.h> #include <stdlib.h>
3.1 Khai báo một cấu trúc danh sách liên kết đơn
Trong danh sách liên kết đơn ban đầu, mặc định sẽ có hai thành phần và cũng chính là hai Node là: pHead và pTail
- Con trỏ pHead sẽ được dùng để lưu trữ địa chỉ phần tử đầu danh sách: NODE* pHead;
- Để tiện lợi, có thể sử dụng thêm một con trỏ pTail lưu địa chỉ phần tử cuối danh sách: NODE* pTail;
Cách khai báo một danh sách liên kết đơn mặc định có hai Node là NODE* pHead; và NODE* pTail;
struct list{
//thanh phan dau danh sach
NODE *pHead;
//thanh phan cuoi danh sach
NODE *pTail;
};
typedef struct list LIST;
Trong đó:
- NODE* pHead; là node đầu tiên của danh sách
- NODE* pTail; là node cuối cùng của danh sách
Chú ý rằng để quản lý một DSLK đơn ta chỉ cần biết địa chỉ phần tử đầu danh sách. Vì thế hãy ghi nhớ lại cách khai báo một node trong danh sách liên kết đơn (xem lại ở phần 2) và cách để khai báo một danh sách liên kết đơn gồm 2 node NODE* pHead; và NODE* pTail; chúng sẽ được sử dụng rất nhiều cho những thao tác với cấu trúc danh sách liên kết đơn ở những bài sau!
3.2 Hàm khởi tạo danh sách liên kết đơn
Mặc định ban đầu khi danh sách được khởi tạo, các thành phần NODE* pHead và NODE* pTail của danh sách được coi là rỗng (NULL). Vì vậy, hàm khởi tạo là thao tác gán giá trị con trỏ quản lý địa chỉ đầu (NODE* pHead) và cuối (NODE *pTail) của danh sách về con trỏ NULL.
Hàm void KhoiTao(LIST &ds) dưới đây nhận đối số đầu vào là tham chiếu LIST &ds sau đó thực hiện việc gán địa chỉ phần tử đầu danh sách và địa chỉ cuối danh sách về NULL
void KhoiTao(LIST &ds){
//dat dia chi dau danh sach bang NULL
ds.pHead = NULL;
//dat dia chi cuoi danh sach bang NULL
ds.pTail = NULL;
}
3.3 Hàm kiểm tra rỗng trong danh sách liên kết đơn
Một hàm kiểm tra rỗng có chức năng kiểm tra xem danh sách liên kết đơn đó đã có phần tử hay không có phần tử? Việc kiểm tra rỗng này để thuận tiện hơn cho việc lấy ra phần tử trong danh sách hoặc thêm mới một phần tử vào danh sách.
Hàm int KiemTraRong(LIST ds) dưới đây nhận đầu vào là LIST ds và thực hiện kiểm tra xem phần tử đầu và phần tử cuối của danh sách có là NULL hay không? Nếu là NULL thì danh sách đó được coi là rỗng (NULL). Tuy nhiện, vì trong danh sách liên kết đơn, các phần tử được truy cập tuần tự nên điều kiện cần kiếm tra được rút gọn thành nếu phần tử đầu tiên của danh sách NULL thì toàn bộ danh sách đều là NULL!
int KiemTraRong(LIST ds){
//neu phan tu dau danh sach NULL
if (ds.pHead == NULL){
//tra ve 1 la co NULL
return 1;
}
//truong hop nguoc lai tra ve khong null
return 0;
}
3.4 Hàm tạo một NODE trong danh sách liên kết đơn
Mỗi NODE trong danh sách liên kết đơn ta tưởng tượng giống như một phần tử của mảng vậy. Tuy nhiên một NODE lại khác một phần tử mảng ở việc có 2 thành phần đó là thành phần data và thành phần liên kết. Vì thế , để có được một NODE ta cần phải khai báo được 2 thành phần trên.
Hàm NODE* TaoNode(int x) dưới đây có đầu vào là int x hàm này thực hiện việc tạo ra một NODE mới trong danh sách liên kết đơn với thành phần data = x và thành phần liên kết trỏ đến NULL
NODE* TaoNode(int x) {
//tao mot node p moi
NODE *p;
p = new NODE;
//neu p==NULL thi khong du bo nho va ket thuc viec tao node
if (p==NULL) {
printf ("KHONG DU BO NHO");
return NULL;
}
//gan thanh phan data = x
p->data=x;
//gan con tro next = NULL
p->next=NULL;
//tra ve node p da tao
return p;
}
Chú ý:
- Int x được truyền vào hàm trên chỉ là một kiểu dữ liệu minh họa cho thành phần data của NODE. Tùy vào bài toán mà ta có thể truyền vào kiểu dữ liệu khác nhau ví dụ như float, char hay một kiểu SinhVien mà ta tự định nghĩa.
- Hàm trả về là một NODE đã được tạo thành công!
Hàm trên được sử dụng chính cho công việc thêm phần tử vào trong danh sách liên kết đơn ở những bài sau. Vì thế hay ghi nhớ lại hàm trên!
4.Chương trình cài đặt danh sách liên kết đơn hoàn chỉnh
Chương trình dưới đây là một chương trình cài đặt một danh sách liên kết đơn hoàn chỉnh (đầy đủ các hàm ở trên).
#include <stdio.h>
#include <stdlib.h>
struct Node
{
//khai bao thanh phan du lieu co kieu int
int data;
//khai bao con tro next co kieu Node
Node *next;
};
typedef struct Node NODE;
struct list{
//thanh phan dau danh sach
NODE *pHead;
//thanh phan cuoi danh sach
NODE *pTail;
};
typedef struct list LIST;
void KhoiTao(LIST &ds){
//dat dia chi dau danh sach bang NULL
ds.pHead = NULL;
//dat dia chi cuoi danh sach bang NULL
ds.pTail = NULL;
}
int KiemTraRong(LIST ds){
//neu phan tu dau danh sach NULL
if (ds.pHead == NULL){
//tra ve 1 la co NULL
return 1;
}
//truong hop nguoc lai tra ve khong null
return 0;
}
NODE* TaoNode(int x) {
//tao mot node p moi
NODE *p;
p = new NODE;
//neu p==NULL thi khong du bo nho
if (p==NULL) {
printf ("KHONG DU BO NHO");
return NULL;
}
//gan thanh phan data = x
p->data=x;
//gan con tro next = NULL
p->next=NULL;
//tra ve node p da tao
return p;
}
int main(){
//khai bao mot danh sach
LIST ds;
//khoi tao danh sach
KhoiTao(ds);
//kiem danh sach co rong hay khong
KiemTraRong(ds);
}
Chú ý: Các hàm TaoNode(), KhoiTao(), KiemTraRong() và các struct list cũng như struct Node sẽ được sử dụng rất nhiều ở những bài tiếp theo vì thế việc hiểu và ghi nhớ chúng là bắt buộc!
