目錄

為什么有了順序表，還需要有鏈表這樣的資料結構呢？

?下面實作一個簡單的鏈表：

尾插：

頭插：

尾刪：

頭刪：

計算大小：

查找 & 在pos位置之前去插入x:

洗掉pos位置的數&洗掉pos位置的下一個數：

銷毀單鏈表：

具體代碼：Gitee 單鏈表

為什么有了順序表，還需要有鏈表這樣的資料結構呢？

順序表的問題：

1，中間/頭部的插入洗掉，時間復雜度為O(N)

2，增容需要申請新空間，拷貝資料，釋放舊空間，會有不小的消耗

3，增容一般是呈2倍的增長，勢必會有一定的空間浪費，例如當前容量為100，滿了以后增容到200，我們再繼續插入5個資料，后面沒有資料插入了，那么久浪費了95個資料空間

鏈表是一種物理存盤結構上非連續，非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，

下面實作一個簡單的鏈表：

注意：

1.鏈表結構在邏輯上是連續的，但是在物理上不一定連續

2.現實中的結點一般都是從堆上申請出來的

3.從堆上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續,也可能不連續

尾插：

注意：這里用二級指標，因為要改變phead，不改變就傳一級

當鏈接是空的時候，就有可能改變phead

//創建一個新的結點
SLTNode* BuyListNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
	return node;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	assert(pphead);//頭指標有可能為空，頭指標地址不能為空
	if (*pphead == NULL)
	{
		SLTNode* newnode = BuyListNode(x);
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLTNode* newnode = BuyListNode(x);
		tail->next = newnode;
	}
}

頭插：

思路分析：

void SlistPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;

	//思考：如果鏈表為空，頭插這樣會不會出問題

}

尾刪：

void SlistPopBack(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* tail = *pphead;
	while (tail->next)
	{
		tail = tail->next;
	}
	free(tail);
	tail = NULL;
}

如上會出現什么問題呢？

當最后一個刪掉，倒數第二個就變成尾了

如下提供2種解決方案：

void SlistPopBack(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* tail = *pphead;

	//方法1：
	//while (tail->next->next!=NULL)
	//{
	//	tail = tail->next;
	//}
	//free(tail->next);
	//tail->next = NULL;
	//方法2：
	SLTNode* prev = NULL;
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
}

思考上面會出現什么問題？

當沒有結點的時候，報錯！

當只有一個結點的時候，plist沒有置為NULL

assert(pphead);
	//沒有結點斷言報錯---處理方式較為激進

	assert(*pphead);//鏈表為空，還在呼叫尾刪

	/*if (*pphead == NULL)
	{
		return;
	}*/

	//1,一個結點
	//2,多個結點
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}

頭刪：

void SlistPopFront(SLTNode** pphead)
{
	//plist一定有地址，所以pphead不為空
	assert(pphead);

	//1.鏈表為空
	assert(*pphead);

	//2.只有一個結點
	//3.多個結點
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* node = (*pphead)->next;
		free(*pphead);
		*pphead = node;
	}
}

思考如何進行優化？——可以直接進行合并

void SlistPopFront(SLTNode** pphead)
{
	//plist一定有地址，所以pphead不為空
	assert(pphead);

	//1.鏈表為空
	assert(*pphead);

	//2.只有一個結點
	//3.多個結點
		SLTNode* node = (*pphead)->next;
		free(*pphead);
		*pphead = node;
}

計算大小：

int SListSize(SLTNode* phead)
{
	int size = 0;
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

bool SListEmpty(SLTNode* phead)
{
	return phead == NULL;
}

查找 & 在pos位置之前去插入x:

//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
}

//在pos位置之前去插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
    assert(pos);
	if (*pphead == pos)
	{
		SlistPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuyListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

思考：如果在其pos后插入會不會簡單一點？

注意點：注意順序！

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

單鏈表不適合在pos位置之前插入，因為需要找前一個位置，更適合在之后的位置插入！

洗掉pos位置的數&洗掉pos位置的下一個數：

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	//1.頭刪
	//2.后面結點的洗掉
	if (pos == *pphead)
	{
		SlistPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}

}

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}

銷毀單鏈表：

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

具體代碼：Gitee 單鏈表