Danh sách liên kết kép (Double - lists)

Các khai báo cần thiết

typedef ... ElementType;

//kiểu nội dung của các phần tử trong danh sách

typedef struct Node{

ElementType Element; //lưu trữ nội dung phần tử

//Hai con trỏ trỏ tới phần tử trước và sau

Node* Prev;

Node* Next;

};

typedef Node* Position;

typedef Position DoubleList;

Để quản lí một danh sách liên kết kép ta có thể dùng một con trỏ trỏ đến một ô bất kỳ trong cấu trúc. Hoàn toàn tương tự như trong danh sách liên kết đơn đã trình bày trong phần trước, con trỏ để quản lí danh sách liên kết kép có thể là một con trỏ có kiểu giống như kiểu phần tử trong danh sách và nó có thể được cấp phát ô nhớ (tương tự như Header trong danh sách liên kết đơn) hoặc không được cấp phát ô nhớ. Ta cũng có thể xem danh sách liên kết kép như là danh sách liên kết đơn, với một bổ sung duy nhất là có con trỏ previous để nối kết các ô theo chiều ngược lại. Theo quan điểm này thì chúng ta có thể cài đặt các phép toán thêm (insert), xoá (delete) một phần tử hoàn toàn tương tự như trong danh sách liên kết đơn và con trỏ Header cũng cần thiết như trong danh sách liên kết đơn, vì nó chính là vị trí của phần tử đầu tiên trong danh sách.

Tuy nhiên, nếu tận dụng khả năng duyệt theo cả hai chiều thì ta không cần phải cấp phát bộ nhớ cho Header và vị trí (position) của một phần tử trong danh sách có thể định nghĩa như sau: Vị trí của phần tử a_i là con trỏ trỏ tới ô chứa a_i, tức là địa chỉ ô nhớ chứa a_i. Nói nôm na, vị trí của a_i là ô chứa a_i. Theo định nghĩa vị trí như vậy các phép toán trên danh sách liên kết kép sẽ được cài đặt hơi khác với danh sách liên đơn. Trong cách cài đặt này, chúng ta không sử dụng ô đầu mục như danh sách liên kết đơn mà sẽ quản lý danh sách một các trực tiếp (header chỉ ngay đến ô đầu tiên trong danh sách).

Tạo danh sách liên kết kép rỗng

Giả sử DL là con trỏ quản lí danh sách liên kết kép thì khi khởi tạo danh sách rỗng ta cho con trỏ này trỏ NULL (không cấp phát ô nhớ cho DL), tức là gán DL=NULL.

void MakeNull_List (DoubleList *DL){

(*DL)= NULL;

}

Kiểm tra danh sách liên kết kép rỗng

Rõ ràng, danh sách liên kết kép rỗng khi và chỉ khi chỉ điểm đầu danh sách không trỏ tới một ô xác định nào cả. Do đó ta sẽ kiểm tra DL = NULL.

int Empty (DoubleList DL){

return (DL==NULL);

}

Xóa một phần tử ra khỏi danh sách liên kết kép

Để xoá một phần tử tại vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta phải chú ý đến các trường hợp sau:

- Danh sách rỗng, tức là DL=NULL: chương trình con dừng.

- Trường hợp danh sách khác rỗng, tức là DL!=NULL, ta phải phân biệt hai trường hợp

Ô bị xoá không phải là ô được trỏ bởi DL, ta chỉ cần cập nhật lại các con trỏ để nối kết ô trước p với ô sau p, các thao tác cần thiết là (xem hình II.16):

Nếu (p->previous!=NULL) thì p->previous->next=p->next;

Nếu (p->next!=NULL) thì p->next->previous=p->previous;

Xoá ô đang được trỏ bởi DL, tức là p=DL: ngoài việc cập nhật lại các con trỏ để nối kết các ô trước và sau p ta còn phải cập nhật lại DL, ta có thể cho DL trỏ đến phần tử trước nó (DL = p->Previous) hoặc đến phần tử sau nó (DL = p->Next) tuỳ theo phần tử nào có mặt trong danh sách. Đặc biệt, nếu danh sách chỉ có một phần tử tức là p->Next=NULL và p->Previous=NULL thì DL=NULL.

Hình II.16 Xóa phần tử tại vị trí p

void Delete_List (Position p, DoubleList *DL){

if (*DL == NULL) printf(”Danh sach rong”);

else{

if (p==*DL) (*DL)=(*DL)->Next;

//Xóa phần tử đầu tiên của danh sách nên phải thay đổi DL

else p->Previous->Next=p->Next;

if (p->Next!=NULL)

p->Next->Previous=p->Previous;

free(p);

}

}

Thêm phần tử vào danh sách liên kết kép

Để thêm một phần tử x vào vị trí p trong danh sách liên kết kép được trỏ bởi DL, ta cũng cần phân biệt mấy trường hợp sau:

Danh sách rỗng, tức là DL = NULL: trong trường hợp này ta không quan tâm đến giá trị của p. Để thêm một phần tử, ta chỉ cần cấp phát ô nhớ cho nó, gán giá trị x vào trường Element của ô nhớ này và cho hai con trỏ previous, next trỏ tới NULL còn DL trỏ vào ô nhớ này, các thao tác trên có thể viết như sau:

DL=(Node*)malloc(sizeof(Node));

DL->Element = x;

DL->Previous=NULL;

DL->Next =NULL;

Nếu DL!=NULL, sau khi thêm phần tử x vào vị trí p ta có kết quả như hình II.18

Hình II.17: Danh sách trước khi thêm phần tử x Hình II.18: Danh sách sau khi thêm phần tử x vào tại vị trí p

(phần tử tại vị trí p cũ trở thành phần tử "sau" của x)

Lưu ý: các kí hiệu p, p->Next, p->Previous trong hình II.18 để chỉ các ô trước khi thêm phần tử x, tức là nó chỉ các ô trong hình II.17.

Trong trường hợp p=DL, ta có thể cập nhật lại DL để DL trỏ tới ô mới thêm vào hoặc để nó trỏ đến ô tại vị trí p cũ như nó đang trỏ cũng chỉ là sự lựa chọn trong chi tiết cài đặt.

void Insert_List (ElementType X,Position p, DoubleList *DL){

if (*DL == NULL){

(*DL)=(Node*)malloc(sizeof(Node));

(*DL)->Element = X;

(*DL)->Previous =NULL;

(*DL)->Next =NULL;

}

else{

Position temp;

temp=(Node*)malloc(sizeof(Node));

temp->Element=X;

temp->Next=p;

temp->Previous=p->Previous;

if (p->Previous!=NULL)

p->Previous->Next=temp;

p->Previous=temp;

}

}