Danh sách liên kết đôi
Danh sách liên kết đôi (Doubly Linked List) là một biến thể của danh sách liên kết (Linked List), trong đó hoạt động duyệt qua các nút có thể được thực hiện theo hai chiều: về trước và về sau một cách dễ dàng khi so sánh với Danh sách liên kết đơn. Dưới đây là một số khái niệm quan trọng cần ghi nhớ về Danh sách liên kết đôi.
- Link: mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu và được gọi là một phần tử.
- Next: mỗi link của một Danh sách liên kết có thể chứa một link tới next link và được gọi là Next.
- Prev: mỗi link của một Danh sách liên kết có thể chứa một link tới previous link và được gọi là Prev.
- First và Last: một Danh sách liên kết chứa link kết nối tới first link được gọi là First và tới last link được gọi là Last.
Minh họa danh sách liên kết đôi
Theo minh họa ở trên, sau đây là những điểm quan trọng cần được xem xét.
- Danh sách liên kết đôi có chứa một phần tử liên kết(link), được gọi đầu tiên(first) và cuối cùng(last).
- Mỗi liên kết mang (các) trường dữ liệu và hai trường liên kết được gọi là tiếp theo(next) và trước(prev).
- Mỗi liên kết được liên kết với liên kết tiếp theo bằng next link.
- Mỗi liên kết được liên kết với liên kết trước đó bằng prev link.
- Liên kết cuối cùng mang một liên kết là null để đánh dấu phần cuối của danh sách.
Hoạt động cơ bản
Sau đây là các hoạt động cơ bản được hỗ trợ bởi một danh sách.
- Chèn - Thêm một phần tử ở đầu danh sách.
- Xóa - Xóa một phần tử ở đầu danh sách.
- Chèn vào cuối - Thêm một phần tử vào cuối danh sách.
- Xóa phần tử cuối - Xóa một phần tử ở vị trí cuối danh sách.
- Chèn vào sau - Thêm một phần tử sau một phần tử của danh sách.
- Xóa (bởi key) - Xóa một phần tử khỏi danh sách bằng phím.
- Hiển thị danh sách về phía trước - Hiển thị danh sách đầy đủ theo chiều về phía trước.
- Hiển thị danh sách về phía sau - Hiển thị danh sách đầy đủ theo chiều về phía sau.
Thao tác chèn
Đoạn mã sau biểu thị thao tác chèn vào đầu danh sách liên kết đôi.
Thí dụ
//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
Thao tác xóa
Đoạn mã sau biểu thị thao tác xóa ở đầu danh sách liên kết đôi.
Thí dụ
//delete first item
struct node* deleteFirst() {
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
Chèn vào cuối danh sách liên kết đôi
Đoạn mã sau biểu thị thao tác chèn tại vị trí cuối cùng của danh sách liên kết đôi.
Thí dụ
//insert link at the last location
void insertLast(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
- Hiếu Kiều -
Bài viết nổi bật
Bài viết nổi bật