21xrx.com
2025-06-24 23:55:02 Tuesday
文章检索 我的文章 写文章
C++实现单链表代码
2023-07-05 11:51:58 深夜i     22     0
C++ 单链表 实现 代码

单链表是一种常用的数据结构，可以通过链式结构存储一系列的数据。在C++中，我们可以使用指针来实现单链表。下面是一个简单的单链表的C++实现代码。

单链表节点的定义

我们首先需要定义单链表的节点，每个节点由两个部分组成：data用于存储节点的数据，next指向下一个节点。

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

单链表实现

我们可以定义一个单链表类来实现单链表的相关操作。下面是一个简单的单链表类的定义，包括头指针head和相关的操作函数。

class LinkedList{
public:
  LinkedList(); //构造函数
  ~LinkedList(); //析构函数
  void insert(int value); //在链表的结尾插入一个节点
  void remove(int value); //删除指定数值的节点
  bool contains(int value); //判断链表中是否存在指定数值的节点
  void clear(); //清空链表
  void print(); //打印链表的节点
private:
  ListNode* head; //头指针
};

构造函数

构造函数主要用于初始化单链表，将头指针head设置为NULL。

LinkedList::LinkedList()
  head = NULL;

析构函数

析构函数用于释放单链表所占用的内存，需要释放每个节点占用的内存空间。

LinkedList::~LinkedList(){
  ListNode* current = head;
  ListNode* temp;
  while(current != NULL)
    temp = current->next;
    delete current;
    current = temp;
  
}

插入节点

在单链表的结尾插入一个节点，需要遍历链表找到最后一个节点，然后将新的节点插入到最后一个节点之后。

void LinkedList::insert(int value){
  ListNode* newNode = new ListNode; //新建一个节点
  newNode->data = value;
  newNode->next = NULL;
  if(head == NULL) //如果链表为空
  ListNode* current = head;
  while(current->next != NULL) //遍历链表找到最后一个节点
    current = current->next;
  
  current->next = newNode; //将新节点插入到最后一个节点之后
}

删除节点

删除链表中一个指定数值的节点，需要遍历链表找到节点，并删除该节点。

void LinkedList::remove(int value){
  if(head == NULL)直接返回
    return;
  
  if(head->data == value){ //如果头指针指向的节点就是要删除的节点，将头指针指向下一个节点即可
    ListNode* temp = head;
    head = head->next;
    delete temp;
    return;
  }
  ListNode* current = head;
  while(current->next != NULL && current->next->data != value) //遍历链表找到节点
    current = current->next;
  
  if(current->next == NULL)直接返回
    return;
  
  ListNode* temp = current->next;
  current->next = current->next->next; //删除节点
  delete temp;
}

查找节点

判断链表中是否存在指定数值的节点，需要遍历链表并查找节点。

bool LinkedList::contains(int value){
  ListNode* current = head;
  while(current != NULL){ //遍历链表查找节点
    if(current->data == value)
      return true;
    
    current = current->next;
  }
  return false;
}

清空链表

清空链表需要释放每个节点所占用的内存空间。

void LinkedList::clear(){
  ListNode* current = head;
  ListNode* temp;
  while(current != NULL)
    temp = current->next;
    delete current;
    current = temp;
  
  head = NULL;
}

打印链表

打印链表的节点，需要遍历链表并依次输出节点的数值。

void LinkedList::print(){
  ListNode* current = head;
  while(current != NULL) //遍历链表打印节点
    cout << current->data << " ";
    current = current->next;
  
  cout << endl;
}

总结

上述代码实现了单链表的基本操作，包括插入节点、删除节点、查找节点、清空链表和输出链表的节点等操作。单链表的实现需要注意指针的使用和内存管理，希望大家能够通过实践深入了解单链表的相关知识。

  
  

评论区