C++双向循环链表 |21xrx.com

C++双向循环链表

2023-06-22 03:04:49 深夜i -- --

C++ 双向循环链表数据结构节点操作函数

C++双向循环链表是一种常见的数据结构，它是一种链表，每个节点包含指向前后节点的指针，最后一个节点指向第一个节点，第一个节点指向最后一个节点。

通过这种数据结构，我们可以实现一些常见的操作，比如添加节点、删除节点、遍历节点等。同时，由于双向循环链表是一种线性结构，它还可以用作栈或队列的底层实现。

下面是一份简单的C++代码实现：


#include <iostream>
using namespace std;
struct Node {
  int data;
  Node* prev;
  Node* next;
};
class DoublyLinkedList {
private:
  Node* head;
  int size;
public:
  DoublyLinkedList()
    head = NULL;
    size = 0;
  
  void addFirst(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    if (head == NULL)
      head = newNode;
      head->prev = head->next = head;
    
    else {
      Node* last = head->prev;
      newNode->next = head;
      head->prev = newNode;
      newNode->prev = last;
      last->next = newNode;
      head = newNode;
    }
    size++;
  }
  void addLast(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    if (head == NULL)
      head = newNode;
      head->prev = head->next = head;
    
    else {
      Node* last = head->prev;
      newNode->prev = last;
      last->next = newNode;
      newNode->next = head;
      head->prev = newNode;
    }
    size++;
  }
  void removeFirst() {
    if (head == NULL)
      cout << "The list is empty!";
    
    else {
      Node* oldHead = head;
      Node* newHead = head->next;
      Node* last = head->prev;
      newHead->prev = last;
      last->next = newHead;
      head = newHead;
      delete oldHead;
      size--;
    }
  }
  void removeLast() {
    if (head == NULL)
      cout << "The list is empty!";
    
    else {
      Node* last = head->prev;
      Node* newLast = last->prev;
      newLast->next = head;
      head->prev = newLast;
      delete last;
      size--;
    }
  }
  void clear() {
    while (head != NULL) {
      removeFirst();
    }
  }
  void display() {
    if (head == NULL)
      cout << "The list is empty!";
    
    else {
      Node* current = head;
      do
        cout << current->data << " ";
        current = current->next;
       while (current != head);
    }
    cout << endl;
  }
  int getSize()
    return size;
  
  ~DoublyLinkedList() {
    clear();
  }
};
int main() {
  DoublyLinkedList list;
  list.addFirst(1);
  list.addFirst(2);
  list.addLast(0);
  list.addLast(3);
  list.display(); // Output: 2 1 0 3
  list.removeFirst();
  list.removeLast();
  list.display(); // Output: 1 0
  cout << "Size: " << list.getSize() << endl; // Output: Size: 2
  list.clear();
  list.display(); // Output: The list is empty!
  return 0;
}

上面的代码演示了添加第一个节点、添加末尾节点、移除第一个节点、移除末尾节点、清空链表等操作。在使用双向循环链表时，不同的操作需要特别注意指向前后节点的指针的处理，以保证链表结构的正确性。

总之，C++双向循环链表是一种常见的数据结构，可以用于实现许多场合的数据存储与操作，同时也是程序设计中不可或缺的基础知识。

上一篇: idea打包java可执行jar包

下一篇: 如何打开Dev C++程序并切换用户？

评论区

()

相似文章