C++ 手搓单链表（附源码）

总述

周知众所，要存储一堆数据，一般采取顺序表的方式，也就是C++中的数组，大家应该十分熟悉。但是，数组长度固定，realloc也浪费内存。所以，一种叫链表（linked list）的东东应运而生。这玩意长这样：

链表可以分为单向链表、双向链表，而其中每一种都分循环与否。今天做的是不循环的单链表。

虽说STL里早就有了，也肯定比我做得好，但自己做一遍，加深学习。

实现

环境：VS2022Preview/std:c++20

注：本文实现链表未使用哑头（即数据块为空的第一个节点）。

节点

节点node一般使用结构体，在其中添加数据块data和指向后继节点的指针next。以示区分，命名节点为single_node。为了适应多种数据类型，我们可以使用类模板。

template <typename T>
struct single_node {
public:
	T data;
	single_node<T>* next;
};

方法

单链表中，我们主要来实现这样几种方法：

push();       //插入
front_push(); //头插法
rear_push();  //尾插法
pop();        //删除
front_pop();  //头删法
rear_pop();   //尾删法
empty();      //判断是否为空
clear();      //清空
size();       //获取元素个数
front();      //获取首元素
rear();       //获取尾元素

当然，还包括构造函数和析构函数。 

size()

先从最简单的size()开始。网上普遍是遍历累加，但是我想采用维护大小变量的方式。这在后面也能简化empty()方法。这个变量就取名为s吧。那么，在构造函数中，就要初始化；在插入与删除时，就得改变s的值。在size()中，直接返回s就可以了。由于这个函数过于简单，可以声明为inline和noexcept。改动部分：

single_linked_list() {
	s = 0;
}
T push(T last, T data) {
	s++;
}
T front_push(T data) {
	s++;
}
T rear_push(T data) {
	s++;
}
T pop(T last) {
	s--;
}
T front_pop() {
	s--;
}
T rear_pop() {
	s--;
}
inline int size() noexcept {
	return s;
}
private:
	int s;

empty()

这个方法超级简单，只消判断s是否为0就可以了，因此也加上inline和noexcept。

inline bool empty() noexcept {
	return !s;
}

front()和rear()

维护一个指针f，保持指向首元素。但是，front()方法的返回值不应该是一个node对象，而是node中的data。rear()相似，以r作为尾指针。f与r都需要在构造函数中初始化为nullptr。同时，这两个函数都非常简单，修饰为inline。但是，可能出现链表为空的情况，因此增加条件判断，若链表为空，则返回0。万无一失，noexcept。

inline T front() noexcept {
	if (!s)
		return 0;
	return f->data;
}
inline T rear() noexcept {
	if (!s)
		return 0;
	return r->data;
}

而这是现在的构造函数： 

single_linked_list() noexcept {
    s = 0;
    f = r = nullptr;
}

private里也加上

single_node<T>* f, * r;

push() 

这个方法由调用者传入两个T类型的参数，把第二个添加在第一个之后。那么，我们需要先创建一个工作指针p，遍历查找第一个参数，以确定插入位置。接着，创建一个新节点，node赋值为传入的第二个参数，next就等于p->next。最后，使p->next指向新节点。这里，我们认为调用者会对传入的参数负责。

想了一想，还漏了特殊情况。要是查找到的节点是尾节点怎么办？增加处理特殊情况的代码后，函数长这样：

T push(T data, T last) {
	single_node<T>* p = f;
	while (p->data != last)
		p = p->next;
	single_node<T>* n = new single_node<T>;
	n->data = data;
	n->next = p->next;
	p->next = n;
	if (r == p)
		r = n;
	s++;
	return data;
}

front_push()

这个函数与上面的相仿，只是把p->next换做f，同时又增加了一种特殊情况：链表可能为空。如果r == nullptr，那么就把r也赋值为新节点的地址。

T front_push(T data) {
	single_node<T>* n = new single_node<T>;
	n->data = data;
	n->next = f;
	f = n;
	if (r == nullptr)
		r = n;
	s++;
	return data;
}

rear_push()

刚刚特殊情况都处理过了，这个方法就可以依葫芦画瓢地写了，此处不多赘述。

T rear_push(T data) {
	single_node<T>* n = new single_node<T>;
	n->data = data;
	n->next = nullptr;
	if (r == nullptr)
		f = n;
	else
		r->next = n;
	r = n;
	s++;
	return data;
}

pop() 

要实现从链表中删除节点，就要先查找到要删除的节点。这个创建指针d，遍历一下就可以了。然后，d的前一个节点的next应该指向d->next，然后释放d的内存。但是，还是有漏洞。如果调用者传的是头节点的data，有人可能会说，要是调用者给的data不存在呢？我还是认为，检查正确性应该是调用者的事。你们支不支持呢？去文末投个票吧！也欢迎在评论区发表自己的见解！

T pop(T data) noexcept {
	single_node<T>* d = f;
	single_node<T>* last = nullptr;
	while (d->data != data) {
		last = d;
		d = d->next;
	}
	if (last == nullptr)
		f = d->next;
    else
        last->next = d->next;
	delete d;
	s--;
	return data;
}

突然想到一个问题：万一有多个节点的data相同怎么办？于是，我重载了pop()方法，加了一个这样的：

T pop(T data, unsigned int num) noexcept {
	single_node<T>* d = f;
	single_node<T>* last = nullptr;
	while (d->data != data) {
		last = d;
		d = d->next;
	}
	for (unsigned int i = 1; i < num; i++) {
		last = d;
		d = d->next;
		while (d->data != data) {
			last = d;
			d = d->next;
		}
	}
	if (last == nullptr)
		f = d->next;
	else
		last->next = d->next;
	delete d;
	s--;
	return data;
}

很显然，只是copy下来，多查找几遍，其余没有任何改变。

front_pop()

删掉头节点，就是把pop()方法中last->next换成f,，还省下了查找，不要太好写！但是还有一个特殊情况，就是删完变成了空链表，检查一下size的值就可以解决。突然想到“代码复用”这回事，于是决定复用pop()方法，把头节点的data传给pop()，再返回pop()的返回值。由于pop()是noexcept，所以front_pop()也是。就像这样：

T front_pop() noexcept {
	return pop(f->data);
}

复用代码，可以有效地偷懒减少代码量并减少工作量，提高效率以省下摸鱼时间。

rear_pop()

删掉尾节点不能再复用pop()方法了，因为我们无法保证r->data一定是第一次出现。因此，我们需要先找到r前面一个节点，删掉尾节点，那么r前面那个节点就成为了新的尾节点，因此置空它的next。但是，删完了变成空链表了怎么办？那就得置空f与r。

T rear_pop() noexcept {
	T data = r->data;
	single_node<T>* last = f;
	if (s == 1) {
		delete r;
		f = r = nullptr;
	}
	else {
		while (last->next != r)
			last = last->next;
		last->next = nullptr;
	}
	delete r;
	r = last;
	s--;
	return data;
}

clear() 

简而言之，不停pop直到链表为空。

void clear() {
	while (s)
		front_pop();
}

构造函数

无参的构造函数其实已经在前面写好了，这里再单独拎出来看一下：

single_linked_list() {
	s = 0;
	f = r = nullptr;
}

再加一个拷贝的：

single_linked_list(single_linked_list<T>& another) {
	s = another.s;
	f = another.f;
	r = another.r;
}

析构函数

析构函数负责释放所有空间，一个clear()就搞定。又一个代码复用的例子！

~single_linked_list() {
	clear();
}

测试与调试

改进一：加上迭代器

写测试代码时，我发现少了一个迭代器iterator。这非常不方便。于是我写了一个：

template <typename T>
class iterator {
	friend iterator<T> single_linked_list::begin() noexcept;
	friend iterator<T> single_linked_list::end() noexcept;
public:
	iterator(single_node<T>* begin) noexcept{
		i = begin;
	}
	iterator& operator++() {
		iterator iter(i);
		i = i->next;
		return iter;
	}
	const iterator& operator++(int) noexcept {
		i = i->next;
		return *this;
	}
	T operator*() noexcept {
		return i->data;
	}
	bool operator==(iterator the_other) noexcept {
		return this->i == the_other.i;
	}
	bool operator!=(iterator the_other) noexcept {
		return this->i != the_other.i;
	}
private:
	single_node<T>* i;
};

附赠begin()&end()： 

iterator<T> begin() noexcept {
	iterator begin(f);
	return begin;
}
iterator<T> end() noexcept {
	iterator end(r);
	end.i = nullptr;
	return end;
}

改进二：新的push()

T push(T data, T last, unsigned int num) {
	single_node<T>* p = f;
	while (p->data != last)
		p = p->next;
	for (unsigned int i = 1; i < num; i++) {
		p = p->next;
		while (p->data != last)
			p = p->next;
	}
	single_node<T>* n = new single_node<T>;
	n->data = data;
	n->next = p->next;
	p->next = n;
	if (r == p)
		r = n;
	s++;
	return data;
}

受到重载pop()的启发，想到push时也会有多个相同数据，于是又写了一个push()来弥补。思路都在第二个pop()与push()里，这里不讲了。

测试

测试代码：

#include <cstdio>
#include "linked_list.h"

int main() {
	single_linked_list<int> test;
	for (single_linked_list<int>::iterator<int> i = test.begin(); i != test.end(); i++)
		std::printf("%d", *i);
	std::printf("\n");
	std::printf("%d\n", test.front());
	std::printf("%d\n", test.rear());
	test.clear();
	test.front_push(2);
	test.rear_push(4);
	test.push(3, 2, 1);
	std::printf("%d\n", test.front_push(1));
	std::printf("%d\n", test.rear_push(5));
	std::printf("%d\n", test.push(6, 5));
	for (single_linked_list<int>::iterator<int> i = test.begin(); i != test.end(); i++)
		std::printf("%d", *i);
	std::printf("\n");
	std::printf("%d\n", test.pop(4));
	std::printf("%d\n", test.front_pop());
	std::printf("%d\n", test.rear_pop());
	std::printf("%d\n", test.pop(2, 1));
	for (single_linked_list<int>::iterator<int> i = test.begin(); i != test.end(); i++)
		std::printf("%d", *i);
	std::printf("\n");
	test.clear();
	test.front_push(7);
	for (single_linked_list<int>::iterator<int> i = test.begin(); i != test.end(); i++)
		std::printf("%d", *i);
	std::printf("\n");
	return 0;
}

预期结果：

（空）
0
0
1
5
6
123456
4
1
6
2
35
7

 实际结果：

成品

#pragma once

template <typename T>
struct single_node {
public:
	T data;
	single_node<T>* next;
};

template <typename T>
class single_linked_list {
public:
	single_linked_list() noexcept {
		s = 0;
		f = r = nullptr;
	}
	single_linked_list(single_linked_list<T>& another) {
		s = another.s;
		f = another.f;
		r = another.r;
	}
	~single_linked_list() {
		clear();
	}
	T push(T data, T last) {
		single_node<T>* p = f;
		while (p->data != last)
			p = p->next;
		single_node<T>* n = new single_node<T>;
		n->data = data;
		n->next = p->next;
		p->next = n;
		if (r == p)
			r = n;
		s++;
		return data;
	}
	T push(T data, T last, unsigned int num) {
		single_node<T>* p = f;
		while (p->data != last)
			p = p->next;
		for (unsigned int i = 1; i < num; i++) {
			p = p->next;
			while (p->data != last)
				p = p->next;
		}
		single_node<T>* n = new single_node<T>;
		n->data = data;
		n->next = p->next;
		p->next = n;
		if (r == p)
			r = n;
		s++;
		return data;
	}
	T front_push(T data) {
		single_node<T>* n = new single_node<T>;
		n->data = data;
		n->next = f;
		f = n;
		if (r == nullptr)
			r = n;
		s++;
		return data;
	}
	T rear_push(T data) {
		single_node<T>* n = new single_node<T>;
		n->data = data;
		n->next = nullptr;
		if (r == nullptr)
			f = n;
		else
			r->next = n;
		r = n;
		s++;
		return data;
	}
	T pop(T data) noexcept {
		single_node<T>* d = f;
		single_node<T>* last = nullptr;
		while (d->data != data) {
			last = d;
			d = d->next;
		}
		if (last == nullptr)
			f = d->next;
		else
			last->next = d->next;
		delete d;
		s--;
		return data;
	}
	T pop(T data, unsigned int num) noexcept {
		single_node<T>* d = f;
		single_node<T>* last = nullptr;
		while (d->data != data) {
			last = d;
			d = d->next;
		}
		for (unsigned int i = 1; i < num; i++) {
			last = d;
			d = d->next;
			while (d->data != data) {
				last = d;
				d = d->next;
			}
		}
		if (last == nullptr)
			f = d->next;
		else
			last->next = d->next;
		delete d;
		s--;
		return data;
	}
	T front_pop() noexcept {
		return pop(f->data);
	}
	T rear_pop() noexcept {
		T data = r->data;
		single_node<T>* last = f;
		if (s == 1) {
			delete r;
			f = r = nullptr;
		}
		else {
			while (last->next != r)
				last = last->next;
			last->next = nullptr;
		}
		delete r;
		r = last;
		s--;
		return data;
	}
	inline bool empty() noexcept {
		return !s;
	}
	inline void clear() noexcept{
		while (s)
			front_pop();
	}
	inline int size() noexcept {
		return s;
	}
	inline T front() noexcept {
		if (!s)
			return 0;
		return f->data;
	}
	inline T rear() noexcept {
		if (!s)
			return 0;
		return r->data;
	}
	template <typename T>
	class iterator {
		friend iterator<T> single_linked_list::begin() noexcept;
		friend iterator<T> single_linked_list::end() noexcept;
	public:
		iterator(single_node<T>* begin) noexcept{
			i = begin;
		}
		iterator<T>& operator++() {
			iterator<T> iter(i);
			i = i->next;
			return iter;
		}
		const iterator<T>& operator++(int) noexcept {
			i = i->next;
			return *this;
		}
		T operator*() noexcept {
			return i->data;
		}
		bool operator==(iterator<T> the_other) noexcept {
			return this->i == the_other.i;
		}
		bool operator!=(iterator<T> the_other) noexcept {
			return this->i != the_other.i;
		}
	private:
		single_node<T>* i;
	};
	iterator<T> begin() noexcept {
		iterator<T> begin(f);
		return begin;
	}
	iterator<T> end() noexcept {
		iterator<T> end(r);
		end.i = nullptr;
		return end;
	}
private:
	unsigned int s;
	single_node<T>* f, * r;
};

在单链表的测试与调试过程中，遇到了<cstdio>莫名其妙报错的问题，参考了CSDN博客

《头文件包含顺序不当引起错误》                                                               ——走啊走已存在

原文链接：                      头文件包含顺序不当引起错误_头文件顺序导致编译失败-CSDN博客 

在头文件的最后编排过程中，遇到了需要在不同头文件中声明友元的问题，参考了CSDN博客

《关于友元声明的注意事项和头文件声明的规范》                                        ——码农力量大 

原文链接：关于友元声明的注意事项和头文件声明的规范_c++友元类声明需要引用头文件吗-CSDN博客

图片素材来源网络，侵权联系删除！