企业官网建设流程全解析

前言

单链表是最基础的手写数据结构：每个节点保存一个值和指向下一个节点的指针，节点在内存中不必连续。它适合频繁在头部插入删除、或者需要在遍历中「摘除」节点的场景；代价是不能随机访问，查找第 k 个元素要从头走。

自己实现单链表，难点不在「怎么连指针」，而在边界与所有权：头指针为空时怎么插入、删除尾节点后尾指针指向哪里、析构时会不会漏掉节点、拷贝对象时会不会两个链表共用同一批节点导致重复释放。这些问题在 LeetCode 的裸指针接口里往往被隐藏，在真实工程里却必须处理。

本文实现一个带head、tail、size三个成员的链表类，覆盖头插、尾插、按位置插入、按位置删除、查找、反转、清空，以及析构、拷贝、移动。代码以 C++17 为准，使用裸指针new/delete是为了讲清所有权；工程代码可以用std::unique_ptr串联节点，避免手写析构。

一、节点设计与类的不变量

节点只需要两个字段：值、下一个节点的指针。把节点定义在链表类的私有区域，外部只能通过链表的接口操作，避免调用方直接改next破坏结构。

链表类维护三个成员：

这三个不变量是实现的「合同」。每次插入删除后都要检查：空表时head_与tail_是否同时为空；非空时tail_是否真的指向最后一个节点；size_是否与节点数一致。很多 bug 不是指针写错，而是某次操作后不变量被破坏，后续操作在错误状态上继续执行。

size_让size()变成 O(1)，代价是每次插入删除都要维护。如果不需要常数时间取长度，也可以省掉它，遍历计数，但那样每次取长度都是 O(n)。

二、插入：先接后断，别丢链

头插最简单：新节点的next指向当前head_，再让head_指向新节点。如果原表为空，还要把tail_也指向新节点。顺序不能反：先让head_指向新节点，再设置新节点的next，就会把原来的整条链表丢掉。

尾插分两种情况。空表时，新节点既是头也是尾，head_、tail_都指向它。非空时，把tail_->next指向新节点，再更新tail_。这里不需要遍历，因为尾指针已经保存了最后一个节点，这也是维护tail_的意义。

按位置插入的合法位置是[0, size]，pos == 0等价于头插，pos == size等价于尾插，中间位置要先走到pos-1个节点，令新节点的next指向prev->next，再令prev->next指向新节点。这两步的顺序同样不能反：先改prev->next，新节点就找不到原来的后继了。

用文字表示中间插入：

插入前：prev -> current
插入后：prev -> node -> current
步骤：node->next = prev->next; prev->next = node;

size_在插入成功后加一。若new抛出std::bad_alloc，链表保持原状，因为我们在分配成功后才修改指针。

三、删除：先保存，再摘除，最后释放

删头：保存head_，让head_指向head_->next，释放旧头。如果删除后size_变为 0，必须把tail_置空，否则tail_会指向已释放的节点，成为悬垂指针。

删中间或尾部：走到待删节点的前驱prev，保存victim = prev->next，令prev->next = victim->next。如果victim == tail_，说明删的是尾节点，要更新tail_ = prev。最后delete victim，size_减一。

顺序的关键是「先保存待删节点，再改指针，最后释放」。如果先delete再访问victim->next，就是释放后使用，属于未定义行为（undefined behavior, UB），可能读到垃圾值，也可能崩溃。

删除操作的合法性：pos必须小于size_。越界时返回 false，不做任何修改。空表删除直接返回 false，不要解引用空指针。

四、资源管理、常用操作与完整实现

析构要释放所有节点。从头节点开始，先用next保存后继，再delete当前节点，最后把head_、tail_置空、size_归零。不能直接delete head_了事，那样只会释放第一个节点，后面的全部泄漏。

拷贝构造不能只复制head_指针，否则两个链表共用同一批节点，任一析构都会让另一个悬垂，随后重复释放。正确做法是深拷贝：遍历源链表，对每个值调用push_back，得到一批独立节点。

拷贝赋值要处理自赋值和旧资源释放。推荐拷贝并交换（copy-and-swap）：先按值得到一个临时副本，再与*this交换三个成员，临时对象析构时释放旧链。这样既处理了自赋值，也提供了较强的异常安全保证。

移动构造直接「偷」走三个成员，并把源对象置为空表。移动赋值先释放自身资源，再接管源对象的指针。移动后源对象处于「有效但未指定」状态，本文的实现把它明确置为空表，调用方仍可安全地析构或重新赋值。

如果一个类手动管理资源，析构、拷贝构造、拷贝赋值通常要一起定义，这就是「规则三」；C++11 之后再加上移动构造与移动赋值，称为「规则五」。更好的做法是「零规则」：用std::unique_ptr或标准容器管理资源，不手写这些函数。本文手写是为了展示原理。

反转与查找

反转用三个指针：prev、cur、next。每次先用next保存cur->next，再让cur->next = prev，然后prev = cur、cur = next。循环结束时prev是新的头，head_ = prev。原来的头变成新的尾，所以进入循环前要记下tail_ = head_；空表时tail_保持空。

反转过程中不能先改cur->next再保存后继，否则会丢失剩余链表。三指针的顺序是「存后继、改指向、推进」。

查找返回指向节点值的指针，找不到返回nullptr。提供const与非const两个重载：const版本返回const int*，避免调用方通过常量链表修改元素。返回指针而不是值，是为了让调用方能区分「找到 0」和「没找到」；如果返回值类型，0会和失败混淆。

完整实现

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

class SinglyList {
public:
SinglyList() = default;

~SinglyList() {
clear();
}

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

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

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

SinglyList& operator=(SinglyList&& 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(int value) {
Node* node = new Node{value, head_};
head_ = node;
if (tail_ == nullptr) {
tail_ = node;
}
++size_;
}

void push_back(int value) {
Node* node = new Node{value, nullptr};
if (tail_ == nullptr) {
head_ = node;
tail_ = node;
} else {
tail_->next = node;
tail_ = node;
}
++size_;
}

bool insert(std::size_t pos, int value) {
if (pos > size_) return false;
if (pos == 0) {
push_front(value);
return true;
}
if (pos == size_) {
push_back(value);
return true;
}
Node* prev = head_;
for (std::size_t i = 0; i + 1 < pos; ++i) {
prev = prev->next;
}
Node* node = new Node{value, prev->next};
prev->next = node;
++size_;
return true;
}

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

int* find(int value) {
for (Node* p = head_; p != nullptr; p = p->next) {
if (p->value == value) return &p->value;
}
return nullptr;
}

const int* find(int value) const {
for (const Node* p = head_; p != nullptr; p = p->next) {
if (p->value == value) return &p->value;
}
return nullptr;
}

void reverse() {
Node* prev = nullptr;
Node* cur = head_;
tail_ = head_;
while (cur != nullptr) {
Node* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
head_ = prev;
}

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

std::size_t size() const { return size_; }
bool empty() const { return head_ == nullptr; }

void print() const {
for (const Node* p = head_; p != nullptr; p = p->next) {
std::cout << p->value << ' ';
}
std::cout << '\n';
}

private:
struct Node {
int value;
Node* next;
};

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

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

int main() {
SinglyList list;
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_front(0);
list.insert(2, 99);
list.erase(1);
list.reverse();
list.print();

SinglyList copy = list;
copy.push_back(4);
copy.print();
list.print();
return 0;
}

reverse()中tail_ = head_在循环前执行，循环后head_指向原来的尾节点，tail_指向原来的头节点，两个不变量都保持。insert的循环i + 1 < pos走到pos-1位置，pos等于 1 时循环不执行，prev就是头节点，逻辑正确。

常见坑点

1. 头插时先改head_再连后继

❌head_ = node; node->next = head_;，形成自环并丢失原链表。

✅node->next = head_; head_ = node;。

2. 删除尾节点不更新tail_

❌ 只改前驱的next并delete，tail_仍指向已释放节点。

✅if (victim == tail_) tail_ = prev;。

3. 删除唯一节点后tail_悬垂

❌ 删头后只更新head_，不管tail_。

✅size_变为 0 时把tail_置空。

4. 析构只删头节点

❌delete head_;就结束。

✅ 循环保存next再逐个删除。

5. 拷贝构造只复制指针

❌head_ = other.head_;，两个链表共享节点。

✅ 深拷贝，逐个push_back新节点。

6. 拷贝赋值不处理自赋值

❌ 先clear()再读other，当this == &other时读到已释放内容。

✅ 拷贝并交换，或先判断this != &other。

7. 反转时先改指针再保存后继

❌cur->next = prev; next = cur->next;，next拿到的是prev。

✅ 先next = cur->next;，再改cur->next。

8. 按位置插入/删除不检查边界

❌ 对空表erase(0)直接解引用head_。

✅pos >= size_时返回 false，空表不进入删除逻辑。

总结

单链表的实现可以归结为两条纪律：每次修改指针前先保存「会丢失的那一端」，每次删除或插入后检查head_、tail_、size_三个不变量。把这两条守住，头插、尾插、反转、析构就不会出现「丢链」「悬垂」「重复释放」这三类经典问题。