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.

• 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.

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ớ:

• Danh sách liên kết đôi chứa một phần tử link và được gọi là First và Last.
• Mỗi link mang một trường dữ liệu và một trường link được gọi là Next.
• Mỗi link được liên kết với phần tử kế tiếp bởi sử dụng Next Link.
• Mỗi link được liên kết với phần tử phía trước bởi sử dụng Prev Link.
• Last Link mang một link trỏ tới NULL để đánh dầu phần cuối của Danh sách liên kết.

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

• Hoạt động chèn: thêm một phần tử vào vị trí đầu của Danh sách liên kết.
• Hoạt động xóa: xóa một phần tử tại vị trí đầu của Danh sách liên kết.
• Hoạt động chèn vào cuối: thêm một phần tử vào vị trí cuối của Danh sách liên kết.
• Hoạt động xóa phần tử cuối: xóa một phần tử tại vị trí cuối của Danh sách liên kết.
• Hoạt động chèn vào sau: thêm một phần tử vào sau một phần tử của Danh sách liên kết.
• Hoạt động xóa (bởi key): xóa một phần tử từ Danh sách liên kết bởi sử dụng khóa đã cung cấp.
• Hiển thị danh sách về phía trước: hiển thị toàn bộ Danh sách liên kết theo chiều về phía trước.
• Hiển thị danh sách về phía sau: hiển thị toàn bộ Danh sách liên kết theo chiều về phía sau.

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

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

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