C++ 链表详解

什么是链表？

要想知道什么是链表，我们要知道什么是链式存储

什么是链式存储？

要想知道什么是链式存储，我们要知道什么是线性存储，什么是线性表

线性存储&线性表

通俗来说，将逻辑有序的内容实际（物理空间）也有序地存储在一起，就是线性存储，

那线性表，就是将一堆线性存储的数据，比如说我们编程经常使用的数组

type array_name[length];

线性表的存储修改等操作都是通过数学公式实现的，因此速度较快，但是必须在最开头确定长度（存储空间大小）

复杂度：

获取长度	O(1)
修改	O(1)
删除	O(n)
移动	O(n)
查找	O(1)

空间复杂度：T(n) ∈ O(n)

链式存储

既然我们已经知道了线性存储是什么，那么我们马上再来关注以下什么是链式存储

链式存储是将将逻辑有序的内容实际（物理空间）无序地存储在一起，
换句话说，链表存储的数据元素，其物理存储位置是随机的

数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构

比如说在一个抽屉里放了一些东西（数据），然后里面还有一张小纸条，告诉你，下面一个（些）数据放在哪里

struct Drawer{
    int value;
    Drawer* next;
};

当然，我们也可以在抽屉里不仅放一个数据，可以放一个收纳盒，标准的形式就是这样：

struct information {
    int data;
    // another information
};

struct node;
typedef node* n;

struct node {
    information value;
    n next;
};

我们也可以不仅只存储它的直接后继（next），再存储它的直接前驱（prev），那么就变成了一个双向链表

struct node {
    information value;
    n next, prev;
};

再设计它的存取函数

struct node {
    information value;
    n prev, next;
    int getifm()
    {
        return this->value.data;
    }
    int setifm(int x)
    {
        this->value.data = x;
    }
};

至此，我们已经设计好了一个链表节点里的所有内容

因此，链表的节点由两个部分组成

也就是数据域，和指针域，其中数据域存储数据，就是我们刚刚写的information value，而指针域存储前一个结点下一个节点等联系，也就是我们刚刚写的n prev, next。

链表

我们已经对链表有了一定的了解，下面让我们写一个专门控制链表节点的结构体，我们把它称为

链表（link list）

，很明显，我们要在这里面存储它的head（头节点）end（尾节点，爱存不存），length（长度，爱存不存，但按照我的习惯，我一般都存）：

struct linkl
{
    n head, end;
    int length;
};

也就是说，如果我们要存储一些数据，比如说{1，3，4，7，2}

数组是这样子的：

x	x+4	x+8	x+16	x+20
1	3	4	7	2

而链表可能是这样子的

NULL

在这个样例中，f就是头节点，c就是尾节点。

当然，也可以是各种各样的组合方式，其中abcde都是随机的，当然，我们也可以再弄7列存储它的prev（直接前驱），但是这样也够了。

初始化

让后让我们写一个链表最重要的函数——init初始化

int init(int l=0)
	{
		this->h = new node;
		this->e = new node;
		n p, r;
		p = this->h;
		for(int i=1; i<=l; i++)
		{
			r = new node;
			p->next = r;
			r->prev = p;
			p = r;
		}
		p->next = this->e;
		this->e->prev = p;
		this->len = l;
	}

其中l表示要初始化的长度，p为上一轮创建的节点，r是当前节点，在这一轮结束后，将p指向r，

下面我们要学的就是链表最重要的两行代码：

p->next = r;
r->prev = p;

通过这两行代码，我们可以轻松将p和r建立联系。

通过观察，不难发现初始化链表，或者说其中最重要的新建空节点的复杂度为O(n)。

分析真实下标

在这里，我们可以自己规定，头尾节点不存储数据，而节点的下标为1~length，反向下标为-1~-length，于是我们可以在写一个函数，专门用来分析下标（在之后会用到）

int real_index(int x)
	{
		if(x<0) return this->check_len()+x+1;
		else return x;
	}

获取长度

为了及时获取链表的长度，我们再写一个函数用于分析链表的长度，实现很简单，只要不断便利，看看它的后继是不是end就行了

int check_len()
	{
		n p = this->h;
		int t = 0;
		while(p->next != this->e)
		{
			t++;
			p = p->next;	
		}	
		this->len = t;
		return t;
	}

改&查（get&set）

这很简单，只要找到那个节点，然后对它进行setifm或getifm就行了

int set(int o, int i)
	{
		o = this->real_index(o);
		n p = this->h;
		for(int i=1; i<=o; i++)
		{
			p = p->next;
		}
		return p->setifm(i);
	}
int get(int o)
	{
		o = this->real_index(o);
		n p = this->h;
		for(int i=1; i<=o; i++)
		{
			p = p->next;
		}
		return p->getifm();
	}

尾部增删节点

实现的方法就是找到尾节点的前面一个节点（因为尾节点是不存数据的），然后新建或删除指定数量的节点，并让最后一次操作的节点和尾节点建立联系，以下是代码

int new_node(int l=1)
	{
		n p, r;
		p = this->e->prev;
		for(int i=1; i<=l; i++)
		{
			r = new node;
			p->next = r;
			r->prev = p;
			p = r;
		}
		p->next = this->e;
		this->e->prev = p;
		this->len += l;
	}
int del_node(int l=1)
	{
		n r;
		r = this->e;
		for(int i=1; i<=l; i++)
		{
			r = r->prev;
			delete r->next;
		}
		r->next = this->e;
		this->e->prev = r;
		this->len -= l;
	}

清空链表元素

这只要使用我们刚刚编写的del_node，即可完成

int clear_items()
	{
		this->del_node(this->check_len());
		this->len = 0;
	}

注意，为什么我们不使用简单的h->next=e, e->prev=h，是因为我们要在过程中释放节点空间，delete掉被删除的node

迭代器

为了为以后做准备，让我们来写一个iter（迭代器），如果不知道迭代器的人，可以去看stl，

在下面这篇关于实现栈和队列的文章里，我们提到了迭代器，但这种迭代器极其简单，因为我们是通过数组来实现的，而数组是一种线性存储的结构，因此迭代器只要把它设成指向数据的指针就可以了，但是现在是链表，我们要如何实现迭代器呢？（很明显，指针自增自减已经不管用了）

C++ 手动实现栈&队列_嘉定世外的JinJiayang的博客-CSDN博客

“让我们来写一个结构体吧。”

struct iter;

下面让我们来实现它存储的信息

struct iter {
	n nd;
};

你没有看错，就是这么简单，下面让我们实现它的自增自减运算符，如果不知道如何重载运算符，可以baidu/google……一下

struct iter {
	n nd;
	iter operator++()
	{
		if(this->nd->next == NULL) return *this;
		this->nd = this->nd->next;
		return *this;
	}
	iter operator++(int)
	{
		if(this->nd->next == NULL) return *this;
		iter i = *this;
		this->nd = this->nd->next;
		return i;
	}
	iter operator--()
	{
		if(this->nd->prev == NULL) return *this;
		this->nd = this->nd->prev;
		return *this;
	}
	iter operator--(int)
	{
		if(this->nd->prev == NULL) return *this;
		iter i = *this;
		this->nd = this->nd->prev;
		return i;
	}
};

然后实现一下获取node的函数

struct iter {
	n nd;
	n get()
	{
		return this->nd;
	}
};

输出函数（友元friend），这里输出了node的数据

struct iter {
	n nd;
	n get()
	{
		return this->nd;
	}
	friend ostream& operator<<(ostream& os, iter self)
	{
		os << self.get()->getifm(); 
		return os;
	}
};

与整数类型加减函数，自增/自减n位

struct iter {
	n nd;
	n get()
	{
		return this->nd;
	}
	iter operator--()
	{
		if(this->nd->prev == NULL) return *this;
		this->nd = this->nd->prev;
		return *this;
	}
	iter operator--(int)
	{
		if(this->nd->prev == NULL) return *this;
		iter i = *this;
		this->nd = this->nd->prev;
		return i;
	}
	iter operator+(int l)
	{
		iter it = *this;
		for(int i=1; i<=l; i++) it++;
		return it;
	}
	iter operator-(int l)
	{
		iter it = *this;
		for(int i=1; i<=l; i++) it--;
		return it;
	}
};

等于/不等于判断

struct iter {
	n nd;
	n get()
	{
		return this->nd;
	}
	bool operator==(const iter other)
	{
		return (this->nd) == (other.nd);
	}
	bool operator!=(const iter other)
	{
		return (this->nd) != (other.nd);
	}
};

返回该迭代器的头部（head->next）/尾部（end->prev）/真实头部（head）/真实尾部（end）

struct iter {
	n nd;
	n get()
	{
		return this->nd;
	}
	iter real_head()
	{
		iter p = *this;
		iter r = p--;
		while(p.nd != r.nd) p--, r--;
		return p;
	}
	iter real_end()
	{
		iter p = *this; 
		iter r = p++;
		while(p.nd != r.nd) p++, r++;
		iter ready;
		ready.nd = p.get();
		return ready;
	}
	iter head()
	{
		return ++this->real_head();
	}
	iter end()
	{
		return --this->real_end();
	}
};

迭代器的完整代码

struct iter {
	n nd;
	n get()
	{
		return this->nd;
	}
	friend ostream& operator<<(ostream& os, iter self)
	{
		os << self.get()->getifm(); 
		return os;
	}
	iter operator++()
	{
		if(this->nd->next == NULL) return *this;
		this->nd = this->nd->next;
		return *this;
	}
	iter operator++(int)
	{
		if(this->nd->next == NULL) return *this;
		iter i = *this;
		this->nd = this->nd->next;
		return i;
	}
	iter operator--()
	{
		if(this->nd->prev == NULL) return *this;
		this->nd = this->nd->prev;
		return *this;
	}
	iter operator--(int)
	{
		if(this->nd->prev == NULL) return *this;
		iter i = *this;
		this->nd = this->nd->prev;
		return i;
	}
	iter operator+(int l)
	{
		iter it = *this;
		for(int i=1; i<=l; i++) it++;
		return it;
	}
	iter operator-(int l)
	{
		iter it = *this;
		for(int i=1; i<=l; i++) it--;
		return it;
	}
	bool operator==(const iter other)
	{
		return (this->nd) == (other.nd);
	}
	bool operator!=(const iter other)
	{
		return (this->nd) != (other.nd);
	}
	iter real_head()
	{
		iter p = *this;
		iter r = p--;
		while(p.nd != r.nd) p--, r--;
		return p;
	}
	iter real_end()
	{
		iter p = *this; 
		iter r = p++;
		while(p.nd != r.nd) p++, r++;
		iter ready;
		ready.nd = p.get();
		return ready;
	}
	iter head()
	{
		return ++this->real_head();
	}
	iter end()
	{
		return --this->real_end();
	}
};

下面让我们在结构体linkl里写几个返回迭代器的函数

iter get_iter(int o)
	{
		o = this->real_index(o);
		n p = this->h;
		for(int i=1; i<=o; i++)
		{
			p = p->next;
		}
		iter r;
		r.nd = p;
		return r; 
	}
iter iter_real_head()
	{
		return this->get_iter(0);
	 } 
iter iter_head()
	{
		return this->get_iter(1);
	}
iter iter_end()
	{
		return this->get_iter(-1);
	}
iter iter_real_end()
	{
		return ++this->get_iter(-1);
	}

从现在起，我们想获得链表的第n个元素，就可以写成

n node_name = link_list.get_iter(n).get();

有了迭代器以后，我们之后的工作就方便多了。

任意位置增删节点

这很简单，使用我们刚刚学习的迭代器即可解决，和init函数和del_node/new_node差不多，遍历+新建/删除

int self_del_node(int i, int l=1)
	{
		i = this->real_index(i);
		iter it = this->get_iter(i);
		--it;
		iter now = it+l;
		++now;
		n begin = it.get(), end = now.get();
		begin->next = end;
		end->prev = begin;
		this->len -= l;
	}
int self_new_node(int i, int l=1)
	{
		i = this->real_index(i);
		n f = this->get_iter(i).get();
		n r, p=f;
		n nextf = f->next;
		for(int i=1; i<=l; i++)
		{
			r = new node;
			p->next = r;
			r->prev = p;
			p = r;
		}
		p->next = nextf;
		nextf->prev = p; 
		this->len += l;
	}

I/O操作

为了方便我们进行debug，我们可以写一些专门用来输入输出的函数，即IO函数，代码很简单

void print(string sep=" ", string end="\n")
	{
		n p = this->h;
		int i;
		for(i=1; p->next != this->e; i++)
		{
			p = p->next;
			cout << p->getifm() << sep;
		}
		cout << end;
		this->len = i-1;
	}
	void reversed_print(string sep=" ", string end="\n")
	{
		n p = this->e;
		int i;
		for(i=1; p->prev != this->h; i++)
		{
			p = p->prev;
			cout << p->getifm() << sep;
		}
		cout << end;
		this->len = i-1;
	}
	string to_string(string sep=" ", string end="\n")
	{
		string result;
		n p = this->h;
		int i;
		for(i=1; p->next != this->e; i++)
		{
			p = p->next;
			result += to_string(p->getifm()) + sep;
		}
		result += end;
		this->len = i-1;
		return result;
	}
	void known_read(int t)
	{
		iter start = this->iter_end();
		this->new_node(t);
		for(int i=1; i<=t; i++)
		{
			start++;
			int v;
			cin >> v;
			start.get()->setifm(v);
		}
		start.get()->next = this->e;
	}
	int read()
	{
		this->init(0);
		int t;
		cin >> t;
		this->known_read(t);
		return 0;
	}
	int write()
	{
		this->print();
		return 0;
	}

数据填充

这个函数的目的是让链表的所有元素都填充为指定数据，实现方法就是遍历一个个节点，然后修改数据就行了

int fill(int i, int from=1, int end=-1)
	{
		from = this->real_index(from);
		end = this->real_index(end);
		iter first = this->get_iter(from-1);
		for(int j=from; j<=end; j++)
		{
			++first;	
			first.get()->setifm(i);
		}
	}

数据置空（数据初始化）

这个和我们之前学习的clear_items不一样这个是把数据初始化为-1，也就是fill为-1，代码只有三行

int clear()
	{
		this->fill(-1);
	}

就是用了我们刚刚写的fill函数，没什么很难的地方，很容易理解。

数据交换

swap函数的实现就是找到两个节点，然后如何交换就像交换两个变量一样

int a, b;
int swap(int* a, int* b)
{
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

那么代码如下

int swap(int i1, int i2)
	{
		n n1 = this->get_iter(i1).get();
		n n2 = this->get_iter(i2).get();
		int tmp;
		tmp = n1->getifm();
		n1->setifm(n2->getifm());
		n2->setifm(tmp);
	}

链表复制

如果我将链表直接复制另一个链表中，如下面的代码的话，

linkl l;
linkl l2;
l2 = l;

但是l2的数据如果改动，l1的数据也会改动，因此是一种浅拷贝，这显然达不到我们想要的结果，因为我们希望的是l2的数据和l的数据是没有关联的，那么我们就要自己实现一个copy函数，一个深拷贝函数

那么怎么实现呢？

其实很简单，我们只要把init函数拿过来，做一些小改动就可以了，比如说在new节点的时候赋this对象的值，下面给出了代码：

linkl copy()
	{
		linkl result;
		n noden = this->h;
		result.h = new node;
		n nn, pnn=result.h;
		while(this->e != noden)
		{
			noden = noden->next;
			n nnn = new node;
			nnn->k = noden->k;
			nnn->ifm = noden->ifm;
			pnn->next = nnn;
			nnn->prev = pnn; 
			pnn = nnn;
		}
		result.e = pnn;
		result.len = this->len;
		return result;
	}

拷贝列表部分

这个也可以使用链表复制的思路，但是就没有锻炼思维的意义了，因此我们换一种思路，使用我们的迭代器，方法如下：

1.新建链表result，并申请空间；

2.声明两个迭代器，分别赋值为result的head和this的head；

3.持续赋值，然后迭代器自增，直到结束。

linkl get_part(int from=1, int end=-1)
	{
		linkl listt = this->copy();
		from = listt.real_index(from);
		end = listt.real_index(end);
		int sub = end-from;
		linkl result;
		result.init(sub+1);
		iter a = listt.get_iter(from);
		iter b = result.get_iter(1);
		for(int i=1; i<=sub+1; ++i, ++a, ++b)
			b.get()->setifm(a.get()->getifm());
		result.len = sub+1;
		return result;
	}

链表合并

链表合并是比较简单的，只要找到另一个链表的头节点和尾节点，运用我们最开始学到的知识，将另一个链表的头节点和尾节点与要衔接的节点连接，合并就完成了。当然如果你不想浅拷贝，只需要在函数的开头加上copy函数就行了。

int merge(linkl other, int o=-1)
	{
		other = other.copy();
		n noden = this->get_iter(o).get();
		n nnoden = noden->next;
		iter noth = other.iter_head();
		noden->next = noth.get();
		noth.get()->prev = noden;
		noth = noth.end();
		noth.get()->next = nnoden, nnoden->prev = noth.get();
		this->len += other.len; 
	}

链表高级操作（统计/查找）

这个的实现和普通数组是一样的，只是下标变成了迭代器而已

统计：

int count(int v)
	{
		int r = 0;
		iter n = this->iter_real_head();
		iter e = this->iter_real_end();
		while(n.get()->next != e.get())
		{
			++n;
			if(n.get()->getifm() == v) r++; 
		 } 
		return r;
	}

如果是数组，那么代码是：

int count(int v)
{
	int result = 0;
	for(int i=1; i<=length; i++)
	{
		if(value[i] == v) result++;
	}
	return result;
}

查找：

int find(int v)
	{
		iter n = this->iter_real_head();
		iter e = this->iter_real_end();
		int i = 0;
		while(n.get()->next != e.get())
		{
			++i, ++n;
			if(n.get()->getifm() == v) return i; 
		 } 
		return -1;
	 }