Cấu trúc dữ liệu - Danh sách được liên kết kép

Danh sách được 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 chuyển tiếp và lùi lại so với Danh sách được liên kết đơn. Sau đây là các thuật ngữ quan trọng để hiểu khái niệm về danh sách liên kết kép.

Link - Mỗi liên kết của danh sách liên kết có thể lưu trữ một dữ liệu gọi là phần tử.
Next - Mỗi liên kết của một danh sách liên kết chứa một liên kết đến liên kết tiếp theo được gọi là Next.
Prev - Mỗi liên kết của một danh sách 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 - Một 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.

Trình bày danh sách được liên kết gấp đô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 được liên kết đôi chứa một phần tử liên kết được gọi là đầ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 của nó bằng cách sử dụng liên kết tiếp theo của nó.
Mỗi liên kết được liên kết với liên kết trước của nó bằng cách sử dụng liên kết trước của nó.
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.

Insertion - Thêm một phần tử vào đầu danh sách.
Deletion - Xóa một phần tử ở đầu danh sách.
Insert Last - Thêm một phần tử vào cuối danh sách.
Delete Last - Xóa một phần tử khỏi cuối danh sách.
Insert After - Thêm một phần tử sau một mục của danh sách.
Delete - Xóa một phần tử khỏi danh sách bằng phím.
Display forward - Hiển thị danh sách đầy đủ theo cách chuyển tiếp.
Display backward - Hiển thị danh sách đầy đủ theo cách lùi.

Thao tác chèn

Đoạn mã sau minh họa thao tác chèn vào đầu danh sách được liên kết kép.

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

Mã sau minh họa thao tác xóa ở đầu danh sách được liên kết kép.

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 một hoạt động

Đoạn mã sau minh họa thao tác chèn ở vị trí cuối cùng của danh sách được liên kết kép.

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;
}

Để xem cách triển khai bằng ngôn ngữ lập trình C, vui lòng nhấp vào đây .