【C++初阶】list的模拟实现 附源码

**C++ 初阶：List 的模拟实现**

在 C++ 中，`std::list` 是一个双向链表容器，它提供了高效的插入、删除和查找元素的功能。然而，在实际开发中，我们可能需要自己实现一个类似于 `std::list` 的数据结构来满足特定的需求。在本文中，我们将模拟实现一个简单的双向链表，并且附带源码。

### 模拟实现原理我们的模拟实现基于以下基本概念：

* **结点（Node）**：每个结点代表一个元素，包含两个指针分别指向前一个结点和后一个结点。
* **头结点（Head Node）** 和 **尾结点（Tail Node）**：头结点指向链表的第一个元素，而尾结点指向最后一个元素。

### 模拟实现源码

cpp#include <iostream>

// 结点类，包含两个指针分别指向前一个结点和后一个结点class Node {
public:
 int data; // 元素值 Node* prev; // 前一个结点的指针 Node* next; // 后一个结点的指针 // 构造函数，初始化元素值、前一个结点和后一个结点 Node(int value) {
 data = value;
 prev = nullptr;
 next = nullptr;
 }
};

// 双向链表类，包含头结点、尾结点以及插入、删除等方法class DoublyLinkedList {
private:
 Node* head; // 头结点的指针 Node* tail; // 尾结点的指针public:
 // 构造函数，初始化头结点和尾结点 DoublyLinkedList() {
 head = nullptr;
 tail = nullptr;
 }

 // 销毁链表 ~DoublyLinkedList() {
 while (head != nullptr) {
 Node* temp = head;
 head = head->next;
 delete temp;
 }
 }

 // 插入元素到头结点前面 void insertAtHead(int value) {
 Node* newNode = new Node(value);
 if (head == nullptr) {
 head = newNode;
 tail = newNode;
 } else {
 newNode->next = head;
 head->prev = newNode;
 head = newNode;
 }
 }

 // 插入元素到尾结点后面 void insertAtTail(int value) {
 Node* newNode = new Node(value);
 if (tail == nullptr) {
 head = newNode;
 tail = newNode;
 } else {
 newNode->prev = tail;
 tail->next = newNode;
 tail = newNode;
 }
 }

 // 删除头结点 void deleteHead() {
 if (head != nullptr) {
 Node* temp = head;
 head = head->next;
 if (head == nullptr) {
 tail = nullptr;
 } else {
 head->prev = nullptr;
 }
 delete temp;
 }
 }

 // 删除尾结点 void deleteTail() {
 if (tail != nullptr) {
 Node* temp = tail;
 tail = tail->prev;
 if (tail == nullptr) {
 head = nullptr;
 } else {
 tail->next = nullptr;
 }
 delete temp;
 }
 }

 // 打印链表 void printList() {
 Node* temp = head;
 while (temp != nullptr) {
 std::cout << temp->data << " ";
 temp = temp->next;
 }
 std::cout << std::endl;
 }
};

int main() {
 DoublyLinkedList list;

 // 插入元素 list.insertAtHead(10);
 list.insertAtTail(20);
 list.insertAtHead(5);
 list.insertAtTail(15);

 // 打印链表 list.printList(); // 输出：51020 // 删除头结点 list.deleteHead();

 // 打印链表 list.printList(); // 输出：1020 return0;
}

在这个例子中，我们定义了一个 `Node` 类来代表每个元素，包含两个指针分别指向前一个结点和后一个结点。然后我们定义了一个 `DoublyLinkedList` 类来模拟实现双向链表的功能。

### 模拟实现方法* **insertAtHead(int value)**：插入元素到头结点前面。
* **insertAtTail(int value)**：插入元素到尾结点后面。
* **deleteHead()**：删除头结点。
* **deleteTail()**：删除尾结点。

### 模拟实现源码注释

cpp// 结点类，包含两个指针分别指向前一个结点和后一个结点class Node {
public:
 int data; // 元素值 Node* prev; // 前一个结点的指针 Node* next; // 后一个结点的指针 // 构造函数，初始化元素值、前一个结点和后一个结点 Node(int value) {
 data = value;
 prev = nullptr;
 next = nullptr;
 }
};

// 双向链表类，包含头结点、尾结点以及插入、删除等方法class DoublyLinkedList {
private:
 Node* head; // 头结点的指针 Node* tail; // 尾结点的指针public:
 // 构造函数，初始化头结点和尾结点 DoublyLinkedList() {
 head = nullptr;
 tail = nullptr;
 }

 // 销毁链表 ~DoublyLinkedList() {
 while (head != nullptr) {
 Node* temp = head;
 head = head->next;
 delete temp;
 }
 }

 // 插入元素到头结点前面 void insertAtHead(int value) {
 Node* newNode = new Node(value);
 if (head == nullptr) {
 head = newNode;
 tail = newNode;
 } else {
 newNode->next = head;
 head->prev = newNode;
 head = newNode;
 }
 }

 // 插入元素到尾结点后面 void insertAtTail(int value) {
 Node* newNode = new Node(value);
 if (tail == nullptr) {
 head = newNode;
 tail = newNode;
 } else {
 newNode->prev = tail;
 tail->next = newNode;
 tail = newNode;
 }
 }

 // 删除头结点 void deleteHead() {
 if (head != nullptr) {
 Node* temp = head;
 head = head->next;
 if (head == nullptr) {
 tail = nullptr;
 } else {
 head->prev = nullptr;
 }
 delete temp;
 }
 }

 // 删除尾结点 void deleteTail() {
 if (tail != nullptr) {
 Node* temp = tail;
 tail = tail->prev;
 if (tail == nullptr) {
 head = nullptr;
 } else {
 tail->next = nullptr;
 }
 delete temp;
 }
 }

 // 打印链表 void printList() {
 Node* temp = head;
 while (temp != nullptr) {
 std::cout << temp->data << " ";
 temp = temp->next;
 }
 std::cout << std::endl;
 }
};

在这个例子中，我们定义了一个 `Node` 类来代表每个元素，包含两个指针分别指向前一个结点和后一个结点。然后我们定义了一个 `DoublyLinkedList` 类来模拟实现双向链表的功能。

### 模拟实现方法* **insertAtHead(int value)**：插入元素到头结点前面。
* **insertAtTail(int value)**：插入元素到尾结点后面。
* **deleteHead()**：删除头结点。
* **deleteTail()**：删除尾结点。

### 模拟实现源码注释

cpp// 结点类，包含两个指针分别指向前一个结点和后一个结点class Node {
public:
 int data; // 元素值 Node* prev; // 前一个结点的指针 Node* next; // 后一个结点的指针 // 构造函数，初始化元素值、前一个结点和后一个结点 Node(int value) {
 data = value;
 prev = nullptr;
 next = nullptr;
 }
};

// 双向链表类，包含头结点、尾结点以及插入、删除等方法class DoublyLinkedList {
private:
 Node* head; // 头结点的指针 Node* tail; // 尾结点的指针public:
 // 构造