C++数据结构——链表
链表基础与核心概念
链表是一种动态数据结构，它通过指针将一组零散的内存块串联起来使用。与数组相比，链表在插入和删除操作上更加高效，但失去了随机访问的能力。
为什么使用链表？
1.动态大小：不需要预先知道数据量大小
2.高效插入/删除：O(1)时间复杂度（已知位置时）
3.内存效率：不需要连续内存空间
一、链表核心组件详解
1. ListNode 结构体深度解析
struct ListNode {
int val; // 数据域 - 存储节点值
ListNode* next; // 指针域 - 指向下一个节点
// 构造函数家族
ListNode() : val(0), next(nullptr) {
// 默认构造函数，创建空节点
}
ListNode(int x) : val(x), next(nullptr) {
// 带值构造函数，next自动初始化为nullptr
// 确保新节点不会意外指向其他内存
}
ListNode(int x, ListNode* next) : val(x), next(next) {
// 完整构造函数，允许指定下一个节点
// 常用于构建特定结构的链表
}
// 析构函数（高级用法）
~ListNode() {
// 注意：通常不在节点析构函数中处理next指针
// 因为链表管理应由链表类负责
// 但如果节点包含需要清理的资源，可以在此处理
}
// 成员函数示例（高级用法）
void setNext(ListNode* node) {
next = node;
}
ListNode* getNext() const {
return next;
}
int getValue() const {
return val;
}
void setValue(int value) {
val = value;
}
};
关键点说明：
next指针必须正确初始化，否则会成为野指针- 构造函数重载提供了多种创建节点的方式
- 析构函数通常保持简单，复杂清理应由链表类处理
- 添加成员函数可以封装节点操作，提高安全性
2. LinkedList 类完整实现
class LinkedList {
private:
ListNode* head; // 头节点指针
ListNode* tail; // 尾节点指针（优化尾部操作）
size_t size; // 链表长度（使用size_t避免负数）
// 私有工具函数
ListNode* getNodeAt(int index) const {
if (index < 0 || index >= size) return nullptr;
ListNode* current = head;
for (int i = 0; i < index; ++i) {
current = current->next;
}
return current;
}
public:
// 构造函数家族
LinkedList() : head(nullptr), tail(nullptr), size(0) {
// 默认构造空链表
}
LinkedList(std::initializer_list<int> initList) : LinkedList() {
// 初始化列表构造
for (int val : initList) {
append(val);
}
}
// 拷贝构造函数（深拷贝）
LinkedList(const LinkedList& other) : LinkedList() {
ListNode* current = other.head;
while (current != nullptr) {
append(current->val);
current = current->next;
}
}
// 移动构造函数（C++11）
LinkedList(LinkedList&& other) noexcept
: head(other.head), tail(other.tail), size(other.size) {
other.head = other.tail = nullptr;
other.size = 0;
}
// 析构函数
~LinkedList() {
clear(); // 确保释放所有节点
}
// 赋值运算符重载
LinkedList& operator=(const LinkedList& other) {
if (this != &other) {
clear();
ListNode* current = other.head;
while (current != nullptr) {
append(current->val);
current = current->next;
}
}
return *this;
}
// 移动赋值运算符（C++11）
LinkedList& operator=(LinkedList&& other) noexcept {
if (this != &other) {
clear();
head = other.head;
tail = other.tail;
size = other.size;
other.head = other.tail = nullptr;
other.size = 0;
}
return *this;
}
// 容量操作
bool isEmpty() const { return size == 0; }
size_t getSize() const { return size; }
// 元素访问（带边界检查）
int& operator[](int index) {
ListNode* node = getNodeAt(index);
if (node == nullptr) {
throw std::out_of_range("Index out of bounds");
}
return node->val;
}
const int& operator[](int index) const {
return const_cast<LinkedList*>(this)->operator[](index);
}
int front() const {
if (isEmpty()) throw std::out_of_range("List is empty");
return head->val;
}
int back() const {
if (isEmpty()) throw std::out_of_range("List is empty");
return tail->val;
}
// 修改操作
void append(int value) {
ListNode* newNode = new ListNode(value);
if (isEmpty()) {
head = tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
++size;
}
void prepend(int value) {
ListNode* newNode = new ListNode(value, head);
head = newNode;
if (tail == nullptr) {
tail = head;
}
++size;
}
bool insert(int index, int value) {
if (index < 0 || index > size) return false;
if (index == 0) {
prepend(value);
} else if (index == size) {
append(value);
} else {
ListNode* prev = getNodeAt(index - 1);
ListNode* newNode = new ListNode(value, prev->next);
prev->next = newNode;
++size;
}
return true;
}
bool removeAt(int index) {
if (index < 0 || index >= size) return false;
ListNode* toDelete = nullptr;
if (index == 0) {
toDelete = head;
head = head->next;
if (head == nullptr) {
tail = nullptr;
}
} else {
ListNode* prev = getNodeAt(index - 1);
toDelete = prev->next;
prev->next = toDelete->next;
if (toDelete == tail) {
tail = prev;
}
}
delete toDelete;
--size;
return true;
}
void clear() {
while (head != nullptr) {
ListNode* temp = head;
head = head->next;
delete temp;
}
tail = nullptr;
size = 0;
}
// 高级操作
void reverse() {
ListNode *prev = nullptr, *current = head, *next = nullptr;
tail = head; // 反转后尾节点变为原头节点
while (current != nullptr) {
next = current->next; // 保存下一个节点
current->next = prev; // 反转当前节点的指针
prev = current; // 移动prev指针
current = next; // 移动current指针
}
head = prev; // 最后prev指向新的头节点
}
// 迭代器支持（简化版）
class Iterator {
ListNode* current;
public:
Iterator(ListNode* node) : current(node) {}
int& operator*() { return current->val; }
Iterator& operator++() {
current = current->next;
return *this;
}
bool operator!=(const Iterator& other) const {
return current != other.current;
}
};
Iterator begin() { return Iterator(head); }
Iterator end() { return Iterator(nullptr); }
// 输出链表
friend std::ostream& operator<<(std::ostream& os, const LinkedList& list) {
ListNode* current = list.head;
os << "[";
while (current != nullptr) {
os << current->val;
if (current->next != nullptr) {
os << " -> ";
}
current = current->next;
}
os << "]";
return os;
}
};
二、高级特性深度解析
1. 迭代器实现详解
// 完整迭代器实现
class Iterator {
ListNode* current;
public:
using iterator_category = std::forward_iterator_tag;
using value_type = int;
using difference_type = std::ptrdiff_t;
using pointer = int*;
using reference = int&;
explicit Iterator(ListNode* node = nullptr) : current(node) {}
// 解引用运算符
reference operator*() const {
if (current == nullptr) {
throw std::runtime_error("Dereferencing null iterator");
}
return current->val;
}
// 成员访问运算符
pointer operator->() const {
return &(operator*());
}
// 前缀++
Iterator& operator++() {
if (current != nullptr) {
current = current->next;
}
return *this;
}
// 后缀++
Iterator operator++(int) {
Iterator temp = *this;
++(*this);
return temp;
}
// 相等比较
bool operator==(const Iterator& other) const {
return current == other.current;
}
bool operator!=(const Iterator& other) const {
return !(*this == other);
}
// 转换为bool（判断是否有效）
explicit operator bool() const {
return current != nullptr;
}
// 获取内部指针（高级用法）
ListNode* node() const {
return current;
}
};
使用示例：
LinkedList list = {1, 2, 3, 4, 5};
// 使用迭代器遍历
for (LinkedList::Iterator it = list.begin(); it != list.end(); ++it) {
std::cout << *it << " ";
}
// 使用范围for循环（C++11）
for (int val : list) {
std::cout << val << " ";
}
// 使用STL算法
auto it = std::find(list.begin(), list.end(), 3);
if (it != list.end()) {
std::cout << "Found: " << *it;
}
2. 异常安全实现
// 异常安全的插入操作
bool insertSafe(int index, int value) {
// 先创建新节点（可能抛出bad_alloc）
ListNode* newNode = nullptr;
try {
newNode = new ListNode(value);
} catch (const std::bad_alloc&) {
return false; // 内存分配失败
}
// 空链表情况
if (isEmpty()) {
if (index != 0) {
delete newNode;
return false;
}
head = tail = newNode;
++size;
return true;
}
// 插入头部
if (index == 0) {
newNode->next = head;
head = newNode;
++size;
return true;
}
// 插入中间或尾部
try {
ListNode* prev = getNodeAt(index - 1);
if (prev == nullptr && index != size) {
delete newNode;
return false;
}
newNode->next = prev->next;
prev->next = newNode;
if (prev == tail) {
tail = newNode;
}
++size;
return true;
} catch (...) {
delete newNode;
throw; // 重新抛出异常
}
}
3. 线程安全扩展（C++11）
#include 三、性能优化技巧
1. 内存池优化
class ListNodePool {
private:
std::vector<ListNode*> pool;
size_t chunkSize = 100;
void allocateChunk() {
pool.reserve(pool.size() + chunkSize);
for (size_t i = 0; i < chunkSize; ++i) {
pool.push_back(new ListNode(0));
}
}
public:
ListNode* acquire(int value) {
if (pool.empty()) {
allocateChunk();
}
ListNode* node = pool.back();
pool.pop_back();
node->val = value;
node->next = nullptr;
return node;
}
void release(ListNode* node) {
if (node != nullptr) {
node->next = nullptr;
pool.push_back(node);
}
}
~ListNodePool() {
for (ListNode* node : pool) {
delete node;
}
}
};
// 使用内存池的链表
class OptimizedLinkedList {
private:
ListNodePool pool;
// ... 其他成员
public:
void append(int value) {
ListNode* newNode = pool.acquire(value);
// ... 其他操作
}
void removeAt(int index) {
// ... 找到要删除的节点
pool.release(toDelete);
}
};
2. 缓存优化
class CachedLinkedList {
private:
ListNode* head;
ListNode* tail;
size_t size;
// 缓存最近访问的节点
mutable struct {
ListNode* node = nullptr;
int index = -1;
} cache;
ListNode* getNodeAt(int index) const {
if (index < 0 || index >= size) return nullptr;
// 检查缓存
if (cache.index != -1 && std::abs(cache.index - index) < 3) {
if (cache.index == index) return cache.node;
ListNode* current = cache.node;
int step = index > cache.index ? 1 : -1;
while (current != nullptr && cache.index != index) {
current = (step > 0) ? current->next : /* 需要双向链表支持 */;
cache.index += step;
}
if (current != nullptr) {
cache.node = current;
return current;
}
}
// 常规查找
ListNode* current = head;
for (int i = 0; i < index; ++i) {
current = current->next;
}
// 更新缓存
cache.node = current;
cache.index = index;
return current;
}
public:
// ... 其他方法需要清除缓存
void clear() {
// ... 原有清理
cache.node = nullptr;
cache.index = -1;
}
};
四、实际应用案例
1. LRU缓存实现
class LRUCache {
private:
struct CacheNode {
int key;
int value;
CacheNode* prev;
CacheNode* next;
CacheNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
std::unordered_map<int, CacheNode*> cacheMap;
CacheNode* head; // 最近使用的伪头节点
CacheNode* tail; // 最久未使用的伪尾节点
int capacity;
void addToHead(CacheNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(CacheNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(CacheNode* node) {
removeNode(node);
addToHead(node);
}
CacheNode* removeTail() {
CacheNode* node = tail->prev;
removeNode(node);
return node;
}
public:
LRUCache(int capacity) : capacity(capacity) {
head = new CacheNode(-1, -1);
tail = new CacheNode(-1, -1);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cacheMap.count(key)) return -1;
CacheNode* node = cacheMap[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (cacheMap.count(key)) {
CacheNode* node = cacheMap[key];
node->value = value;
moveToHead(node);
} else {
if (cacheMap.size() == capacity) {
CacheNode* removed = removeTail();
cacheMap.erase(removed->key);
delete removed;
}
CacheNode* newNode = new CacheNode(key, value);
cacheMap[key] = newNode;
addToHead(newNode);
}
}
~LRUCache() {
for (auto& pair : cacheMap) {
delete pair.second;
}
delete head;
delete tail;
}
};
2. 多项式运算实现
class Polynomial {
private:
struct Term {
double coefficient;
int exponent;
Term* next;
Term(double coeff, int exp, Term* n = nullptr)
: coefficient(coeff), exponent(exp), next(n) {}
};
Term* head;
public:
Polynomial() : head(nullptr) {}
void addTerm(double coeff, int exp) {
if (coeff == 0.0) return;
if (head == nullptr || exp > head->exponent) {
head = new Term(coeff, exp, head);
return;
}
Term* current = head;
while (current->next != nullptr && current->next->exponent > exp) {
current = current->next;
}
if (current->exponent == exp) {
current->coefficient += coeff;
if (current->coefficient == 0.0) {
// 需要删除该节点
Term* toDelete = current;
if (current == head) {
head = head->next;
} else {
// 需要找到前驱节点
Term* prev = head;
while (prev->next != current) {
prev = prev->next;
}
prev->next = current->next;
}
delete toDelete;
}
} else {
current->next = new Term(coeff, exp, current->next);
}
}
Polynomial add(const Polynomial& other) const {
Polynomial result;
Term* p1 = head;
Term* p2 = other.head;
while (p1 != nullptr && p2 != nullptr) {
if (p1->exponent > p2->exponent) {
result.addTerm(p1->coefficient, p1->exponent);
p1 = p1->next;
} else if (p1->exponent < p2->exponent) {
result.addTerm(p2->coefficient, p2->exponent);
p2 = p2->next;
} else {
double sum = p1->coefficient + p2->coefficient;
if (sum != 0.0) {
result.addTerm(sum, p1->exponent);
}
p1 = p1->next;
p2 = p2->next;
}
}
// 处理剩余项
while (p1 != nullptr) {
result.addTerm(p1->coefficient, p1->exponent);
p1 = p1->next;
}
while (p2 != nullptr) {
result.addTerm(p2->coefficient, p2->exponent);
p2 = p2->next;
}
return result;
}
// ... 其他多项式运算
};
六、性能分析与优化
时间复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 访问 | O(n) | 需要遍历 |
| 搜索 | O(n) | 需要遍历 |
| 插入 | O(1) | 已知位置时 |
| 删除 | O(1) | 已知位置时 |
| 头部操作 | O(1) | 直接操作头指针 |
| 尾部操作 | O(1) | 有尾指针时 |
| 中间操作 | O(n) | 需要先找到位置 |
优化建议
1.维护尾指针：可以显著提高尾部操作效率
2.双向链表：对于需要频繁前向/后向遍历的场景
3.循环链表：适合环形缓冲区等应用场景
4.跳表：对于需要快速查找的有序链表
链表作为基础数据结构，其实现质量直接影响程序性能和稳定性。通过深入理解指针操作、内存管理和各种优化技巧，可以构建出高效可靠的链表实现。
