C++数据结构之单链表简介 |21xrx.com

C++数据结构之单链表简介

2023-06-29 15:49:24 深夜i 11 0

C++ 数据结构单链表简介链表实现

单链表是一种常见的数据结构，它是由若干个节点构成的，每个节点都包含一个数据元素和指向下一个节点的指针。单链表的特点在于它只能从头节点开始遍历，因此访问节点的时间复杂度为O(n)，其中n为链表的长度。但是，插入和删除节点的时间复杂度仅仅为O(1)，所以单链表的优点在于插入和删除操作非常高效。

在C++中，实现单链表需要定义一个节点结构体，结构体包含了节点的数据元素和指向下一个节点的指针。代码如下：

struct Node {
  int val; //数据元素
  Node* next; //指向下一个节点的指针
};

接下来，我们需要定义一个单链表类，类中包括单链表的头节点和一些基本操作，如插入和删除等。代码如下：

class LinkedList {
private:
  Node* head; //头节点
public:
  LinkedList() //构造函数
    head = NULL; //初始化头节点为空
  
  void insert(int val) { //插入操作
    Node* node = new Node; //创建一个新的节点
    node->val = val; //设置节点的数据元素
    node->next = head; //将节点的指针指向头节点
    head = node; //将头节点指向新节点
  }
  void remove(int val) { //删除操作
    if (head == NULL) return; //链表为空，不需要删除
    if (head->val == val) { //头节点需要删除
      Node* node = head;
      head = node->next; //将头节点指向下一个节点
      delete node; //释放节点内存
      return;
    }
    Node* prev = head;
    while (prev->next != NULL && prev->next->val != val) //找到待删除节点的前一个节点
      prev = prev->next;
    
    if (prev->next == NULL) return; //没有找到待删除节点
    Node* node = prev->next; //找到待删除节点
    prev->next = node->next; //将前一个节点的指针指向下一个节点
    delete node; //释放节点内存
  }
  void print() { //遍历操作
    Node* node = head;
    while (node != NULL) //当节点不为空时输出节点的数据元素
      cout << node->val << " ";
      node = node->next; //继续遍历下一个节点
    
    cout << endl;
  }
};

使用以上的LinkedList类，我们可以方便地进行单链表的插入、删除和遍历等操作。例如，我们可以将以下代码添加到main函数中：

LinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.print();
list.remove(2);
list.print();

运行上述代码，输出结果为：

3 2 1 3 1

可以看到，单链表的插入和删除操作非常高效，我们可以方便地通过单链表实现许多复杂的算法。因此，掌握单链表的实现是C++程序员必不可少的基础知识之一。

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

下一篇: C++少儿编程培训班学费一般多少？

评论区

相似文章