C++动态链表搭建 |21xrx.com

C++动态链表搭建

2023-07-05 12:17:03 深夜i -- --

C++ 动态链表搭建

动态链表是一种非常重要的数据结构，在C++中使用它可以实现动态地插入、删除、查找等操作。下面我们来了解一下如何搭建一个C++动态链表。

首先，我们需要定义链表节点的结构体。每个节点应该包含两个变量：data存放数据，next指向下一个节点。


struct ListNode{
  int data;
  ListNode* next;
};

接着，我们需要创建一个链表的类。链表类应该至少包含三个变量：head指向链表的头节点，tail指向链表的尾节点，count表示链表中节点的数量。同时，我们需要在链表类中定义一些方法，来实现链表的一些基本操作。


class LinkedList{
private:
  ListNode* head;
  ListNode* tail;
  int count;
public:
  LinkedList();      // 构造函数，初始化链表
  ~LinkedList();     // 析构函数，删除链表
  void add(int data);   // 在链表最后添加一个数据节点
  void remove(int data); // 删除链表中第一个值为data的数据节点
  void display();     // 打印输出链表中所有数据节点
};

在链表类中定义了三个方法，分别用于添加、删除、打印链表节点数据。接下来，我们可以逐一实现这些方法。

首先是添加方法，我们需要先判断链表是否为空，如果为空，则将新节点作为头节点；否则，将新节点连接到链表尾部。在添加节点时，需要注意更新tail和count变量。


void LinkedList::add(int data){
  ListNode* newNode = new ListNode;
  newNode->data = data;
  newNode->next = nullptr;
  if (head == nullptr)
    head = newNode;
    tail = newNode;
  
  else
    tail->next = newNode;
    tail = newNode;
  
  count++;
}

接下来是删除节点方法。与添加节点方法类似，删除方法也需要先判断链表是否为空，如果为空则直接返回。如果链表中只有一个节点，则删除该节点并将head和tail指向nullptr。否则，需要遍历链表查找要删除的节点，并更新其前后节点的指针。在删除节点时，同样需要注意更新count变量。


void LinkedList::remove(int data){
  if (head == nullptr)
    return;
  
  ListNode* current = head;
  ListNode* previous = nullptr;
  while (current != nullptr){
    if (current->data == data){
      if (previous == nullptr){
        head = current->next;
        if(head == nullptr)
          tail = nullptr;
        
      } else {
        previous->next = current->next;
        if (current->next == nullptr)
          tail = previous;
        
      };
      delete current;
      count--;
      return;
    }
    previous = current;
    current = current->next;
  }
}

最后是打印链表的方法。需要遍历所有节点并输出节点数据，直到节点为nullptr。


void LinkedList::display(){
  ListNode* current = head;
  while (current != nullptr)
    cout << current->data << " ";
    current = current->next;
  
  cout << endl;
}

至此，我们已经实现了一个简单的C++动态链表。使用它，我们可以实现对链表的基本操作，如添加、删除以及输出节点数据。如果需要，在此基础上可以进行扩展，新增一些方法以实现更多功能。

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

下一篇: C++游戏开发路线图

评论区

()

相似文章