身家過億的帝都富豪來參加1024節專屬盛典，小碼農獻上單鏈表一篇來慶祝盛典

順序表的缺陷

1.空間不夠了需要擴容，增容是要付出代價

realloc的機制代價，與身具來的代價，1.后面記憶體足夠開辟就原地擴容，2.后面記憶體不夠就會異地擴容

2.避免頻繁擴容，我們滿了基本都是擴2倍，可能就會導致一定的空間浪費

3.順序表要求資料從開始位置連續存盤那么我們在頭部或者中間位置插入洗掉資料就需要挪動資料，效率不高

針對順序表的缺陷，就設計出了鏈表

鏈表是按需申請空間，不用了就釋放空間（更合理的使用空間）

頭部中間尾部插入洗掉資料，不需要挪動資料

當然他也是有缺陷的，例如每個資料后面都要存一個指標去鏈接后面的資料節點

不支持隨機訪問（也就是沒有下標訪問了）

鏈表

鏈表的概念及結構

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

鏈表的分類

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構

1.單向或者雙向

2.帶頭或者不帶頭

3.回圈或者非回圈

雖然有那么多的鏈表的結構，但是我們實際中最常用的還是兩種結構

1. 無頭單向非回圈鏈表：結構簡單，一般不會單獨用來存資料，實際中更多是作為其他資料結構的子結構，如哈希桶、圖的鄰接表等等，另外這種結構在筆試面試中出現很多，
2. 帶頭雙向回圈鏈表：==結構最復雜，==一般用在單獨存盤資料，實際中使用的鏈表資料結構，都是帶頭雙向回圈鏈表，另外這個結構雖然結構復雜，但是使用代碼實作以后會發現結構會帶來很多優勢，實作反而
   簡單了，后面我們代碼實作了就知道了，

鏈表的實作

無頭單向

單鏈表節點

typedef int SLTDataType;

//單鏈表節點
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

單鏈表列印函式SListPrint

有時候一步一步除錯會不怎么方便所以我們先把列印函式寫出來，然后再寫增刪改查也不遲

//單鏈表列印
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

單鏈表尾插函式SListPushBack

只要是插入不管你如何如何反正是插入你都得擴容，當然單鏈表擴容的單位是節點

//單鏈表尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//申請一個新節點
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾節點
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}	
}

獲得單鏈表節點函式

這時我是想寫頭插，但是思考一番發現，創建節點這一步會和尾插里面有些步驟重復，因此我們可以把重復的步驟抽離出來寫成一個函式就會方便一些

//獲得單鏈表節點函式
SLTNode* BuySListNode(SLTDataType x)
{
	//申請一個新節點
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)//實際上如果申請失敗了，就說明堆沒有多少空間了
	{
		printf("申請失敗\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;//然后把節點指標回傳出去
}

所以前面那個尾插就可以用這個復寫了

單鏈表頭插函式SListPushFront

//單鏈表頭插函式
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	//申請一個新節點
	SLTNode* newnode = BuySListNode(x);
	
	//讓新節點里面存plist頭結點的地址
	newnode->next = *pphead;
	//然后再讓newnode成為plist頭節點
	*pphead = newnode;
}

單鏈表尾刪函式SListPopBack

//單鏈表尾刪
void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if (!(*pphead)->next)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;//類似一個標記節點指標
		SLTNode* tail = *pphead;
		while (tail->next)//找到最后一個節點
		{
			prev = tail;//每次操作tail前讓prev先存一下他
			tail = tail->next;
		}
		free(tail);//把他空間釋放了
		tail = NULL;//然后指向空
		//但是前一個next我們沒有操作就是指向了原來已經釋放掉了的空間
		prev->next = NULL;
	}	
}

單鏈表頭刪函式SListPopFront

//單鏈表頭刪
void SListPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	(*pphead) = next;
}

單鏈表查找函式

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

主檔案的寫法

void test1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 1);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 2);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 4);
	SListPrint(plist);

	SLTNode* pos =  SListFind(plist,4);
	int i = 1;
	while (pos)
	{
		printf("第%d個pos節點,%p->%d\n",i++,pos,pos->data);
		//找到后的下一個地址
		pos = SListFind(pos->next, 4);
	}
}

查詢后修改

	SLTNode* pos1 = SListFind(plist,2);
	if (pos1)
	{
		//這里就可以看到查詢回傳節點指標的價值所在了
		pos1->data = 20;
	}
	SListPrint(plist);

單鏈表插入函式

可以通過和查詢函式配合來進行插入

//單鏈表插入函式
//在pos前面插入，這個pos在哪里來呢，就是從前面查找函式來
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//首先創建節點
	SLTNode* newnode = BuySListNode(x);
	if (pos == *pphead)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		//找到pos的前一個位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}	
}

看到上面就是知道單鏈表不太適合在前面插入，而是適合在后面插入，因為前插你要知道當前位置前面的那一個節點位置就會有點復雜，而后插就沒有這個prev的節點指標了

單鏈表后插函式

//單鏈表后插函式
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	//創建一個新的節點
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

單鏈表洗掉函式SListErase

單鏈表洗掉函式
這是我自己寫的，我們看下面老師寫的
//void SListErase(SLTNode** pphead, SLTNode* pos)
//{
//	SLTNode* cur = *pphead;
//	SLTNode* prev = NULL;
//	while (cur)
//	{
//		if (cur == pos)
//		{
//			if (pos == *pphead)
//			{
//				cur = (*pphead)->next;
//				free(*pphead);
//				(*pphead) = NULL;
//				*pphead = cur;
//			}
//			else
//			{
//				prev->next = cur->next;
//				free(cur);
//				cur = prev->next;
//			}			
//		}
//		else
//		{
//			prev = cur;
//			cur = cur->next;
//		}
//	}
//}

//單鏈表洗掉函式
//老師寫的
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	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->next);
	SLTNode* nextnode = pos->next;
	pos->next = nextnode->next;
	free(nextnode);
}

單鏈表銷毀函式

//單鏈表銷毀函式
void SListDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* nextnode = cur->next;
		free(cur);
		cur = nextnode;
	}
	*pphead = NULL;
}

練習題（從小到大老師一直教我們數形結合這東西是邏輯的根本，往往簡單的東西有人掌握了就變成了厲害人物，反而那些不在意圖的，死在途中無人問津，曾經我也是喜歡走的快，但是現在我放慢了腳步，為了走得遠）

1.移除鏈表元素

圖解

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* pos  = head;
    struct ListNode* prev = NULL;    
    while(pos)
    {
        if(pos->val == val)
        {
            if(pos == head)
            {
                pos = head->next;
                free(head);
                head = pos;
            }
            else
            {
                prev->next = pos->next;
                free(pos);
                pos = prev->next;
            }           
        }
        else
        {
            prev = pos;
            pos = pos->next;
        }
    }
    return head;
}

2.反轉鏈表

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    if(!cur)
    {
        return head;
    }
    else
    {
        struct ListNode* next = head->next;
        while(next)
        {       
            cur->next = prev;
            prev = cur;
            cur = next;  
            next = next->next;     
        }   
        cur->next = prev;
        return cur;
    }    
}