C++语言实现链表 |21xrx.com

C++语言实现链表

2023-07-07 15:38:25 深夜i -- --

C++ 链表实现

链表是一种动态数据结构，在C++语言中可以通过指针来实现。在这篇文章中，我们将介绍如何使用C++语言来实现链表。

链表是由一个个节点组成，每个节点都包含一个数据元素和指向下一个节点的指针。链表的头指针指向第一个节点，每个节点的指针指向下一个节点，直到最后一个节点的指针指向NULL。

在C++的链表实现中，我们需要定义一个节点类，其中包含数据和指向下一个节点的指针。我们可以这样实现：


class Node {
public:
  int data;
  Node *next;
  Node(int d) : data(d), next(nullptr) {}
};

接下来，我们需要定义一个链表类，该类包含一个指向第一个节点的头指针和一些操作链表的方法。我们可以这样定义：


class LinkedList {
public:
  Node *head;
  LinkedList() : head(nullptr) {}
  
  // 插入操作
  void insert(int data) {
    Node *newNode = new Node(data);
    if (head == nullptr)
      head = newNode;
     else {
      Node *currNode = head;
      while (currNode->next != nullptr)
        currNode = currNode->next;
      
      currNode->next = newNode;
    }
  }
  
  // 删除操作
  void remove(int data) {
    Node *currNode = head;
    Node *prevNode = nullptr;
    while (currNode != nullptr && currNode->data != data)
      prevNode = currNode;
      currNode = currNode->next;
    
    if (currNode != nullptr) {
      if (prevNode == nullptr)
        head = currNode->next;
       else
        prevNode->next = currNode->next;
      
      delete currNode;
    }
  }
  
  // 查找操作
  bool search(int data) {
    Node *currNode = head;
    while (currNode != nullptr) {
      if (currNode->data == data)
        return true;
      
      currNode = currNode->next;
    }
    return false;
  }
  
  // 显示操作
  void display() {
    Node *currNode = head;
    while (currNode != nullptr)
      cout << currNode->data << " ";
      currNode = currNode->next;
    
    cout << endl;
  }
};

在上面的代码中，我们定义了插入、删除、查找和显示操作，这些基本操作可以满足链表的常见需求。需要注意的是，在插入和删除操作中，我们需要遍历链表找到要操作的节点，这需要花费O(n)的时间复杂度。因此，在使用链表时，我们应该根据实际情况选择数据结构。

总的来说，对于初学者来说，实现链表是一项不错的练手项目，可以帮助我们更深刻地理解指针和动态数据结构。在实际开发中，链表也是常用的数据结构之一，应该熟练掌握。

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

下一篇: C++运算符的使用方法详解

评论区

()

相似文章