1 链表的概念

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只 需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。

⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？

最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。

在链表⾥，每节“⻋厢”是什么样的呢？

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点”节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。

图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希 望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。 

为什么还需要指针变量来保存下⼀个节点的位置？

链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针 变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：

假设当前保存的节点为整型

struct SListNode
{
 int data; //节点数据 
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数 据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。

当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个 节点的钥匙）就可以了。

给定的链表结构中，如何实现节点从头到尾的打印？

 先打印第一个节点中的数据，即pcur结构体的data成员，pcur结构体的next指针指向下一个节点（pcur结构体的next指针保存着下一个节点的地址）。我们把这个地址重新赋值给pcur，此时pcur就指向了第二个节点。循环这一过程，直到pcur指向空指针时跳出循环。这样就实现了链表的遍历。

2单链表的实现

2.1开辟新节点

ListNode* NewListNote(DataType x)
{
	ListNode* newlistnode = (ListNode*)malloc(sizeof(ListNode));
	if (newlistnode == NULL)
	{
		perror("malloc error");
		exit(1);
	}
	newlistnode->data = x;
	newlistnode->next = NULL;
	return newlistnode;
}

我们对链表进行插入操作时，需要像内存申请一个节点大小的空间，这里我们用到了malloc函数。

申请新空间并且为结构体的成员赋值。

2.2尾插

在链表的尾部插入一个新节点

void LiseTailAdd(ListNode** pphead, DataType x)
{
	assert(pphead);
	ListNode* newlistnode = NewListNote(x);
	if (*pphead == NULL)
	{
		*pphead = newlistnode;
	}
	else
	{
		ListNode* ptail = *pphead;
		while ((ptail)->next != NULL)
		{
			ptail = (ptail)->next;
		}
		(ptail)->next = newlistnode;
	}
}

如果链表中一个节点都没有，就直接插入一个新节点，新节点作为链表的“头节点”。

如果链表中原来就有节点，那我们应该先找到尾节点，然后在尾节点后边插入新节点。

这里为什么传入二级指针呢？

因为链表的头节点的地址可能会因为新节点的插入而发生改变（原链表中一个节点都没有视情况下）。想要头节点的地址发生改变，就必须传二级指针。即函数的传址调用。

2.3头插

在链表的头部插入一个新节点

void LiseHeadAdd(ListNode** pphead, DataType x)
{
	assert(pphead);
	ListNode* newlistnode = NewListNote(x);
	newlistnode->next = *pphead;
	*pphead = newlistnode;
}

建一个新节点，再让新节点的next指针指向头节点，然后让这个新节点作为链表的“头节点”。

2.4头删

删除链表的“头节点”

void LiseHeadDel(ListNode** pphead)
{
	assert(pphead);
	ListNode* tmp = (*pphead)->next;
	free(*pphead);
	*pphead = tmp;
}

直接释放头节点，让它的下一个节点作为链表的新的头节点，但是直接free头节点后，我们就找不到了它的下一个节点，所以要在释放之前用一个变量tmp把他下一个节点的地址保存下来。再让*pphead指向tmp。

2.5尾删

删除链表的尾节点

void LiseTailDel(ListNode** pphead)
{
	assert(pphead);
	ListNode* per = *pphead;
	ListNode* ptail = *pphead;
	while (ptail->next)
	{
		per = ptail;
		ptail = ptail->next;
	}
	per->next = NULL;
	//free(ptail);
	//ptail = NULL;
}

要删除尾节点，我们应该把尾节点释放掉，并且让为节点的前一个节点的next指针指向空。所以我们要先找到尾节点和尾节点的前一个节点。找尾节点的方法和尾插找尾的方法类似。找到尾后释放即可。

2.6查找数据

ListNode* FindNote(ListNode* phead, DataType x)
{
	while (phead)
	{
		if (phead->data == x)
		{
			printf("找到了\n");
			return phead;
		}
		phead = phead->next;
	}
	printf("没找到");
}

遍历链表，查找某个数据是否存在，如果存在就返回对应节点的地址。不存在的话就打印没找到。

2.7在指定位置之前插入

void PopNoteFrontAdd(ListNode** pphead, ListNode* pop, DataType x)
{
	assert(pphead);
	if (*pphead == pop)
	{
		LiseHeadAdd(pphead, x);
	}
	else
	{
		ListNode* per = *pphead;
		while (per->next != pop)
		{
			per = per->next;
		}
		ListNode* newlistnode = NewListNote(x);
		newlistnode->next = pop;
		per->next = newlistnode;
	}
}

 在指定位置之前插入，我们需要找到这个位置之前的节点，让这个节点的next指针指向新节点，然后新节点的next指针在指向pop。

所以要遍历链表，通过头节点找到这个位置之前的节点。

2.8在指定位置之后插入

void PopNoteBehindAdd(ListNode* pop, DataType x)
{
	ListNode* newlistnode = NewListNote(x);
	newlistnode->next = pop->next;
	pop->next = newlistnode;
}

在指定位置之后插入，只需要让新节点的next指针指向pop的next节点，再让pop的next指针指向新节点。

注意这两条指令的顺序不能颠倒，因为如果先让pop的next指针先发生改变，就找无法找到原来的pop的next节点。

2.9删除pop之后位置节点

void DelPopBehindNode(ListNode* pop)
{
	assert(pop && pop->next);
    ListNode* tmp = pop->next；
	pop->next = tmp->next;
    free(tmp);
    tmp = NULL;
}

释放pop之后位置的节点，但释放之后无法找到这个位置的下一个节点，所以释放之前要用变量tmp把pop->next先存起来。

2.10删除pop位置的节点

void DelPopNode(ListNode* pop, ListNode** pphead)
{
	assert(pphead);
	if (pop == *pphead)
	{
		LiseHeadDel(pphead);
	}
	else
	{
		ListNode* per = *pphead;
		while (per->next != pop)
		{
			per = per->next;
		}
		per->next = pop->next;
		free(pop);
		pop = NULL;
	}
}

如果pop是头节点，直接调用头删函数。

如果pop不是头节点，那应该找到pop的前一个结点，并让其next指针指向pop的下一个节点，最后释放pop节点。

2.11链表销毁

void SListDesTroy(ListNode** pphead)
{
	assert(pphead && *pphead);
	while (*pphead != NULL)
	{
		ListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

遍历链表，逐个节点释放。但是直接释放的话会找不到下一个节点，所以要有一个变量next将下一个节点的地址存起来。