21xrx.com
2025-06-24 15:13:09 Tuesday
登录
文章检索 我的文章 写文章
C++ 单链表完整代码实现
2023-07-04 20:52:28 深夜i     31     0
C++ 单链表 完整代码 实现

单链表是一种线性结构，由节点和指向下一个节点的指针组成。C++语言中可以通过定义结构体或类来实现单链表。下面是一份完整的C++单链表代码实现：

#include <iostream>
using namespace std;
// 定义单链表节点结构体
struct ListNode {
  int val; // 节点的值
  ListNode* next; // 指向下一个节点的指针
  ListNode(int x) : val(x), next(NULL) {} // 构造函数
};
// 定义单链表类
class LinkedList {
public:
  LinkedList()  // 构造函数
    head = NULL;
  
  ~LinkedList() { // 析构函数
    ListNode* curr = head;
    while (curr) {
      ListNode* temp = curr;
      curr = curr->next;
      delete temp;
    }
  }
  // 插入节点
  void insertNode(int val) {
    ListNode* newNode = new ListNode(val);
    if (!head)
      head = newNode;
    
    else {
      ListNode* curr = head;
      while (curr->next)
        curr = curr->next;
      
      curr->next = newNode;
    }
  }
  // 删除节点
  void deleteNode(int val) {
    if (!head)
      return;
    
    if (head->val == val) {
      ListNode* temp = head;
      head = head->next;
      delete temp;
    }
    else {
      ListNode* curr = head;
      while (curr->next && curr->next->val != val)
        curr = curr->next;
      
      if (curr->next) {
        ListNode* temp = curr->next;
        curr->next = curr->next->next;
        delete temp;
      }
    }
  }
  // 遍历节点
  void traverse() {
    ListNode* curr = head;
    while (curr)
      cout << curr->val << " ";
      curr = curr->next;
    
    cout << endl;
  }
private:
  ListNode* head; // 链表头指针
};
int main() {
  LinkedList myLinkedList;
  myLinkedList.insertNode(1);
  myLinkedList.insertNode(2);
  myLinkedList.insertNode(3);
  myLinkedList.insertNode(4);
  myLinkedList.traverse(); // 输出：1 2 3 4
  myLinkedList.deleteNode(3);
  myLinkedList.traverse(); // 输出：1 2 4
  return 0;
}

在上述代码中，我们首先定义了一个`ListNode`结构体，该结构体拥有一个`val`成员变量用于存储节点的值，以及一个`next`指针用于指向下一个节点。接着，我们使用单链表类`LinkedList`来管理整个链表。该类提供了向链表中插入节点、删除节点和遍历节点等基本操作。

在主函数中，我们首先创建了一个`myLinkedList`对象，并调用`insertNode`方法向其中插入四个节点。然后我们调用`traverse`方法输出整个链表的值，可以看出节点的值按顺序输出。接着我们调用`deleteNode`方法删除值为3的节点，并再次调用`traverse`方法输出链表，可以看出节点的值已经变为1、2、4，节点3已被成功删除。

以上便是C++单链表的完整代码实现。需要注意的是，单链表的链表头指针`head`应该在构造函数中进行初始化，析构函数中要及时释放分配的节点空间，以免造成内存泄漏。同时，在删除节点时需要特别注意边界条件，判断链表是否为空，以及头结点是否为待删除节点等。如果一些特殊情况没有特别处理，会导致链表的操作出现异常。

  
  

评论区