C++ Data Structure: Doubly Linked List.
Hi, xin chào các bạn.
Trong bài trước chúng ta đã tìm hiểu về linked list cơ bản, và đó được coi như là một singly linked list.
Khi đã hiểu được nguyên lý của single linked list, chúng ta hoàn toàn có thể phát triển và mở rộng hơn.
Bài hôm nay chúng ta cùng tìm hiểu và xây dựng douby linked list.
1. LÝ THUYẾT CƠ BẢN VỀ DOUBLY LINKED LIST.
Là một dạng mở rộng hơn so với singly linked list. Và nó có nhiều ưu điểm hơn.
– Một phần tử có thể được liên kết theo hai chiều, trước và sau.
Nghĩa là từ một phần từ bạn có thể tìm được phần tử kế tiếp nó, và trước nó.
– Việc xóa bỏ node cũng hiệu quả hơn.
– Có thể chèn một node mới trước một node cố định, và có 4 kiểu chèn cơ bản trong doubly linked list.
+ Chèn trước danh sách.
+ Chèn sau danh sách.
+ Chèn trước một node xác định.
+ Chèn sau một node xác định.
Chúng ta hãy cùng xem hình minh họa cho doubly linked list.
2. TRIỂN KHAI DOUBLY LINKED LIST VỚI CODE C++
a. Xây dựng class NodeData theo template tổng quát.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
template <typename T> class NodeData { public: NodeData() : next_(NULL), prev_(NULL) { ; } void set_data(T val) { data_ = val; } T get_data() const { return data_; } void set_next(NodeData<T>* next) { next_ = next; } NodeData<T>* get_next() const { return next_; }; void set_prev(NodeData<T>* prev) { prev_ = prev;} NodeData<T>* get_prev() const { return prev_; } private: T data_; NodeData<T>* next_; NodeData<T>* prev_; }; |
b. Xây dựng class Doubly Linked List với 4 phương thức chèn.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
template<typename T> class LinkedList { public: LinkedList() : p_head_(NULL) {}; ~LinkedList() { // Giải phóng vùng nhớ khi kết thúc chương trình NodeData<Person>* temp = p_head_; while (temp != NULL) { p_head_ = p_head_->get_next(); delete temp; temp = p_head_; } }; void InsetFront(T val) //CHÈN TRƯỚC DANH SÁCH { NodeData<T>* temp = new NodeData<T>(); temp->set_data(val); temp->set_next(p_head_); temp->set_prev(NULL); if (p_head_ != NULL) p_head_->set_prev(temp); p_head_ = temp; } void InsertBack(T val) // CHÈN SAU DANH SÁCH { NodeData<T>* last = p_head_; // Tim ra node cuoi cung. if (last == NULL) { NodeData<T>* temp = new NodeData<T>(); \ temp->set_data(val); p_head_ = temp; last = temp; } else { while (last->get_next() != NULL) { last = last->get_next(); } NodeData<T>* temp = new NodeData<T>(); \ temp->set_data(val); temp->set_next(NULL); // next temp = NULL temp->set_prev(last); // prev cua temp se la last last->set_next(temp); // next cua last la temp } } void InsertAfterNode(NodeData<T>* node, T val) // CHÈN TRƯỚC MỘT NODE ĐÃ CÓ { if (node != NULL) { NodeData<T>* temp = new NodeData<T>(); temp->set_data(val); temp->set_next(node->get_next()); // next cua temp = next cua node hien tai temp->set_prev(node); // prev cua temp = node node->set_next(temp); // next node = tem if (temp->get_next() != NULL) { temp->get_next()->set_prev(temp); // prev cua (next cua node) = temp } } } void InsertBeforeNode(NodeData<T>* node, T val) // CHÈN SAU MỘT NODE ĐÃ CÓ { if (node != NULL) { NodeData<T>* temp = new NodeData<T>(); temp->set_data(val); temp->set_next(node); temp->set_prev(node->get_prev()); node->set_prev(temp); if (temp->get_prev() != NULL) { temp->get_prev()->set_next(temp); } } } void RemoveFront() // Một hàm xóa phần từ đầu danh sách. { if (p_head_ != NULL) { NodeData<T>* temp = p_head_; p_head_ = p_head_->get_next(); delete temp; } } NodeData<T>* head() { return p_head_; }; public: NodeData<T>* p_head_; }; |
c. Sử dụng doubly linked list với kiểu dữ liệu Person.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <conio.h> #include "DoublyLinkedList.h" class Person { public: Person() { ; }; Person(std::string name, unsigned int age, bool sex); ~Person() { ; }; void operator =(Person& p); std::string get_name() const { return name_; } unsigned int get_age() const { return age_; } bool get_sex() const { return sex_; } void ShowInfo() { std::cout << " Name = " << name_.c_str(); std::cout << " Age = " << age_; std::cout << " Sex = " << ((sex_ == 1) ? "Male" : "Female"); } private: std::string name_; unsigned int age_; bool sex_; }; Person::Person(std::string name, unsigned int age, bool sex) { name_ = name; age_ = age; sex_ = sex; } void Person::operator =(Person& p) { this->name_ = p.name_; this->age_ = p.age_; this->sex_ = p.sex_; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
int main() { LinkedList<Person> data_list; Person person1("Pham A", 20, 1); Person person2("Pham B", 20, 0); Person person3("Pham C", 20, 1); Person person4("Pham MID_BE", 20, 0); Person person5("Pham MID_AF", 20, 0); data_list.InsetFront(person1); data_list.InsetFront(person2); data_list.InsertBack(person3); std::cout << " Insert front and back \n\n"; NodeData<Person>* p_head = data_list.head(); if (p_head != NULL) { NodeData<Person>* temp = p_head; while (temp != NULL) { temp->get_data().ShowInfo(); std::cout << "\n\n\n"; temp = temp->get_next(); } } NodeData<Person>* pHead = data_list.head(); if (pHead != NULL) { NodeData<Person>* pMid = pHead->get_next(); if (pMid != NULL) { data_list.InsertBeforeNode(pMid, person4); data_list.InsertAfterNode(pMid, person5); std::cout << " Insert before and after node \n\n"; NodeData<Person>* p_head = data_list.head(); if (p_head != NULL) { NodeData<Person>* temp = p_head; while (temp != NULL) { temp->get_data().ShowInfo(); std::cout << "\n\n\n"; temp = temp->get_next(); } } } } _getch(); return 0; } |
Chúng ta sẽ thấy như sau.
- A sẽ được chèn vào đâu tiên => danh sách là A
- B sẽ được chèn tiếp vào đầu => danh sách là B A
- C sẽ được chèn vào cuối => Danh sách là B A C
- Sau đó tìm phần tử head là B. => next phần từ head là A.
pMid là A.
- Chèn MID_BE và trước của A => danh sách sẽ là B MID_BE A C
- Sau đó chèn MID_AF vào sau của A => danh sách là B MID_BE A MID_AF C.
Kết quả chương trình chạy như sau:
Như vậy doubly linked link có sự linh hoạt hơn trong việc kiểm soát danh sách liên kết.
Chúng ta có thể dễ dàng chèn được các phần tử mới theo 4 cách.