C++单链表基本操作的代码实现 |21xrx.com

C++单链表基本操作的代码实现

2023-06-29 16:47:54 深夜i 16 0

C++ 单链表基本操作代码实现

C++单链表是一种非常常用的数据结构，在实际开发中也经常会用到。单链表的基本操作有插入、删除、查找、遍历等。在本文中，我们将为大家介绍C++单链表基本操作的代码实现。

先声明单链表结点类Node以及单链表类LinkedList：

class Node {
public:
  int data;    // 数据域
  Node* next;   // 指针域
  Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
public:
  Node* head;   // 头指针
  LinkedList() : head(nullptr) {}
  ~LinkedList();
  void insertHead(int value);
  void insertTail(int value);
  void insertBefore(Node* current, int value);
  void insertAfter(Node* current, int value);
  void deleteHead();
  void deleteTail();
  void deleteNode(Node* current);
  Node* findByValue(int value);
  Node* findByIndex(int index);
  void traversal();
};

定义了结点类Node以及单链表类LinkedList，接下来分别实现各个操作：

## insertHead

在链表头插入结点。

void LinkedList::insertHead(int value) {
  Node* newNode = new Node(value);
  if (head == nullptr)  // 链表为空
    head = newNode;
  
  else  // 链表不为空
    newNode->next = head;
    head = newNode;
  
}

## insertTail

在链表尾插入结点。

void LinkedList::insertTail(int value) {
  Node* newNode = new Node(value);
  if (head == nullptr)  // 链表为空
    head = newNode;
  
  else { // 链表不为空
    Node* current = head;
    while (current->next != nullptr)
      current = current->next;
    
    current->next = newNode;
  }
}

## insertBefore

在某个结点之前插入结点。

void LinkedList::insertBefore(Node* current, int value) {
  if (current == nullptr)   // 指定结点为空
    return;
  
  if (head == current) { // 在头结点之前插入结点
    insertHead(value);
    return;
  }
  Node* newNode = new Node(value);
  Node* prev = head;
  while (prev->next != current)
    prev = prev->next;
  
  prev->next = newNode;
  newNode->next = current;
}

## insertAfter

在某个结点之后插入结点。

void LinkedList::insertAfter(Node* current, int value) {
  if (current == nullptr)   // 指定结点为空
    return;
  
  Node* newNode = new Node(value);
  newNode->next = current->next;
  current->next = newNode;
}

## deleteHead

删除链表头结点。

void LinkedList::deleteHead() {
  if (head == nullptr)  // 链表为空
    return;
  
  Node* temp = head;
  head = head->next;
  delete temp;
}

## deleteTail

删除链表尾结点。

void LinkedList::deleteTail() {
  if (head == nullptr)  // 链表为空
    return;
  
  Node* prev = nullptr;
  Node* current = head;
  while (current->next != nullptr)
    prev = current;
    current = current->next;
  
  if (prev == nullptr)  // 链表只有一个结点
    head = nullptr;
  
  else
    prev->next = nullptr;
  
  delete current;
}

## deleteNode

删除某个结点。

void LinkedList::deleteNode(Node* current) {
  if (current == nullptr)   // 指定结点为空
    return;
  
  if (head == current) { // 删除头结点
    deleteHead();
    return;
  }
  Node* prev = head;
  while (prev->next != current)
    prev = prev->next;
  
  prev->next = current->next;
  delete current;
}

## findByValue

根据结点值查找结点。

Node* LinkedList::findByValue(int value) {
  Node* current = head;
  while (current != nullptr) {
    if (current->data == value)
      return current;
    
    current = current->next;
  }
  return nullptr;
}

## findByIndex

根据结点下标查找结点。

Node* LinkedList::findByIndex(int index) {
  if (index < 0)   // 下标非法
    return nullptr;
  
  Node* current = head;
  int i = 0;
  while (current != nullptr && i < index) {
    current = current->next;
    i++;
  }
  if (i == index)   // 找到了指定结点
    return current;
  
  else  // 下标越界
    return nullptr;
  
}

## traversal

遍历链表。

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

至此，C++单链表基本操作的代码实现就完成了。大家可以根据自己的需求进行使用和扩展。

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

下一篇: C++实现鼠标点击功能

评论区

相似文章