Tìm hiểu danh sách liên kết đôi với minh họa thuật toán bằng lập trình c++ Trong bài viết này Stanford sẽ giúp các bạn học lập trình hiểu rõ hơn về danh sách liên kết đôi trong cấu trúc giải thuật, ứng dụng thực tế của nó cũng như minh họa thuật toán bằng lập trình c++. Danh sách liên kết đôi (doubly linked list) Danh sách liên kết đôi (doubly linked list) là một cấu trúc dữ liệu tương tự như danh sách liên kết đơn. Nhưng mỗi nút trong danh sách liên kết đôi có thêm một con trỏ trỏ đến nút trước đó, ngoài con trỏ trỏ đến nút tiếp theo. Điều này cho phép duyệt danh sách theo cả hai chiều, từ đầu đến cuối và ngược lại. Các thành phần chính của danh sách liên kết đôi: Node: Mỗi nút chứa ba phần: - Dữ liệu: Giá trị của nút. - Con trỏ next: Trỏ đến nút tiếp theo trong danh sách. - Con trỏ prev: Trỏ đến nút trước đó trong danh sách. Head: Con trỏ đầu tiên của danh sách, trỏ đến nút đầu tiên. Tail: Con trỏ cuối cùng của danh sách, trỏ đến nút cuối cùng. Ứng dụng của danh sách đôi trong thực tế Danh sách liên kết đôi có nhiều ứng dụng thực tế trong lập trình và khoa học máy tính. Dưới đây là một số ví dụ phổ biến: Trình duyệt web: Danh sách liên kết đôi có thể được sử dụng để quản lý lịch sử duyệt web. Người dùng có thể dễ dàng di chuyển qua lại giữa các trang đã truy cập bằng cách sử dụng các con trỏ prev và next. Trình phát nhạc: Trong các trình phát nhạc, danh sách liên kết đôi có thể được sử dụng để quản lý danh sách phát (playlist). Người dùng có thể chuyển bài hát trước hoặc sau một cách dễ dàng. Hệ thống quản lý bộ nhớ: Trong các hệ điều hành, danh sách liên kết đôi có thể được sử dụng để quản lý các khối bộ nhớ tự do (free memory blocks) trong bộ nhớ động, giúp dễ dàng phân bổ và giải phóng bộ nhớ. Cấu trúc dữ liệu phức tạp: Danh sách liên kết đôi là nền tảng để triển khai các cấu trúc dữ liệu phức tạp hơn như danh sách liên kết vòng (circular linked list). Ứng dụng trong đồ họa máy tính: Trong đồ họa máy tính, danh sách liên kết đôi có thể được sử dụng để quản lý các đối tượng đồ họa, chẳng hạn như các điểm, đường thẳng, hoặc hình dạng, cho phép duyệt và chỉnh sửa các đối tượng này một cách linh hoạt. Hệ thống quản lý tài liệu: Trong các hệ thống quản lý tài liệu, danh sách liên kết đôi có thể được sử dụng để theo dõi các phiên bản của tài liệu hoặc các thay đổi theo thời gian, cho phép người dùng dễ dàng quay lại các phiên bản trước đó. Ứng dụng trong mạng: Trong các giao thức mạng, danh sách liên kết đôi có thể được sử dụng để quản lý các gói tin (packets) trong hàng đợi truyền tải, cho phép dễ dàng thêm hoặc xóa các gói tin từ cả hai đầu của hàng đợi. Cài đặt danh sách liên kết đôi bằng C++: Dưới đây là một ví dụ cơ bản về cách cài đặt danh sách liên kết đôi bằng lập trình C++: #include <iostream> using namespace std; // Định nghĩa cấu trúc của một nút struct Node { int data; Node* next; Node* prev; }; // Hàm để chèn một nút mới vào đầu danh sách void insertAtHead(Node*& head, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = head; newNode->prev = nullptr; if (head != nullptr) { head->prev = newNode; } head = newNode; } // Hàm để chèn một nút mới vào cuối danh sách void insertAtTail(Node*& head, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = nullptr; if (head == nullptr) { newNode->prev = nullptr; head = newNode; return; } Node* temp = head; while (temp->next != nullptr) { temp = temp->next; } temp->next = newNode; newNode->prev = temp; } //Hàm để xóa một nút với giá trị cụ thể void deleteNode(Node*& head, int key) { Node* temp = head; while (temp != nullptr && temp->data != key) { temp = temp->next; } if (temp == nullptr) return; // Không tìm thấy giá trị cần xóa if (temp->prev != nullptr) { temp->prev->next = temp->next; } else { head = temp->next; } if (temp->next != nullptr) { temp->next->prev = temp->prev; } delete temp; } //Hàm để in danh sách từ đầu đến cuối void printList(Node* head) { Node* temp = head; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; } cout << endl; } //Hàm để in danh sách từ cuối lên đầu void printListReverse(Node* head) { Node* temp = head; if (temp == nullptr) return; if(temp->next != nullptr) { temp = temp->next; } while (temp != nullptr) { cout << temp->data << " "; temp = temp->prev; } cout << endl; } int main() { Node* head = nullptr; // Khởi tạo danh sách rỗng //Chèn các phần tử vào danh sách insertAtHead(head, 10); insertAtHead(head, 20); insertAtTail(head, 30); //In danh sách từ đầu đến cuối cout << "Danh sach tu dau den cuoi:"<<endl; printList(head); //In danh sách từ cuối lên đầu cout << "Danh sach tu cuoi len dau:"<<endl; printListReverse(head); //Xóa nút với giá trị 20 deleteNode(head, 20); //In danh sách sau khi xóa cout << "Danh sach sau khi xoa:"<<endl; printList(head); return 0; } Giải thích: Node: Định nghĩa cấu trúc của một nút với ba thành phần: data, next, và prev. insertAtHead: Hàm để chèn một nút mới vào đầu danh sách. insertAtTail: Hàm để chèn một nút mới vào cuối danh sách. deleteNode: Hàm để xóa một nút với giá trị cụ thể. printList: Hàm để in các phần tử trong danh sách từ đầu đến cuối. printListReverse: Hàm để in các phần tử trong danh sách từ cuối lên đầu. main: Hàm chính để khởi tạo danh sách, chèn các phần tử, in danh sách trước và sau khi xóa một nút. Danh sách liên kết đôi là một cấu trúc dữ liệu linh hoạt và mạnh mẽ, giúp giải quyết nhiều vấn đề trong lập trình và khoa học máy tính. Để hiểu rõ hơn về thuật toán này bạn có thể thực hiện lập trình cài đặt thuật toán danh sách liên kết đôi như hướng dẫn trong bài viết. Bạn có thể tìm hiểu thêm về các thuật toán sắp xếp trong lập trình ở đây. Chúc các bạn thành công ! Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé. ==========🎬 🎬 🎬========== ☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ Hotline: 0963 723 236 - 0866 586 366 Website: https://stanford.com.vn Facebook: https://www.facebook.com/Stanford.com.vn Youtube: http://bit.ly/2TkKT7I Tags: danh sách liên kết đôi, doubly linked list