顺序表的缺陷

学了顺序表后我们会发现它有很多不方便的地方，也可以说是缺陷。

1、顺序表在进行头插或者中间位置插入时，需要挪动数据，此时的时间复杂度为O(N), 增加运行时间以及损耗。

2、顺序表在增容时有一定的消耗：申请空间、拷贝数据、释放空间。

3、增容可能造成一定的空间浪费（开辟100个字节空间，还需5个，这时又开辟了100个空间，造成浪费）。

链表的结构

为了解决上述问题，就有了链表的概念。

链表就像是用链条一样将一个个结构体串联起来，不需要增容，插入数据也不需要挪动，在很多地方较好的解决了顺序表的问题。

链表有8种结构：

 

 今天我们先从最基础的单链表讲起。

单链表

链表是依存结构体实现的一种数据结构，因此我们先在头文件中创建一个结构体。

typedef int SLTDataType;
 
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

单链表是一种非常简单的结构，因此可以不需要初始化，直接设定一个结构体头指针指向空就行了，这也叫空单链表。

	SLTNode* plist = NULL;

单链表的销毁

虽然不用初始化，但是在使用完后需要销毁。

void SListDestory(SLTNode* phead)//？？？？？
{
    
}

这里注意一点：

一：传参的时候传的是 plist 还是 &plist，接收的时候是用一级指针*phead还是二级指针 *pphead

一：应该传的是地址&plist，接收要用二级指针*pphead，因为plist的类型是SLTNode*类型的，是结构体指针，如果传plist本身，在函数使用改变的是在函数内的形参，对外部的实参plist没有影响

举一个简单的例子：

void swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
int main()
{
	int x = 1, y = 2;
	swap(&x, &y);
	return 0;
}

我们都知道交换x , y 需要传它们的地址，如果定义 int* px = &x, int* py =&y，这样传px,py，swap函数用一级指针接收还能完成交换吗？显然是不行的，这时就需要二级指针接收。

void swap(int** ppx, int** ppy)
{
	int* tmp = *ppx;
	*ppx = *ppy;
	*ppy = tmp;
}
int main()
{
	int x = 1, y = 2;
	int* px = &x, * py = &y;
	swap(&px,&py);
	return 0;
}

所以，传一级指针要用二级指针接收，传结构体类型指针，要用相应的二级指针来接收。

因此，这里要用**pphead。

销毁代码如下：

void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pphead = NULL;
}

 这里要多创建一个指针来保存当前free的节点的下一个节点，否则free过后就找不到下一个节点了。

单链表的打印

为了更好地理解单链表，我们先来写一个打印的接口。

void SListPrint(SLTNode* phead)
{
	assert(phead); //？？？？？
}

这里因为不需要改变plist，所以传一级指针就可以了。

注意：在这不能对phead断言。因为phead不可能是空。phead存的是plist的地址，就算plist == NULL，即链表为空，但plist的地址也不为空，因此，phead不可能为空。

打印代码如下：

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

单链表的头插尾插

既然是插入数据，那么就需要保存新数据的新的节点，这里再写一个创建新节点的接口。

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTDataType));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

然后创建新的节点头插。

void SListPushFront(SLTNode** pphead,SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

逻辑角度分析：

 *pphead = NULL（链表为空时一样）

物理角度分析：

尾插：

尾插有两种情况，要分开讨论：

 代码如下：

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	SLTNode* tail = *pphead;
	while (tail->next)
	{
		tail = tail->next;
	}
	tail->next = newnode;
}

注意这里找尾的时候容易出错，不是tail去去找，而是tail->next，tail->next = NULL时就找到了最后一个位置。

头删尾删

头删

 头删的时候注意要先记录第一个节点，然后将其free掉，否则*pphead指向第二个节点就找不到第一个节点了。

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}

尾删

 先找到尾，将其free是不是就行了？错！这是一个经典的野指针问题。

free最后一个节点，倒数第二个节点还指向它，那就是野指针了。

因此，可以用两个指针走，tail记录后一个，用prev记录前一个，tail找到最后一个时prev在倒数第二个的位置，将其next的指向改成null就行了。

 代码如下：

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
		tail = NULL;
	}
	
}

当然，这里也有如果链表为空（*pphead == NULL）的情况，同样断言一下即可。

还需注意的是还有一种只有一个节点的情况没有考虑，当只有一个元素时，会出现越界，所以要单独拿出来讨论一下。

上述代码还有一种写法：

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

查找和修改

这个接口非常的简单，修改在查找到的基础上可以直接改。

代码如下：

SLNode* SListFind(SLNode* phead, SLTDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
 
//test.c
	SLNode* ret = SListFind(plist, 1);
	if (ret)
	{
		printf("找到了\n");
		//修改也可以实现
		ret->data *= 10;
	}
	else
	{
		printf("找不到\n");
	}

指定位置插入

这需要和上面的查找配合使用，找到需要插入的位置，再调用指定位置插入接口。

指定位置前插（pos之前）

//test.c
	
SLNode* ret = SListFind(plist, 1);
	if (ret)
	{
		printf("找到了\n");
		//修改也可以实现
		ret->data *= 10;
		SListPosInsert(&plist, ret, 4);
	}
	else
	{
		printf("找不到\n");
	}
	SListPrint(plist);
}
 
//SList.c
void SListPosInsert(SLNode** pphead, SLNode* pos,SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			//暴力检查，找不到pos，pos传错了
			assert(prev);
		}
		SLNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

 这里注意不能直接找到pos位置插入，因为单链表是单向的，不能后一个节点找前一个节点的位置，所以要创建一个prev指针去找pos前一个节点的位置。

指定位置后插（pos之后）

void SListPosInsertAfter(SLNode* pos, SLTDataType x)//pos位置之后
{
	assert(pos);
	SLNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

后插非常简单，要注意的是连接节点的两句代码容易写反，要想清楚。

 

指定位置删除

指定位置处删除（删除pos处）

分两种情况：pos在头上和不在头上。在头上调用头删接口就行了。

不在头上，和指定位置插入一样，也要创建一个指针prev找到pos的前一个节点，连接prev和pos->next，最后free（pos）。注意：因为这里传参传的pos是一级指针，是无法改变外部实参的，所以要在Test函数中将pos置空。

//SList.c
 
void SListPosErase(SLNode** pphead, SLNode* pos)//pos位置之前
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			assert(prev);
		}
		prev->next = pos->next;
		free(pos);
	}
}
 
//Test.c
void Test3()
{
	SLNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SLNode* ret = SListFind(plist, 3);
	if (ret)
	{
		printf("找到了\n");
		SListPosErase(&plist, ret);
		ret = NULL;
	}
	else
	{
		printf("找不到\n");
	}
}

指定位置后部插入

//SList.h
 
void SListPosEraseAfter(SLNode* pos)//pos位置之后
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	pos->next = pos->next->next;
	free(pos->next);
}
 
 
//Test.c
 
void Test3( )
{
    SListPrint(plist);
 
	SLNode* pos = SListFind(plist, 2);
	if (pos)
	{
		printf("找到了\n");
		SListPosEraseAfter(pos);
	}
	else
	{
		printf("找不到\n");
	}
	SListPrint(plist);
 
	SListDestory(&plist);
 
}

后删就很简单了，大家参考一下就行。

总而言之，单链表因为结构原因，存在很多缺陷，不能完全解决顺序表的问题。只有头部操作的接口比较实用。以后我会讲一种带头双向循环链表，就能较好的解决以上问题了。