Trước khi tìm hiểu về danh sách liên kết đôi, bạn đọc hãy chắc chắn rằng bản thân đã thành thạo với danh sách liên kết đơn. Bởi lẽ, danh sách liên kết đôi cũng gần như có nhiều sự tương đồng với danh sách liên kết đơn. Nắm chắc danh sách liên kết đơn thì việc học danh sách liên kết đôi rất dễ dàng!
1.Danh sách liên kết đôi là gì?
Danh sách liên kết đôi (Doubly Linked List) là một dạng mở rộng của danh sách liên kết đơn. Trong danh sách liên kết đôi cũng bao gồm nhiều các Node (nút) và điều đặc biệt ở danh sách liên kết đôi là các Node liên kết với nhau với 2 con trỏ và theo hai chiều trước – sau. Nghĩa là một Node có thể trỏ đến địa chỉ của Node kế tiếp và cũng có thể trỏ đến địa chỉ của Node phía trước nó.
Qua hình miêu tả danh sách liên kết đôi ở trên ta thấy rằng:
- Các node có 2 mối liên kết là trước và sau cũng chính là 2 con trỏ, previous và next.
- Node đầu tiên của danh sách có previous = NULL (mũ tên trỏ về phần hình tròn màu đỏ là địa chỉ NULL).
2.Node trong danh sách liên kết đôi
Một Node (hay phần tử) trong danh sách liên kết đôi bao gồm 3 thành phần chính đó là:
- Phần data: lưu trữ dữ liệu của node
- Previous: Lưu trữ địa chỉ của node (hay phần tử) đứng trước. Trong trường hợp node này là node đầu tiên của danh sách thì sẽ có previous = NULL
- Next: Lưu trữ địa chỉ của node (hay phần tử) đừng sau. Trong trường hợp node này là node cuối cùng của danh sách thì sẽ có next = NULL
Cách khai báo một Node trong danh sách liên kết đôi 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 de chua dia chi phan tu sau Node *next; //khai bao con tro prev co kieu Node de chua dia chi phan tu truoc Node *prev; }; 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
- Node *prev: là con trỏ mảng kiểu Node và có chức năng trỏ đến đại chỉ của node phía trước.
- 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 đôi
Tương tự như danh sách liên kết đơn, các thư viện được dùng để cài đặt danh sách liên kết đôi vẫn là 2 thư viện:
#include <stdio.h> #include <stdlib.h>
3.1 Khai báo một cấu trúc danh sách liên kết đôi
Tương tự như danh sách liên kết đôi, một cấu trúc của danh sách liên kết đơn ban đầu được khai báo mặc định cũng sẽ có 2 thành phần chính là hai Node là: pHead và pTail
- Thành phần pHead sẽ được dùng để lưu trữ địa chỉ phần tử đầu danh sách: NODE* pHead;
- Thành phần 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 đôi ban đầu mặc định có hai Node là NODE* pHead; và NODE* pTail;
struct doulist{ //thanh phan dau danh sach NODE *pHead; //thanh phan cuoi danh sach NODE *pTail; }; typedef struct doulist DLIST;
Trong đó:
- NODE* pHead; là node đầu tiên của danh sách liên kết đôi
- NODE* pTail; là node cuối cùng của danh sách liên kết đôi
- Từ khóa typedef struct doulist DLIST để viết ngắn gọi lại việc khai bảo một danh sách liên kết đôi
3.2 Hàm khởi tạo danh sách liên kết đôi
Danh sách liên kết đơn hay danh sách liên kết đôi ban đầu khi được khai báo sẽ hoàn toàn không có phần tử nào. Vì thế 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(DLIST &ds) dưới đây nhận đối số đầu vào là tham chiếu DLIST &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(DLIST &ds){ //dat dia chi dau danh sach bang NULL ds.pHead = NULL; //dat dia chi cuoi danh sach bang NULL ds.pTail = NULL; }
Lưu ý: Hàm này có thể làm tương tự cho danh sách liên kết đơn.
3.3 Hàm kiểm tra rỗng trong danh sách liên kết đôi
Hàm kiểm tra rỗng thực hiện chức năng kiểm tra trạng thái của danh sách liên kết đôi đó xem danh sách đó có đang rỗng hay không? 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.
int KiemTraRong(DLIST 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 Node trong danh sách liên kết đơn
Giống như danh sách liên kết đơn, để thực hiện được việc thêm một node vào danh sách liên kết đôi ta cần có một hàm tạo node trước. Tuy nhiên điểm khác biệt của một node danh sách liên kết đôi đó chính là việc một node sẽ có 3 thành phần đó là: thành phần data, Next, Previous vì thế để tạo ra một node mới ta cần khai báo đủ 3 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à ban đầu khi khởi tạo node ta sẽ đặt thành phần next, previous của node đó đều 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; //gan con tro prev = NULL p->prev = NULL; //tra ve node p da tao return p; }
4.Chương trình cài đặt danh sách liên kết đôi hoàn chỉnh
Chương trình dưới đây cài đặt đầy đủ các hàm trên để khởi tạo một danh sách liên kết đôi hoàn chỉnh.
#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 de chua dia chi phan tu sau Node *next; //khai bao con tro prev co kieu Node de chua dia chi phan tu truoc Node *prev; }; typedef struct Node NODE; struct doulist{ //thanh phan dau danh sach NODE *pHead; //thanh phan cuoi danh sach NODE *pTail; }; typedef struct doulist DLIST; void KhoiTao(DLIST &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(DLIST 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 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; //gan con tro prev = NULL p->prev = NULL; //tra ve node p da tao return p; } int main(){ //khai bao mot danh sach lien ket doi DLIST ds; //khoi tao danh sach KhoiTao(ds); //kiem danh sach co rong hay khong KiemTraRong(ds); }
Chương trình trên đã thực hiện được bước đầu trong việc cài đặt danh sách liên kết đôi bằng C/C++, tuy nhiên ta vẫn cần thao tác với danh sách liên kết đôi ở trong những bài sau nữa. Vì thế, hay ghi nhớ các hàm: TaoNode(), KhoiTao(), KiemTraRong() và các struct list cũng như struct Node.
Nếu như bạn đã từng học danh sách liên kết đơn, thì có thể dễ dàng nhận thấy rằng danh sách liên kết đôi có các hàm gần như là tương tự danh sách liên kết đơn. Chúng chỉ co sự khác biệt chính là ở thành phần của node và hàm tạo node trong mỗi danh sách.