提示信息

自定义高效链表容器的STL_list模拟

韦昊 已关注

实现自定义高效链表容器类似于标准模板库(STL)中的std::list,我们需要定义一个双向链表的数据结构,并实现基本的操作方法。以下是一个简单的实现示例:

  1. #include <iostream>
  2. // 定义节点结构
  3. template<typename T>
  4. struct Node {
  5. T data;
  6. Node* prev;
  7. Node* next;
  8. Node(const T& data) : data(data), prev(nullptr), next(nullptr) {}
  9. };
  10. // 自定义链表类
  11. template<typename T>
  12. class MyList {
  13. public:
  14. MyList() : head(nullptr), tail(nullptr), size(0) {}
  15. ~MyList();
  16. void push_back(const T& value);
  17. void pop_back();
  18. void push_front(const T& value);
  19. void pop_front();
  20. std::size_t getSize() const { return size; }
  21. bool empty() const { return size == 0; }
  22. void printList() const;
  23. private:
  24. Node<T>* head;
  25. Node<T>* tail;
  26. std::size_t size;
  27. void clear();
  28. };
  29. // 析构函数,清空链表
  30. template<typename T>
  31. MyList<T>::~MyList() {
  32. clear();
  33. }
  34. // 添加元素到链表尾部
  35. template<typename T>
  36. void MyList<T>::push_back(const T& value) {
  37. Node<T>* newNode = new Node<T>(value);
  38. if (empty()) {
  39. head = tail = newNode;
  40. } else {
  41. tail->next = newNode;
  42. newNode->prev = tail;
  43. tail = newNode;
  44. }
  45. ++size;
  46. }
  47. // 移除链表尾部的元素
  48. template<typename T>
  49. void MyList<T>::pop_back() {
  50. if (empty()) return;
  51. Node<T>* toDelete = tail;
  52. if (tail == head) {
  53. head = tail = nullptr;
  54. } else {
  55. tail = tail->prev;
  56. tail->next = nullptr;
  57. }
  58. delete toDelete;
  59. --size;
  60. }
  61. // 添加元素到链表头部
  62. template<typename T>
  63. void MyList<T>::push_front(const T& value) {
  64. Node<T>* newNode = new Node<T>(value);
  65. if (empty()) {
  66. head = tail = newNode;
  67. } else {
  68. head->prev = newNode;
  69. newNode->next = head;
  70. head = newNode;
  71. }
  72. ++size;
  73. }
  74. // 移除链表头部的元素
  75. template<typename T>
  76. void MyList<T>::pop_front() {
  77. if (empty()) return;
  78. Node<T>* toDelete = head;
  79. if (head == tail) {
  80. head = tail = nullptr;
  81. } else {
  82. head = head->next;
  83. head->prev = nullptr;
  84. }
  85. delete toDelete;
  86. --size;
  87. }
  88. // 输出链表中的元素
  89. template<typename T>
  90. void MyList<T>::printList() const {
  91. Node<T>* current = head;
  92. while (current) {
  93. std::cout << current->data << " ";
  94. current = current->next;
  95. }
  96. std::cout << std::endl;
  97. }
  98. // 清空链表
  99. template<typename T>
  100. void MyList<T>::clear() {
  101. while (!empty()) {
  102. pop_front();
  103. }
  104. }
  105. // 示例用法
  106. int main() {
  107. MyList<int> list;
  108. list.push_back(1);
  109. list.push_back(2);
  110. list.push_back(3);
  111. list.printList(); // 输出: 1 2 3
  112. list.pop_front();
  113. list.printList(); // 输出: 2 3
  114. list.push_front(0);
  115. list.printList(); // 输出: 0 2 3
  116. list.pop_back();
  117. list.printList(); // 输出: 0 2
  118. return 0;
  119. }

这个示例自定义了一个模板类MyList以实现一个简单的双向链表。它支持基本的push_backpop_backpush_frontpop_front等操作。链表操作实行动态内存管理,并具有清理单独节点的方法。这种自定义类模拟了一部分std::list的行为,适合了解链表的工作原理。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
韦昊 关注 已关注

最近一次登录:2024-11-20 13:34:05   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图