1.鏈錶的概念及結構

1.1概念

鏈錶是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈錶
中的指針鏈接次序實現的。

鏈錶的結構就跟火車類似，頭結點就相當於火車頭，每個節點就像每節車厢，相互鏈接起來，但是這裏的鏈錶的物理地址不一定連續，邏輯結構連續，下面用圖給大家演示。
 

圖為單向帶頭不循環鏈錶其中plist裏存放的是node1的地址，node1裏的next存放的是node2的地址，指向第二個結點，依次指下去，最後一個結點node4的next指向的為NULL代錶鏈錶的尾 。

1.2結構

單向與雙向 ：

帶頭與不帶頭： 

 循環與不循環：

下面給大家介紹不帶頭單向不循環鏈錶：上一篇介紹到了順序錶，而面對鏈錶我們需要插入一個數據就開創一個節點，所以面對空間不會存在浪費現象，可能有的人會說這樣一直開辟效率會不會很慢，其實這個問題不用太過關心，因為當前的計算機硬件部分也是相對發達的，運行起來也就是一瞬間的事情。下面用代碼給大家展示一下這個鏈錶的結構：

//對數據類型改名，往後若想替換int類型只需要改在這裏改int就可以
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;//指向下一個節點
}SListNode;

2.單鏈錶功能實現

2.1創建新節點

//創建一個新節點
SListNode* SLBuyNode(SLDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}

2.2删除 

單鏈錶的删除只需要free掉需要删除的節點，然後將鏈錶連接起來即可，不需要挪動數據。 

2.2.1尾删 

//尾删
void SListPopBack(SListNode** pphead)
{
if (*pphead == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}

2.2.2頭删

//頭删
void SListPopFront(SListNode** pphead)
{
assert(*pphead);
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

2.2.3在指定比特置後删除 

//在pos後删除
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next == NULL)
return;
SListNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}

 2.3插入數據

單鏈錶想要插入一個數據時需要創建一個新節點，並在想要插入的比特置將前後鏈錶鏈接起來，也就是使用next的指向鏈接即可。

2.3.1尾插 

//尾插
void SLPushBack(SListNode** pplist, SLDataType x)
{
assert(*pplist);
SListNode* newnode = SLBuyNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
SListNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}

2.3.2頭插

//頭插
void SLPushFront(SListNode** pplist, SLDataType x)
{
assert(*pplist);
SListNode* tail = SLBuyNode(x);
tail->next = *pplist;
//將鏈錶的頭部變為新節點
*pplist = tail;
}

2.3.3在指定比特置後插入

//在pos後插入
void SListInsertAfter(SListNode* pos, SLDataType x)
{
assert(pos);
SListNode* newnode = SLBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

2.4查找

 我們通過指定的數據查找當前比特置，找到了就返回當前節點的地址，通過遍曆一遍鏈錶，比較每個節點的data是否和X相等。找不到就返回NULL錶示沒有。

//查找
SListNode* SListFind(SListNode* plist, SLDataType x)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
printf("找到了\n");
return cur;
}
cur = cur->next;
}
return NULL;
}

2.5修改數據

這裏修改數據和查找配合使用，當我們找到需要修改的數據的地址過後直接將該數據的data變成我們需要的數據覆蓋即可。 

//修改
void SListModify(SListNode* pos, SLDataType x)
{
assert(pos);
pos->data = x;
}

這裏的鏈錶就到這裏，下一篇給大家介紹單鏈錶的經典筆試題。