如何在类中实现双向链表。 |21xrx.com

如何在类中实现双向链表。

2023-06-23 13:53:58 深夜i 19 0

双向链表类实现

双向链表是一种常见的数据结构，它与单向链表相比具有更高效的遍历和删除操作。一个双向链表包括一个头节点、一个尾节点和若干个元素节点。每个元素节点包括两个指针，分别指向前一个节点和后一个节点。以下是如何在类中实现双向链表的基本步骤。

1. 定义节点类

首先，需要定义一个节点类来表示双向链表的每个元素节点。该类应该包括数据成员和两个指针成员，其中一个指针指向前一节点，另一个指针指向后一节点。

class Node {
public:
  int data;
  Node* prev;
  Node* next;
};

2. 定义链表类

接下来，需要定义一个链表类，它包含两个指针成员，分别指向链表的头节点和尾节点。此外，还需要实现一些基本操作，如插入、删除和遍历节点。

class DoublyLinkedList {
public:
  Node* head;
  Node* tail;
  DoublyLinkedList()
    head = nullptr;
    tail = nullptr;
  
  void insert(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->prev = nullptr;
    newNode->next = head;
    if (head != nullptr)
      head->prev = newNode;
    
    head = newNode;
    if (tail == nullptr)
      tail = head;
    
  }
  void remove(Node* node) {
    if (node == head)
      head = node->next;
    
    if (node == tail)
      tail = node->prev;
    
    if (node->prev != nullptr)
      node->prev->next = node->next;
    
    if (node->next != nullptr)
      node->next->prev = node->prev;
    
    delete node;
  }
  void traverse() {
    Node* currentNode = head;
    while (currentNode != nullptr)
      // do something with currentNode->data
      currentNode = currentNode->next;
    
  }
};

3. 测试代码

完成双向链表的类定义之后，可以编写一些测试代码来验证其正确性。

DoublyLinkedList list;
list.insert(3);
list.insert(2);
list.insert(1);
list.traverse();    // output: 1 2 3
list.remove(list.head); // remove first node
list.traverse();    // output: 2 3

以上就是如何在类中实现双向链表的基本步骤。通过定义节点类和链表类，实现了双向链表的基本操作，包括插入、删除和遍历节点。

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

下一篇: C++中Map的Count函数

评论区

相似文章