【C++进阶之路】list的基本使用和模拟实现

**C++进阶之路**

在 C++ 的学习过程中，链表（List）是一个非常重要的数据结构。它能够高效地存储和管理大量的元素，而不像数组那样需要预先分配固定大小的空间。链表的基本使用和模拟实现是 C++ 进阶之路中的一个关键环节。

**1. 链表的基本概念**

链表是一种线性数据结构，通过指针将每个结点连接起来。每个结点包含两个部分：一个用于存储元素的值（也称为数据），另一个用于存储下一个结点的指针（也称为 next 指针）。

**2. 链表的基本操作**

链表支持以下基本操作：

* **插入**:在链表中插入新元素。
* **删除**:从链表中删除指定元素。
* **查找**:在链表中找到指定元素。
* **遍历**:按照链表中的顺序访问每个元素。

**3. 链表的实现**

下面是 C++ 中链表的基本实现：

cpp// Node 结构体，代表一个结点struct Node {
 int data; // 存储元素的值 Node* next; // 下一个结点的指针};

// List 类，代表一个链表class List {
private:
 Node* head_; // 链表头部结点的指针public:
 // 构造函数，初始化链表 List() : head_(nullptr) {}

 // 析构函数，释放链表中的所有结点 ~List() { clear(); }

 // 插入新元素到链表中 void insert(int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = head_;
 head_ = newNode;
 }

 // 删除指定元素从链表中 void remove(int data) {
 if (head_ == nullptr) return;

 if (head_->data == data) {
 Node* temp = head_;
 head_ = head_->next;
 delete temp;
 return;
 }

 Node* prev = head_;
 while (prev->next != nullptr && prev->next->data != data) {
 prev = prev->next;
 }

 if (prev->next != nullptr) {
 Node* temp = prev->next;
 prev->next = prev->next->next;
 delete temp;
 }
 }

 // 查找指定元素在链表中 bool find(int data) {
 Node* current = head_;
 while (current != nullptr && current->data != data) {
 current = current->next;
 }

 return current != nullptr;
 }

 // 遍历链表中的所有元素 void traverse() {
 Node* current = head_;
 while (current != nullptr) {
 std::cout << current->data << " ";
 current = current->next;
 }
 std::cout << std::endl;
 }

 // 清除链表中的所有结点 void clear() {
 while (head_ != nullptr) {
 Node* temp = head_;
 head_ = head_->next;
 delete temp;
 }
 }
};

cppint main() {
 List list;

 // 插入元素到链表中 list.insert(10);
 list.insert(20);
 list.insert(30);

 // 遍历链表中的所有元素 std::cout << "链表中的元素：";
 list.traverse();

 // 删除指定元素从链表中 list.remove(20);

 // 遍历链表中的所有元素 std::cout << "链表中的元素（删除20 后）：";
 list.traverse();

 return0;
}

cpp// Node 结构体，代表一个结点struct Node {
 int data; // 存储元素的值};

// List 类，代表一个链表class List {
private:
 Node* head_; // 链表头部结点的指针public:
 // 构造函数，初始化链表 List() : head_(nullptr) {}

 // 析构函数，释放链表中的所有结点 ~List() { clear(); }

 // 插入新元素到链表中 void insert(int data) {
 Node* newNode = new Node();
 newNode->data = data;
 if (head_ == nullptr) {
 head_ = newNode;
 } else {
 Node* current = head_;
 while (current->next != nullptr) {
 current = current->next;
 }
 current->next = newNode;
 }
 }

 // 删除指定元素从链表中 void remove(int data) {
 if (head_ == nullptr) return;

 if (head_->data == data) {
 Node* temp = head_;
 head_ = head_->next;
 delete temp;
 return;
 }

 Node* current = head_;
 while (current->next != nullptr && current->next->data != data) {
 current = current->next;
 }

 if (current->next != nullptr) {
 Node* temp = current->next;
 current->next = current->next->next;
 delete temp;
 }
 }

 // 查找指定元素在链表中 bool find(int data) {
 Node* current = head_;
 while (current != nullptr && current->data != data) {
 current = current->next;
 }

 return current != nullptr;
 }

 // 遍历链表中的所有元素 void traverse() {
 Node* current = head_;
 while (current != nullptr) {
 std::cout << current->data << " ";
 current = current->next;
 }
 std::cout << std::endl;
 }

 // 清除链表中的所有结点 void clear() {
 while (head_ != nullptr) {
 Node* temp = head_;
 head_ = head_->next;
 delete temp;
 }
 }
};

cppint main() {
 List list;

 // 插入元素到链表中 list.insert(10);
 list.insert(20);
 list.insert(30);

 // 遍历链表中的所有元素 std::cout << "链表中的元素：";
 list.traverse();

 // 删除指定元素从链表中 list.remove(20);

 // 遍历链表中的所有元素 std::cout << "链表中的元素（删除20 后）：";
 list.traverse();

 return0;
}