Danh sách liên kết đôi là một biến thể của danh sách được liên kết trong đó có thể điều hướng theo cả hai cách, dễ dàng tiến và lùi so với Danh sách liên kết đơn. Sau đây là các điều khoản quan trọng để hiểu khái niệm danh sách liên kết đôi.
- Liên kết - Mỗi liên kết của danh sách được liên kết có thể lưu trữ dữ liệu được gọi là một phần tử.
- Tiếp theo - Mỗi liên kết của danh sách được liên kết chứa một liên kết đến liên kết tiếp theo được gọi là Tiếp theo.
- Trước đó - Mỗi liên kết của danh sách được liên kết chứa một liên kết đến liên kết trước đó được gọi là Prev.
- LinkedList - Danh sách được liên kết chứa liên kết kết nối đến liên kết đầu tiên được gọi là Đầu tiên và đến liên kết cuối cùng được gọi là Cuối cùng.
Đại diện 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 yếu tố liên kết được gọi đầu tiên và cuối cùng.
- 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 và trước.
- Mỗi liên kết được liên kết với liên kết tiếp theo bằng liên kết tiếp theo.
- Mỗi liên kết được liên kết với liên kết trước đó bằng liên kết trước đó.
- 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 lần cuối - Thêm một phần tử vào cuối danh sách.
- Xóa lần cuối - Xóa một phần tử khỏi cuối danh sách.
- Chèn sau - Thêm một phần tử sau một mục của danh sách.
- Xóa - Xóa một phần tử khỏi danh sách bằng phím.
- Hiển thị chuyển tiếp - Hiển thị danh sách đầy đủ theo cách chuyển tiếp.
- Hiển thị lùi - Hiển thị danh sách đầy đủ theo cách lùi.
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 hoạt động
Đ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 được 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;
}Được cập nhật: 12 tháng 4 lúc 1:41:15 | Lượt xem: 456
