Cộng đồng chia sẻ tri thức Doc24.vn

Danh sách liên kết đôi

Gửi bởi: Võ Thị Hường vào ngày 2020-02-13 03:23:34

Mục lục
* * * * *
Danh sách liên kết đôi
Danh sách liên kết đôi

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.

  1. 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ử.
  2. 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.
  3. 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.
  4. 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.

  1. 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.
  2. 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.
  3. 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.
  4. 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 đó.
  5. 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.

  1. Chèn - Thêm một phần tử ở đầu danh sách.
  2. Xóa - Xóa một phần tử ở đầu danh sách.
  3. Chèn lần cuối - Thêm một phần tử vào cuối danh sách.
  4. Xóa lần cuối - Xóa một phần tử khỏi cuối danh sách.
  5. Chèn sau - Thêm một phần tử sau một mục của danh sách.
  6. Xóa - Xóa một phần tử khỏi danh sách bằng phím.
  7. Hiển thị chuyển tiếp - Hiển thị danh sách đầy đủ theo cách chuyển tiếp.
  8. 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;
}
Lượt xem: 149

Các bài học liên quan