在学习了顺序表，我们可能会对其有一些思考：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
   200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

那么有没有一些更好的结构来解决这些问题呢？这篇博客就给大家讲一讲单链表这个重要的数据结构。

---

⚡链表的概念及结构

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

链表的结构： 链式结构在逻辑上是连续的，但在物理上不一定连续。

---

⚡单链表各接口实现

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

动态申请一个结点：

SLTNode* BuySLNode(SLTDatatype x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){printf("malloc fail\n");return 0;}newnode->data = x;newnode->next = NULL;return newnode;
}

单链表的打印：

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

单链表头插：

void SLPushFront(SLTNode** pphead, SLTDatatype x)
{/*SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){printf("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;*/SLTNode* newnode = BuySLNode(x);newnode->next = *pphead;*pphead = newnode;
}

单链表尾插：

void SLPushBack(SLTNode** pphead, SLTDatatype x)
{SLTNode* newnode = BuySLNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

单链表头删：

void SLPopFront(SLTNode** pphead)
{assert(*pphead);/*if ((*pphead)->next == NULL){*pphead = NULL;}else{SLTNode* tail = *pphead;*pphead = tail->next;}*/SLTNode* tail = *pphead;*pphead = tail->next;
}

单链表尾删：

void SLPopBack(SLTNode** pphead)
{assert(*pphead);//单链表只有一个结点if ((*pphead)->next == NULL){*pphead = NULL;}//结点数大于1else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}tail->next = NULL;}
}

 单链表查找：

SLNode* SLFind(SLNode* pphead, SLNDatatype x)
{SLNode* tail = pphead;while (tail != NULL){if (tail->data == x){return tail;}tail = tail->next;}return NULL;
}

单链表pos位置处插入结点：

void SLInsert(SLNode** pphead, SLNode* pos, SLNDatatype x)
{assert(pphead);assert(pos);if (*pphead == pos){SLPushFront(pphead, x);}else{SLNode* tail = *pphead;while (tail->next != pos){tail = tail->next;}SLNode* newnode = BuySLNode(x);tail->next = newnode;newnode->next = pos;}
}

单链表pos位置之后插入结点：

void SLInsertAfter(SLNode* pos, SLNDatatype x)
{assert(pos);SLNode* newnode = BuySLNode(x);newnode->next = pos->next;pos->next = newnode;
}

在单链表删除pos处的结点：

void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLPopFront(pphead);}else{SLNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);}
}

在单链表删除pos之后的结点：

void SLEraseAfter(SLNode* pos)
{assert(pos);assert(pos -> next);pos->next = pos->next->next;free(pos->next);
}

---

感谢大家能够看完这篇博客，创作时长，小伙伴们觉得我的博客对你有帮助，不妨留下你的点赞的收藏，关注我，带你了解不一样的数据结构。