在C++中，鏈表是一種常見的數據結構，它由一系列節點組成，每個節點包含數據部分和指向下一個節點的指針。C++標準庫（STL）中提供了std::list和std::forward_list兩種鏈表實現，分別對應雙向鏈表和單向鏈表。此外，也可以通過手動實現鏈表來加深對鏈表的理解。

1. C++標準庫中的鏈表

（1）std::list（雙向鏈表）

std::list是C++標準庫中的雙向鏈表實現，每個節點包含指向前一個節點和后一個節點的指針。它支持高效的插入和刪除操作，但隨機訪問效率較低。

• 基本操作

  #include <iostream>
  #include <list>int main() {std::list<int> myList;// 插入元素myList.push_back(10); // 在鏈表尾部插入myList.push_front(20); // 在鏈表頭部插入myList.insert(myList.begin() + 1, 30); // 在指定位置插入// 遍歷鏈表for (int value : myList) {std::cout << value << " ";}std::cout << std::endl;// 刪除元素myList.pop_back(); // 刪除尾部元素myList.pop_front(); // 刪除頭部元素myList.erase(myList.begin() + 1); // 刪除指定位置的元素// 遍歷鏈表for (int value : myList) {std::cout << value << " ";}std::cout << std::endl;return 0;
  }

（2）std::forward_list（單向鏈表）

std::forward_list是C++11引入的單向鏈表實現，每個節點只包含指向下一個節點的指針。它比std::list更輕量，但只能單向遍歷。

• 基本操作

  #include <iostream>
  #include <forward_list>int main() {std::forward_list<int> myList;// 插入元素myList.push_front(10); // 在鏈表頭部插入myList.push_front(20);myList.insert_after(myList.begin(), 30); // 在指定位置插入// 遍歷鏈表for (int value : myList) {std::cout << value << " ";}std::cout << std::endl;// 刪除元素myList.pop_front(); // 刪除頭部元素myList.erase_after(myList.begin()); // 刪除指定位置的元素// 遍歷鏈表for (int value : myList) {std::cout << value << " ";}std::cout << std::endl;return 0;
  }

2. 手動實現鏈表

手動實現鏈表可以幫助更好地理解鏈表的內部機制。以下是單向鏈表和雙向鏈表的基本實現。

（1）單向鏈表

#include <iostream>// 定義鏈表節點
struct Node {int data;Node* next;Node(int value) : data(value), next(nullptr) {}
};// 定義鏈表類
class LinkedList {
private:Node* head;public:LinkedList() : head(nullptr) {}// 插入元素到鏈表尾部void append(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;}}// 插入元素到鏈表頭部void prepend(int value) {Node* newNode = new Node(value);newNode->next = head;head = newNode;}// 刪除元素void remove(int value) {if (head == nullptr) return;if (head->data == value) {Node* temp = head;head = head->next;delete temp;return;}Node* current = head;while (current->next != nullptr && current->next->data != value) {current = current->next;}if (current->next != nullptr) {Node* temp = current->next;current->next = temp->next;delete temp;}}// 遍歷鏈表void print() const {Node* current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}// 析構函數，釋放鏈表內存~LinkedList() {Node* current = head;while (current != nullptr) {Node* temp = current;current = current->next;delete temp;}}
};int main() {LinkedList list;list.append(10);list.append(20);list.prepend(5);list.print(); // 輸出：5 10 20list.remove(10);list.print(); // 輸出：5 20return 0;
}

（2）雙向鏈表

#include <iostream>// 定義鏈表節點
struct Node {int data;Node* next;Node* prev;Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};// 定義鏈表類
class DoublyLinkedList {
private:Node* head;Node* tail;public:DoublyLinkedList() : head(nullptr), tail(nullptr) {}// 插入元素到鏈表尾部void append(int value) {Node* newNode = new Node(value);if (head == nullptr) {head = newNode;tail = newNode;} else {tail->next = newNode;newNode->prev = tail;tail = newNode;}}// 插入元素到鏈表頭部void prepend(int value) {Node* newNode = new Node(value);if (head == nullptr) {head = newNode;tail = newNode;} else {newNode->next = head;head->prev = newNode;head = newNode;}}// 刪除元素void remove(int value) {Node* current = head;while (current != nullptr && current->data != value) {current = current->next;}if (current == nullptr) return;if (current->prev != nullptr) {current->prev->next = current->next;} else {head = current->next;}if (current->next != nullptr) {current->next->prev = current->prev;} else {tail = current->prev;}delete current;}// 遍歷鏈表void print() const {Node* current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}// 析構函數，釋放鏈表內存~DoublyLinkedList() {Node* current = head;while (current != nullptr) {Node* temp = current;current = current->next;delete temp;}}
};int main() {DoublyLinkedList list;list.append(10);list.append(20);list.prepend(5);list.print(); // 輸出：5 10 20list.remove(10);list.print(); // 輸出：5 20return 0;
}

總結

• 標準庫鏈表：std::list和std::forward_list提供了豐富的功能和高效的插入刪除操作，適合大多數應用場景。

• 手動實現鏈表：通過手動實現鏈表，可以加深對鏈表內部機制的理解，例如節點的創建、插入、刪除和內存管理等。