数据结构.单链表

啊，哈喽，小伙伴们大家好。我是#张亿，今天呐，学的是数据结构.单链表

1. 定义

采用链式存储的线性表被称为链表。

这个定义非常的冷冰冰，只能通过后面更多的讲解来帮助理解和加深认识了。

2. 链表的常见操作

2.1 初始化

班主任陈老师把班里同学排成一列。这一次，陈老师决定做一些创新，他只记录了第一位的同学是谁，以及每一位同学后面站的是谁。那么用 c++ 程序来表达这个记录方式，是这样的

int n,id[101],head,next[i],tmp;
string name[101];
cin>>n;
cin<<name[1]<<id[1]; //记下排第一位的是谁
head = 1; //头部是数组元素 1
for(int i=2;i<=n;i++)
{
    cin>>name[i]>>id[i];
    next[i-1] = i; // 让上一位同学指向这位同学
}

2.2 间接访问

链表是不支持直接访问的。比方说，黄级长想知道队伍里面排第 5 的同学是谁，是不能认为 name[5] 和 id[5] 就是答案。因为，这个队伍加入是动态变化的，随着若干次的删除和插入操作之后，之前的第 5 个就可能不是真的第 5 个了。正确的做法是

int tmp=head; //从链头开始找
for(int cnt=1;cnt<5;cnt++)
{
    if(next[tmp])
    {
        tmp = next[tmp]; // 根据上一个人找下一个人，相当于跳转
        if(cnt==4) //跳转了 4 次，找到了
            cout<<"找到了，第 5 个人是 "<<name[tmp]<<" "<<id[tmp]<<endl;
    }
    else
    {
        printf("错误，这个队伍就不够 5 个人\n")；
        break;
    }
}

2.3 查找

如果黄级长想知道是否有 张鹏 这个同学，也需要访问整条链（如果早早找到，就提前结束，最坏的情况是找不到，则整条链都探寻了一次）。

int tmp=head; //从链头开始找
bool Found=false;
int cnt=1;
while(tmp)
{
    if(name[tmp]=="张鹏")
    {
        printf("张鹏找到了，他排在队伍的第 %d 个。\n",cnt);
        Found = true;
        break;
    }
    else
    {
        cnt++;
        tmp = next[tmp]; // 链的跳转
    }
}
if(!Found) printf("张鹏没找到\n");

2.4 中间插入

假设新来了个 张亮 ，要插入到 黄宏 的后面，这时候不需要挪动很多人的位置。我们只需要让 张亮 指向 黄宏 之前后面的那个人，然后让 黄宏 指向张亮即可。

 
// 记录 张亮 的信息，把姓名和学号存放到 name 和 id 数组
n++;
cin>>name[n]>>id[n];
int tmp=head; //从链头开始找
while(tmp)
{
    if(name[tmp]=="黄宏")
    {
        next[n] = next[tmp];  // 让 张亮 记住 现在 黄宏 后面的人是谁，这人将来就是张亮后面的人
        next[tmp] = n; // 张亮 称为 黄宏 后面的人
        break;
    }
}

2.5 头插入

头插入是最常用的插入模式。只需要让新的元素指向之前的头，然后让新元素称为新的头即可。

// 在数组尾部记录新的元素
n++; 
cin>>name[n]>>id[n];
next[n] = head; //让新的元素指向原来的头
head = n; // 让新的元素称为头

2.6 删除

假设 叶超 有事先走，我们要删除叶超，也不需要挪动后面的数据。只需要让叶超前面的人指向叶超后面的人即可。

if(name[head]=="叶超")
{
    //叶超就是 队头
    head = next[head];
}
else
{
    int tmp=head; //从链头开始找
    bool Found=false;
    int cnt=1;
    while(1) //假设一定有叶超，这里可以设无条件循环，跳出条件放在循环内
    {
        if(name[next[tmp]]=="叶超") // tmp 就是 叶超 前面的人
        {
            //tmp 是叶超前面的人， next[tmp] 是 叶超， next[next[tmp]] 就是叶超后面的人
            next[tmp] = next[next[tmp]];  // 叶超前面的人指向 叶超 后面的人
            break;
        }
    }
}

2.7 快慢指针

求链表倒数第 k 个元素
可以设置两个指针 快指针 fast 和 慢指针 slow ，让 fast 去指向第 k+1 个元素，然后让 slow 指向链表的头（fast 比 slow 领先 k 个元素），然后，让 fast 和 slow 同步向后移动，当 fast 到达链表的尾巴的时候，slow 指向了倒数第 k 个元素。理解这个问题的关键点是同步移动。

int fast=head,slow=head; //从链头开始找
 
//让 fast 指针指向 第 k+1 个元素 
for(int i=1;i<=k;i++)
	fast=next[fast];
 
while(fast)
{
	//fast,slow 同步移动，fast 总是 领先 slow k 个元素 
	fast=next[fast];
	slow=next[slow];
}
//退出循环的时候 ,fast 指向尾巴后的空元素，slow 指向倒数第 k 个元素 

假设链表中有奇数个元素，如何找到中间项呢？一个简单的办法是设置两个指针，一个快指针，一次跳动 2 个元素，一个慢指针，一次跳动 1 个元素。然后他们同时从链头出发往后移动，当快指针到达链尾的时候，慢指针指向链表的中间项。

int fast=head,low=head; //从链头开始找
while(next[fast])
{
	//fast,slow 同步移动，fast 总是比 slow 快一倍 
	fast=next[next[fast]];  // fast 一次跳 2 格 
	slow=next[slow];  //slow 一次跳 1 格 
}
//退出循环的时候 ,fast 在尾巴元素 ,slow 在中间元素 

3. 基于结构体的代码模板

上面的内容，可以基于结构体的方式加以实现。基于结构体实现是容易理解的，但是考试的时候，程序阅读题往往不是基于结构体来写的，所以，掌握原理很重要，掌握了原理，可以应对千变万化。

struct Stu
{
	int next,id;
	string name;
}x[1001];
int n,head;
void init() //初始化，确定链头，把链组织起来。
{
	cin>>n;
	for(int i=1;i<=n;i++)
	    cin>>x[i].name>>x[i].id;
	head = 1; //头部是数组元素 1
	for(int i=2;i<=n;i++)
	    x[i-1].next = i; // 让上一位同学指向这位同学	
}
stu query(int cnt) // 查找队伍中第 cnt 个人，返回他的信息
{
	int tmp=head; //从链头开始找
	for(int i=1;i<cnt;i++)
	{
	    if(!tmp) // 已经到了链的尾巴了，表示没找到 
	    {
	        printf("错误，这个队伍就不够 %d 个人\n",cnt);
			Stu ret;
			ret.id=-1;
	        return ret;  //返回一个很特别的值，表示找不到
	    }
 
		if(i==cnt) //跳转了 4 次，找到了
			return x[tmp];
 
        tmp = x[tmp].next; // 根据上一个人找下一个人，相当于跳转
	}
}
int Search(string Name) //查找有没有人叫 Name，如果找到返回他的数组下标 ，找不到返回 -1 
{
	int tmp=head; //从链头开始找
	while(tmp)
	{
	    if(x[tmp].name==Name)
	    {
	    	// 找到，返回他的下标 
	    	return tmp;
	    }
		tmp = x[tmp].next;
	}
	printf("错误，这个队伍没有这个人\n");
	return -1; // -1 是特殊值，表示没扎到 
}
void Insert(int new_id, string new_name)  // 在头部插入，头部插入是链表的常用插入方法 
{
	n++;
	x[n].name=new_name;
	x[n].id=new_id;
	x[n].next=head;  //让新元素指向之前的链头
	head = n; // 让新元素称为新的链头
}
void Delete(string Name) //删除姓名为 Name 的人
{
	if(x[head].name==Name)
		head = x[head].next; //删除链头，让链头指向的人称为链头
	else
	{
		int tmp = head;
		while(tmp)
		{
			if(x[x[tmp].next].name==Name) // tmp 指向的人为 Name
			{
				// tmp 是 Name 的上一个 , x[tmp].next 是 Name， x[x[tmp].next].next 是 Name 的下一个
				x[tmp].next = x[x[tmp].next].next; // 让 Name 前面的人指向 Name 后面的人
				return;
			}
			tmp = x[tmp].next;
		}
	}
}

4. 循环链表

当链表的尾巴指向链表的头，链表就会形成一个环，称为循环链表

5. 链表的特点

链表改善了线性表中数据插入和数据删除的性能问题，避免了数据的挪动，但是链表在数据查找时仍然效率低下，而且链表不支持直接访问

PS: 上述的时间复杂度描述中，数据的删除、插入 操作不包括先找到数据位置（删除哪一个数据，插入数据到什么位置）。