有关链表的知识可以点击我上篇文章这里就不再赘述LinkedList

在这里插入图片描述
在这里插入图片描述

  • 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

双向循环链表的可以点击我这篇文章这里就不再赘述DoubleLoopLinkList

在这里插入图片描述

  1. void addFirst(const T &e) {
  2. 	//新建一个节点让它前驱指向头，后继指向头的后继然后再让头的后继指向新建的节点，
  3.         head->next = new Node<T>(e, head, head->next);
  4.         //把新节点的后继节点的前驱指向新节点
  5.         head->next->next->prev = head->next;
  6.         ++size;
  7. }
  1. void add(const int index, const T &e) {
  2.         assert(index >= 0 && index <= size);
  3.         Node<T> *prevNode = head;
  4.         for (int i = 0; i < index; ++i) {
  5.             prevNode = prevNode->next;
  6.         }
  7.         prevNode->next = new Node<T>(e, prevNode, prevNode->next);
  8.         prevNode->next->next->prev = prevNode->next;
  9.         ++size;
  10.     }
  1. void addLast(const T &e) {
  2. 		//
  3.         tail->prev = new Node<T>(e, tail->prev, tail);
  4.         tail->prev->prev->next = tail->prev;
  5.         ++size;
  6. }
  1.  T removeFirst() {
  2.         return remove(0);//调不调都是O(1)，就这吧。
  3.     }
  1. T remove(int index) {
  2.         assert(index >= 0 && index < size);
  3.         //找到待删除节点的前一节点
  4.         Node<T> *prevNode = head;
  5.         for (int i = 0; i < index; ++i) {
  6.             prevNode = prevNode->next;
  7.         }
  8.         //暂存要删除的节点
  9.         Node<T> *retNode = prevNode->next;
  10.         T temp = retNode->e;
  11.         //前一节点的后继指向待删除节点的后继
  12.         prevNode->next = retNode->next;
  13.         //后一节点的前驱指向待删除节点的前驱
  14.         retNode->next->prev = retNode->prev;
  15.         retNode->next = nullptr;
  16.         retNode->prev = nullptr;
  17.         --size;
  18.         delete retNode;
  19.         retNode = nullptr;
  20.         return temp;
  21.     }
  1. T removeLast() {
  2. 	//先暂存要删除的节点
  3.     Node<T> *retNode = tail->prev;
  4.     T temp = retNode->e;
  5.     //尾指针的前驱指向待删除的前驱
  6.     tail->prev = retNode->prev;
  7.     待删除节点前面一节点的后继指向尾指针
  8.     retNode->prev->next = tail;
  9.     retNode->next = nullptr;
  10.     retNode->prev = nullptr;
  11.     delete retNode;
  12.     retNode = nullptr;
  13.     --size;
  14.     return temp;
  15. }
  1. //
  2. // Created by cheng on 2021/7/5.
  3. //
  5. #ifndef LINKEDLIST_TEST_H
  6. #define LINKEDLIST_TEST_H
  7. #include <assert.h>
  9. template<typename T>
  10. class Node {
  11. public:
  12.     T e;
  13.     Node *prev;
  14.     Node *next;
  16.     Node() : e(0), prev(nullptr), next(nullptr) {
  18.     }
  20.     Node(const T &E) : e(E), prev(nullptr), next(nullptr) {
  22.     }
  24.     Node(const T &E, Node<T> *Prev, Node<T> *Next) : e(E), prev(Prev), next(Next) {
  26.     }
  27. };
  29. template<typename T>
  30. class DoubleLinkedList {
  31. public:
  32.     DoubleLinkedList() : size(0) {
  33.         head = new Node<T>(0, nullptr, head);
  34.         tail = new Node<T>(0, tail, nullptr);
  35.     }
  37.     constexpr int getSize() const {
  38.         return size;
  39.     }
  41.     constexpr bool isEmpty() const {
  42.         return size == 0;
  43.     }
  45.     void add(const int index, const T &e) {
  46.         assert(index >= 0 && index <= size);
  47.         Node<T> *prevNode = head;
  48.         for (int i = 0; i < index; ++i) {
  49.             prevNode = prevNode->next;
  50.         }
  51.         prevNode->next = new Node<T>(e, prevNode, prevNode->next);
  52.         prevNode->next->next->prev = prevNode->next;
  53.         ++size;
  54.     }
  56.     void addFirst(const T &e) {
  57.         head->next = new Node<T>(e, head, head->next);
  58.         head->next->next->prev = head->next;
  59.         ++size;
  60.     }
  62.     void addLast(const T &e) {
  63.         tail->prev = new Node<T>(e, tail->prev, tail);
  64.         tail->prev->prev->next = tail->prev;
  65.         ++size;
  66.     }
  68.     void set(const int index, const T &e) {
  69.         assert(index >= 0 && index < size);
  70.         Node<T> *cur = head->next;
  71.         for (int i = 0; i < index; ++i) {
  72.             cur = cur->next;
  73.         }
  74.         cur->e = e;
  75.     }
  77.     void setFirst(const T &e) {
  78.         head->next->e = e;
  79.     }
  81.     void setLast(const T &e) {
  82.         tail->prev->e = e;
  83.     }
  85.     bool contains(const T &e) const {
  86.         Node<T> *cur = head->next;
  87.         while (cur != nullptr) {
  88.             if (cur->e = e) {
  89.                 return true;
  90.             }
  91.             cur = cur->next;
  92.         }
  93.         return false;
  94.     }
  96.     T get(const int index) const {
  97.         assert(index >= 0 && index < size);
  98.         Node<T> *cur = head->next;
  99.         for (int i = 0; i < index; ++i) {
  100.             cur = cur->next;
  101.         }
  102.         return cur->e;
  103.     }
  105.     T getFirst() const {
  106.         return head->next->e;
  107.     }
  109.     T getLast() const {
  110.         return tail->prev->e;
  111.     }
  113.     T remove(int index) {
  114.         assert(index >= 0 && index < size);
  115.         Node<T> *prevNode = head;
  116.         for (int i = 0; i < index; ++i) {
  117.             prevNode = prevNode->next;
  118.         }
  119.         Node<T> *retNode = prevNode->next;
  120.         prevNode->next = retNode->next;
  121.         retNode->next->prev = retNode->prev;
  122.         retNode->next = nullptr;
  123.         retNode->prev = nullptr;
  124.         --size;
  125.         T temp = retNode->e;
  126.         delete retNode;
  127.         retNode = nullptr;
  128.         return temp;
  129.     }
  131.     T removeFirst() {
  132.         return remove(0);
  133.     }
  135.     T removeLast() {
  136.         Node<T> *retNode = tail->prev;
  137.         T temp = retNode->e;
  138.         tail->prev = retNode->prev;
  139.         retNode->prev->next = tail;
  140.         retNode->next = nullptr;
  141.         retNode->prev = nullptr;
  142.         delete retNode;
  143.         retNode = nullptr;
  144.         --size;
  145.         return temp;
  146.     }
  148.     ~DoubleLinkedList() {
  149.         Node<T> *cur = head->next;
  150.         Node<T> *temp;
  151.         while (cur != nullptr) {
  152.             temp = cur->next;
  153.             delete cur;
  154.             cur = temp;
  155.         }
  156.         head->next = nullptr;
  157.         head->prev = nullptr;
  158.         tail->prev = nullptr;
  159.         tail->next = nullptr;
  160.         delete head;
  161.         head = nullptr;
  162.         delete tail;
  163.         tail = nullptr;
  164.     }
  166.     void print() {
  167.         Node<T> *prevNode = head;
  168.         std::cout << "LinkedList: size = " << size << std::endl;
  169.         std::cout << "[";
  170.         for (int i = 0; i < size; ++i) {
  171.             prevNode = prevNode->next;
  172.             std::cout << prevNode->e;
  173.             if (i < size - 1) {
  174.                 std::cout << ", ";
  175.             }
  176.         }
  177.         std::cout << "]" << std::endl;
  178.     }
  180. private:
  181.     Node<T> *head, *tail;
  182.     int size;
  183. };
  184. #endif //LINKEDLIST_TEST_H
  1. //
  2. // Created by cheng on 2021/7/5.
  3. //
  5. #ifndef LINKEDLIST_DOUBLELINKEDLIST_H
  6. #define LINKEDLIST_DOUBLELINKEDLIST_H
  8. #include <assert.h>
  10. template<typename T>
  11. class Node {
  12. public:
  13.     T e;
  14.     Node *prev;
  15.     Node *next;
  17.     Node() : e(0), prev(nullptr), next(nullptr) {}
  19.     Node(const T &E) : e(E), prev(nullptr), next(nullptr) {}
  21.     Node(const T &E, Node<T> *Prev, Node<T> *Next) : e(E), prev(Prev), next(Next) {}
  22. };
  24. template<typename T>
  25. class DoubleLinkedList {
  26. public:
  27.     DoubleLinkedList() : size(0) {
  28.         dummyHead = new Node<T>(0, nullptr, dummyHead);
  29.     }
  31.     constexpr int getSize() const {
  32.         return size;
  33.     }
  35.     constexpr bool isEmpty() const {
  36.         return size == 0;
  37.     }
  39.     void add(const int index, const T &e) {
  40.         assert(index >= 0 && index <= size);
  41.         Node<T> *prevNode = dummyHead;
  42.         for (int i = 0; i < index; ++i) {
  43.             prevNode = prevNode->next;
  44.         }
  45.         prevNode->next = new Node<T>(e, prevNode, prevNode->next);
  46.         prevNode->next->next->prev = prevNode->next;
  47.         ++size;
  48.     }
  50.     void addFirst(const T &e) {
  51.         add(0, e);
  52.     }
  54.     void addLast(const T &e) {
  55.         add(size, e);
  56.     }
  58.     void set(const int index, const T &e) {
  59.         assert(index >= 0 && index < size);
  60.         Node<T> *cur = dummyHead->next;
  61.         for (int i = 0; i < index; ++i) {
  62.             cur = cur->next;
  63.         }
  64.         cur->e = e;
  65.     }
  67.     void setFirst(const T &e) {
  68.         set(0, e);
  69.     }
  71.     void setLast(const T &e) {
  72.         set(size, e);
  73.     }
  75.     bool contains(const T &e) const {
  76.         Node<T> *cur = dummyHead->next;
  77.         while (cur != nullptr) {
  78.             if (cur->e = e) {
  79.                 return true;
  80.             }
  81.             cur = cur->next;
  82.         }
  83.         return false;
  84.     }
  86.     T get(const int index) const {
  87.         assert(index >= 0 && index < size);
  88.         Node<T> *cur = dummyHead->next;
  89.         for (int i = 0; i < index; ++i) {
  90.             cur = cur->next;
  91.         }
  92.         return cur->e;
  93.     }
  95.     T getFirst() const {
  96.         return get(0);
  97.     }
  99.     T getLast() const {
  100.         return get(size - 1);
  101.     }
  103.     T remove(int index) {
  104.         assert(index >= 0 && index < size);
  105.         Node<T> *prevNode = dummyHead;
  106.         for (int i = 0; i < index; ++i) {
  107.             prevNode = prevNode->next;
  108.         }
  109.         Node<T> *retNode = prevNode->next;
  110.         prevNode->next = retNode->next;
  111.         retNode->next->prev = retNode->prev;
  112.         retNode->next = nullptr;
  113.         retNode->prev = nullptr;
  114.         --size;
  115.         T temp = retNode->e;
  116.         delete retNode;
  117.         retNode = nullptr;
  118.         return temp;
  119.     }
  121.     T removeFirst() {
  122.         return remove(0);
  123.     }
  125.     T removeLast() {
  126.         return remove(size - 1);
  127.     }
  129.     ~DoubleLinkedList() {
  130.         Node<T> *cur = dummyHead->next;
  131.         Node<T> *temp;
  132.         while (cur != nullptr) {
  133.             temp = cur->next;
  134.             delete cur;
  135.             cur = temp;
  136.         }
  137.         dummyHead->next = nullptr;
  138.         dummyHead->prev = nullptr;
  139.         delete dummyHead;
  140.         dummyHead = nullptr;
  141.     }
  143.     void print() {
  144.         Node<T> *prevNode = dummyHead;
  145.         std::cout << "LinkedList: size = " << size << std::endl;
  146.         std::cout << "[";
  147.         for (int i = 0; i < size; ++i) {
  148.             prevNode = prevNode->next;
  149.             std::cout << prevNode->e;
  150.             if (i < size - 1) {
  151.                 std::cout << ", ";
  152.             }
  153.         }
  154.         std::cout << "]" << std::endl;
  155.     }
  157. private:
  158.     Node<T> *dummyHead;
  159.     int size;
  160. };
  163. #endif //LINKEDLIST_DOUBLELINKEDLIST_H

版权声明：本文为chengmf原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/chengmf/p/14977506.html