Cấu trúc dữ liệu và giải thuật Danh sách liên kết đôi

Danh sách liên kết đôi (Doubly Linked List) là gì ?

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.

Biểu diễn Danh sách liên kết đôi

Như hình minh họa trên, bạn cần ghi nhớ:

Các hoạt động cơ bản trên Danh sách liên kết đôi

Hoạt động chèn trong Danh sách liên kết đôi

Phần dưới đây là giải thuật minh họa cho hoạt động chèn tại vị trí đầu của một Danh sách liên kết đôi.

//Chèn link tại vị trí đầu tiên
void insertFirst(int key, int data) {

   //tạo một link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //Biến nó thành last link
      last = link;
   }else {
      //Cập nhật prev link đầu tiên
      head->prev = link;
   }

   //Trỏ nó tới first link cũ
   link->next = head;
	
   //Trỏ first tới first link mới
   head = link;
}

Để tìm hiểu chi tiết code minh họa của danh sách liên kết đôi trong ngôn ngữ C, mời bạn click chuột vào chương: Chương trình danh sách liên kết đôi trong C.

Hoạt động xóa trong Danh sách liên kết đôi

Phần dưới đây là giải thuật minh họa cho hoạt động xóa phần tử tại vị trí đầu của một Danh sách liên kết đôi.

//xóa phần tử đầu tiên
struct node* deleteFirst() {

   //Lưu tham chiếu tới first link
   struct node *tempLink = head;
	
   //Nếu chỉ có link
   if(head->next == NULL) {
      last = NULL;
   }else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //Trả về link đã bị xóa
   return tempLink;
}

Để tìm hiểu chi tiết code minh họa của danh sách liên kết đôi trong ngôn ngữ C, mời bạn click chuột vào chương: Chương trình danh sách liên kết đôi trong C.

Hoạt động chèn tại vị trí cuối trong Danh sách liên kết đôi

Phần dưới đây là giải thuật minh họa cho hoạt động chèn tại vị trí cuối của một Danh sách liên kết đôi.

//Chèn link vào vị trí cuối cùng
void insertLast(int key, int data) {

   //tạo một link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //biến nó thành last link
      last = link;
   }else {
      //làm cho link trở thành last link mới
      last->next = link;     
      //Đánh dấu last node là prev của new link
      link->prev = last;
   }

   //Trỏ last tới new last node
   last = link;
}

Để tìm hiểu chi tiết code minh họa của danh sách liên kết đôi trong ngôn ngữ C, mời bạn click chuột vào chương: Chương trình danh sách liên kết đôi trong C.