C++使用模板实现单链表

前言

单链表是理解指针操作和动态内存管理最合适的练手容器：每个节点持有一个值和一条指向后继的指针，插入删除只改指针，不搬移元素。把它写成类模板，则顺带练到了模板的定义位置、依赖名解析、实例化和「三法则/五法则」这几个 C++ 的核心知识点。

初学者常见的误解有几种。第一，把模板类的成员函数实现放进.cpp文件，然后在另一个翻译单元里使用，链接时报「undefined reference」——模板不是普通函数，编译器在看到使用点之前不会为具体类型生成代码。第二，以为析构函数只要delete head_就够了——那样只释放第一个节点，后面的全部泄漏。第三，拷贝一个链表时直接写head_ = other.head_，结果两个对象共享节点，析构时重复释放。

本文实现一个带迭代器、支持深拷贝和移动语义的SinglyLinkedList<T>，重点说明所有权转移、异常安全和模板代码的组织方式。代码基准为 C++17。

一、节点设计与模板的放置位置

1.1 节点结构

// 适用于 C++17
template <typename T>
class SinglyLinkedList {
private:
struct Node {
T value;
Node* next;

Node(const T& v, Node* n) : value(v), next(n) {}
Node(T&& v, Node* n) : value(std::move(v)), next(n) {}
};

Node* head_ = nullptr;
Node* tail_ = nullptr;
std::size_t size_ = 0;
};

Node放在private里，外部看不见它的布局，这是封装的关键：以后想把单链表改成带哨兵头节点、或者给节点加缓存字段，都不会影响使用者。代价是迭代器必须作为嵌套类定义在类内，才能访问Node。

tail_不是链表结构必需的，但有了它push_back才是 O(1)；没有它每次尾部插入都要从头遍历。size_同理，用 O(1) 的空间换 O(1) 的size()。

1.2 为什么模板要写在头文件里

普通函数在.cpp里定义、在头文件里声明，链接器能在目标文件里找到符号。模板不同：它本身不是代码，只是生成代码的图纸。编译器在实例化点（通常是使用处）才用具体类型替换T并生成机器码。如果定义在另一个.cpp里，当前翻译单元只看到声明，无法实例化，链接阶段就找不到符号。

显式实例化的写法是template class SinglyLinkedList<int>;，它强制编译器在这里生成int版本的代码。缺点是每加一种类型都要改一次，适合类型集合固定的库。

1.3 依赖名与typename

在模板内部引用依赖于T的嵌套类型时，编译器默认按「值」而不是「类型」解析，必须加typename。类内定义时这不是问题，但在类外写成员函数就需要：

// 适用于 C++17
template <typename T>
typename SinglyLinkedList<T>::iterator
SinglyLinkedList<T>::begin() {
return iterator(head_);
}

这里的typename不能省，否则编译器会把SinglyLinkedList<T>::iterator当成一个静态数据成员。同理，如果嵌套的是模板（比如T::template rebind<U>），还要加template关键字。这些规则属于「两阶段名字查找」：不依赖T的名字在定义时查，依赖T的名字在实例化时查。

二、五法则：析构、拷贝、移动

2.1 析构必须是遍历释放

// 适用于 C++17
~SinglyLinkedList() { clear(); }

void clear() noexcept {
Node* cur = head_;
while (cur != nullptr) {
Node* next = cur->next; // 先存后继，再删当前
delete cur;
cur = next;
}
head_ = tail_ = nullptr;
size_ = 0;
}

顺序不能反：先delete cur再读cur->next是释放后使用（use-after-free），属于未定义行为。clear()标noexcept与析构函数默认的noexcept(true)一致，避免异常逃逸触发std::terminate。

2.2 拷贝构造要深拷贝

默认的拷贝构造函数做的是逐成员复制，复制完两个链表指向同一批节点。任何一个析构，另一个就悬垂；两个都析构，就是重复释放（double free）。必须自己写：

// 适用于 C++17
SinglyLinkedList(const SinglyLinkedList& other) {
for (Node* p = other.head_; p != nullptr; p = p->next) {
push_back(p->value);
}
}

逐个push_back在分配失败时会抛std::bad_alloc。此时构造函数未完成，析构函数不会运行，head_是裸指针也不会被销毁，已建的节点就泄漏了。严格写法要么在try/catch里clear()再抛，要么让节点由std::unique_ptr串起来。

更稳的写法是先用局部对象tmp构造，成功后swap(tmp)：tmp在异常展开时会正常析构，this保持空链表状态。

2.3 拷贝赋值用 copy-and-swap

// 适用于 C++17
SinglyLinkedList& operator=(const SinglyLinkedList& other) {
if (this != &other) {
SinglyLinkedList tmp(other); // 先完整复制，失败则原对象不变
swap(tmp);
}
return *this;
}

void swap(SinglyLinkedList& other) noexcept {
std::swap(head_, other.head_);
std::swap(tail_, other.tail_);
std::swap(size_, other.size_);
}

自赋值检查不能省：a = a时如果不检查，先清空自己再读other就读到了已释放的内存。copy-and-swap 同时给出了强异常保证——复制失败时*this原封不动。

2.4 移动构造与移动赋值

移动的语义是「偷走指针，把源置空」：

// 适用于 C++17
SinglyLinkedList(SinglyLinkedList&& other) noexcept
: head_(other.head_), tail_(other.tail_), size_(other.size_) {
other.head_ = nullptr;
other.tail_ = nullptr;
other.size_ = 0;
}

SinglyLinkedList& operator=(SinglyLinkedList&& other) noexcept {
if (this != &other) {
clear();
head_ = other.head_;
tail_ = other.tail_;
size_ = other.size_;
other.head_ = nullptr;
other.tail_ = nullptr;
other.size_ = 0;
}
return *this;
}

移动构造必须把源对象置成合法的空状态，否则源对象析构时会把已经转移走的节点再删一遍。noexcept很重要：std::vector扩容时只有在移动构造是noexcept的情况下才会选择移动而不是拷贝。

注意std::move本身不移动任何东西，它只是把表达式转成右值引用，真正转移指针的是上面这些函数。

三、迭代器与边界操作

3.1 一个够用的前向迭代器

迭代器是一个只持有Node*的小类：operator*返回node_->value，operator->返回成员地址，前置++把指针推到next。再补上后置++、==、!=和默认构造，就满足前向迭代器（forward iterator）的最低要求。

end()用空指针表示「尾后位置」，因此对end()解引用是 UB。有了begin/end，基于范围的 for 循环就能直接用：

// 适用于 C++17
SinglyLinkedList<int> list;
for (int v : list) {
// ...
}

还缺const_iterator，以及cbegin/cend。真实实现里通常用一个模板化的迭代器基类同时生成两者，这里为了篇幅从简。

3.2 尾部插入与按下标插入

// 适用于 C++17
void push_back(const T& v) {
Node* n = new Node(v, nullptr);
if (tail_ == nullptr) {
head_ = tail_ = n;
} else {
tail_->next = n;
tail_ = n;
}
++size_;
}

所有插入函数都遵循同一个顺序：先分配、再改指针、最后改计数。如果new抛bad_alloc，链表结构完全没动，满足强异常保证。push_front是对称的：新节点的next指向原head_，若原链表为空则同时更新tail_。

按下标插入insert_at(index, value)需要先走到第index - 1个节点，循环条件是i + 1 < index，走完后prev正好是前驱。index == size_时prev是尾节点，新节点的next为nullptr，此时要更新tail_。index == 0直接转给push_front。

3.3 删除与尾指针维护

删除分两种情形。删头节点时把head_后移；若链表因此变空，tail_必须一并置空。删中间或尾部节点时先找到前驱，把prev->next指向victim->next，再delete victim。

最容易漏的是尾节点分支：如果被删的正好是tail_，要把tail_回退到前驱，否则tail_悬垂，下一次push_back就往已释放的内存里写。删除唯一节点时同时触发「head_变空」和「tail_需要置空」两个条件，这两处必须一起处理。

四、完整示例

// 适用于 C++17
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>

template <typename T>
class SinglyLinkedList {
private:
struct Node {
T value;
Node* next;
Node(const T& v, Node* n) : value(v), next(n) {}
Node(T&& v, Node* n) : value(std::move(v)), next(n) {}
};

public:
class iterator {
public:
iterator() = default;
explicit iterator(Node* p) : node_(p) {}
T& operator*() const { return node_->value; }
T* operator->() const { return &node_->value; }
iterator& operator++() { node_ = node_->next; return *this; }
iterator operator++(int) {
iterator tmp = *this;
node_ = node_->next;
return tmp;
}
bool operator==(const iterator& o) const { return node_ == o.node_; }
bool operator!=(const iterator& o) const { return node_ != o.node_; }
private:
Node* node_ = nullptr;
};

SinglyLinkedList() = default;
~SinglyLinkedList() { clear(); }

SinglyLinkedList(const SinglyLinkedList& other) {
SinglyLinkedList tmp;
for (Node* p = other.head_; p != nullptr; p = p->next) {
tmp.push_back(p->value);
}
swap(tmp);
}

SinglyLinkedList& operator=(const SinglyLinkedList& other) {
if (this != &other) {
SinglyLinkedList tmp(other);
swap(tmp);
}
return *this;
}

SinglyLinkedList(SinglyLinkedList&& other) noexcept
: head_(other.head_), tail_(other.tail_), size_(other.size_) {
other.head_ = nullptr;
other.tail_ = nullptr;
other.size_ = 0;
}

SinglyLinkedList& operator=(SinglyLinkedList&& other) noexcept {
if (this != &other) {
clear();
head_ = other.head_;
tail_ = other.tail_;
size_ = other.size_;
other.head_ = nullptr;
other.tail_ = nullptr;
other.size_ = 0;
}
return *this;
}

void push_front(const T& v) {
Node* n = new Node(v, head_);
head_ = n;
if (tail_ == nullptr) tail_ = n;
++size_;
}

void push_back(const T& v) {
Node* n = new Node(v, nullptr);
if (tail_ == nullptr) {
head_ = tail_ = n;
} else {
tail_->next = n;
tail_ = n;
}
++size_;
}

bool insert_at(std::size_t index, const T& value) {
if (index > size_) return false;
if (index == 0) { push_front(value); return true; }
Node* prev = head_;
for (std::size_t i = 0; i + 1 < index; ++i) prev = prev->next;
Node* n = new Node(value, prev->next);
prev->next = n;
if (n->next == nullptr) tail_ = n;
++size_;
return true;
}

bool erase_at(std::size_t index) {
if (index >= size_) return false;
Node* victim = nullptr;
if (index == 0) {
victim = head_;
head_ = head_->next;
if (head_ == nullptr) tail_ = nullptr;
} else {
Node* prev = head_;
for (std::size_t i = 0; i + 1 < index; ++i) prev = prev->next;
victim = prev->next;
prev->next = victim->next;
if (victim == tail_) tail_ = prev;
}
delete victim;
--size_;
return true;
}

void clear() noexcept {
Node* cur = head_;
while (cur != nullptr) {
Node* next = cur->next;
delete cur;
cur = next;
}
head_ = tail_ = nullptr;
size_ = 0;
}

void swap(SinglyLinkedList& other) noexcept {
std::swap(head_, other.head_);
std::swap(tail_, other.tail_);
std::swap(size_, other.size_);
}

iterator begin() { return iterator(head_); }
iterator end() { return iterator(nullptr); }
bool empty() const { return head_ == nullptr; }
std::size_t size() const { return size_; }
T& front() { return head_->value; }

private:
Node* head_ = nullptr;
Node* tail_ = nullptr;
std::size_t size_ = 0;
};

int main() {
SinglyLinkedList<std::string> words;
words.push_back("alpha");
words.push_back("beta");
words.push_front("zero");

words.insert_at(1, "one");
words.erase_at(2);

for (const auto& w : words) {
std::cout << w << '\n';
}

SinglyLinkedList<std::string> copy = words;
copy.push_back("gamma");

SinglyLinkedList<std::string> moved = std::move(copy);
std::cout << "moved size = " << moved.size() << '\n';
return 0;
}

常见坑点

1. 
   
2. ❌ 把模板成员函数定义放进.cpp再跨文件使用
3. 
   

✅ 定义和声明都放头文件，或在.cpp里显式实例化 编译器在实例化点必须看到完整定义，否则链接期报未定义符号。

1. 
   
2. ❌ 析构函数只写delete head_;
3. 
   

✅ 循环遍历，先存next再删当前节点 只删头节点会让后续所有节点泄漏。

1. 
   
2. ❌ 默认拷贝构造，让两个链表共享节点
3. 
   

✅ 手写深拷贝，逐节点复制值 默认拷贝是浅拷贝，析构时 double free 属于 UB。

1. 
   
2. ❌ 拷贝赋值不检查自赋值a = a
3. 
   

✅if (this != &other)或直接用 copy-and-swap 先清空自己再读other会读到已释放内存。

1. 
   
2. ❌ 移动构造后不把源对象的head_置空
3. 
   

✅ 源对象置为合法的空状态 源对象析构时会重复释放已经转移的节点。

1. 
   
2. ❌ 删除尾节点后不更新tail_
3. 
   

✅ 若被删的是尾节点，tail_回退到前驱；链表空时置nullptr悬垂的tail_会让下一次push_back写已释放内存。

1. 
   
2. ❌ 在模板里写T::value_type不加typename
3. 
   

✅typename T::value_type依赖名默认按值解析，编译器无法判断它是类型。

总结

模板单链表的价值不在链表本身——标准库的std::forward_list已经覆盖了绝大多数需求——而在于它把「模板定义位置、依赖名、五法则、异常安全、迭代器约定」压缩进一个几十行的类里。亲手写一遍并逐条推演边界，比背规则更能形成直觉。