Bài tập danh sách liên kết có lời giải năm 2024

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.

Minh họa 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 phần tử liên kết[link], được gọi đầu tiên[first] và cuối cùng[last].
  • 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[next] và trước[prev].
  • Mỗi liên kết được liên kết với liên kết tiếp theo bằng next link.
  • Mỗi liên kết được liên kết với liên kết trước đó bằng prev link.
  • 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 vào cuối - Thêm một phần tử vào cuối danh sách.
  • Xóa phần tử cuối - Xóa một phần tử ở vị trí cuối danh sách.
  • Chèn vào sau - Thêm một phần tử sau một phần tử của danh sách.
  • Xóa [bởi key] - Xóa một phần tử khỏi danh sách bằng phím.
  • Hiển thị danh sách về phía trước - Hiển thị danh sách đầy đủ theo chiều về phía trước.
  • Hiển thị danh sách về phía sau - Hiển thị danh sách đầy đủ theo chiều về phía sau.

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;

}

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

}

- Hiếu Kiều -

Chủ Đề