链表，也称线性表的链式存储结构，其元素在内存空间上不是连续的，通过指针链接来决定元素的次序。
创新互联是一家成都网站制作、成都网站设计，提供网页设计，网站设计，网站制作，建网站，按需网站开发，网站开发公司，从2013年开始是互联行业建设者，服务者。以提升客户品牌价值为核心业务，全程参与项目的网站策划设计制作，前端开发，后台程序制作以及后期项目运营并提出专业建议和思路。目录
- 一、链表的分类
- 1.单向或者双向
- 2.带头或者不带头
- 3.循环或者非循环
- 二、单链表的实现
- 动态申请一个节点
- 单链表打印
- 单链表尾插
- 单链表尾删
- 单链表头插
- 单链表头删
- 单链表查找
- 单链表pos之后插入x
- 单链表pos之前插入x
- 单链表删除pos之后的节点
- 单链表删除pos节点
- 单链表销毁
- 例题——删除链表中等于给定值 val 的所有节点
- 方法一：原链表修改
- 方法二：创建新链表
- 方法三：创建带头链表
- 例题——反转链表
- 三、双向带头循环链表的实现
- 动态申请一个节点
- 初始化
- 打印
- 尾插
- 尾删
- 头插
- 头删
- 查找
- 插入
- 删除
- 判断链表是否为空
- 返回链表长度
- 销毁
- 四、总结
一、链表的分类
链表的结构多种多样，以下的情况组合起来就有8种链表结构。
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
虽然有这么多种结构，但是我们最常用的只有两种：
1.无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。
2.带头双向循环链表：结构最复杂，但实现起来比较简单。
二、单链表的实现
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;
struct SListNode* next;
}SLTNode;
//动态申请一个节点
SLTNode* BuySListNode(SLTDataType x);
//单链表打印
void SLTPrint(SLTNode* phead);
//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//单链表尾删
void SLTPopBack(SLTNode** pphead);
//单链表头插
void SLTPushFount(SLTNode** pphead, SLTDataType x);
//单链表头删
void SLTPopFount(SLTNode** pphead);
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//单链表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//单链表pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//单链表删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//单链表删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//单链表销毁
void SLTDestroy(SLTNode** pphead);
动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{perror("malloc file:");
exit(-1);//退出程序
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
单链表打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;
while (cur != NULL)
{printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{*pphead = newnode;
}
else
{SLTNode* tail = *pphead;
while (tail->next)
{ tail = tail->next;
}
tail->next = newnode;
}
}
这里使用二级指针是因为当链表为空时，需要改变一级指针phead为newnode，想要改变一级指针的值要用二级。
单链表尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);
if ((*pphead)->next == NULL)
{free(*pphead);
*pphead = NULL;
}
else
{SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{ prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
单链表头插
void SLTPushFount(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
单链表头删
void SLTPopFount(SLTNode** pphead)
{assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;
while (cur)
{if (cur->data == x)
{ return cur;
}
cur = cur->next;
}
return NULL;
}
单链表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
单链表pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);
if (*pphead == pos)
{SLTPushFount(pphead, x);
}
else
{SLTNode* prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
------为什么在pos之后插入x相比在之前插入要简单呢？
因为想要在pos之前插入，必须要找到pos的前一个节点，只能通过遍历链表来找到它。后面的删除指定结点也是相同的道理。
单链表删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);
if (pos->next == NULL)
{return;
}
else
{SLTNode* nextNode = pos->next;
pos->next = pos->next->next;
free(nextNode);
}
}
单链表删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);
if (*pphead == pos)
{SLTPopFount(pphead);
}
else
{SLTNode* prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
单链表销毁
void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;
while (cur)
{SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
通过以上代码可以看出，相比顺序表，链表的头插和头删要简便许多，而尾插和尾删要繁琐一些，这是因为链表不能随机存取，想要找到最后一个结点必须从头开始遍历。
学会了单链表的实现，那么有不少单链表的题就可以有思路了，许多题看似复杂，但实际上就是单链表的插入、删除。
例题——删除链表中等于给定值 val 的所有节点
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
val = 5：
方法一：原链表修改
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *p = head;
while (cur)
{if(cur == head) //当cur为头时
{if (cur->val == val)
{cur = cur->next;
head = cur;
p = cur;
}
else
{cur = cur->next;
}
}
else if (cur->next == NULL) //当cur为尾时
{if (cur->val == val)
{cur = cur->next;
p->next = NULL;
}
else
{cur = cur->next;
}
}
else //当cur在中间
{if (cur->val == val)
{cur = cur->next;
p->next = p->next->next;
}
else
{p = cur;
cur = cur->next;
}
}
}
return head;
}
这是我做这道题时想出的第一个方法，这个方法非常繁琐，要考虑三种情况，就是当cur在头、尾、中间。这个方法很容易想到但难以用代码去实现，在写代码的过程中经常容易乱。
其实这个方法可以优化一下，把“if (cur->val = val)”这个判断拿到外层。代码如下：
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *prev = head;
while (cur)
{if (cur->val == val)
{if (cur == head) //当cur为头时
{cur = cur->next;
free(head);
head = cur;
prev = cur;
}
else //当cur不为头
{prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
else
{prev = cur;
cur = cur->next;
}
}
return head;
}
这下看起来是不是简单多了？
回到优化前的代码：在每一个判断cur位置的条件语句中，都包含了对cur->val的判断，于是我想到不妨把里面的这个条件语句拿出来，这样外层就只需要if-else就好了，少了一层判断。再看内部，我也只分了两个条件，一个是cur为头，另一个就是不为头，当cur在中间和尾时的操作其实时相同的，所以把它们合并在一起。并且加上了free函数，把要删除的结点free掉，防止内存泄漏。
其实很多人第一次写都会写出像优化前那样的代码，这很正常，因为初次接触思路可能没有那么清晰，多练练就好了。
方法二：创建新链表
与其像方法一那样在原链表上进行操作，我们不妨创建一个新的链表，然后把符合条件的值尾插到新链表中。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
struct ListNode* newhead = NULL; //新链表的头
struct ListNode* tail = NULL; //新链表的尾
while (cur)
{if (cur->val != val)
{if (tail == NULL) //判断新链表是否为空
{newhead = tail = cur;
}
else
{tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
if (tail) //把新链表的尾结点的next置NULL
{tail->next = NULL;
}
return newhead;
}
这种方法想起来不难，实现起来也不难，写完之后就会发现这不就是单链表的尾插吗，只不过就是加了一个筛选条件而已。
方法三：创建带头链表
第三种方法是创建一个带头链表。
我们知道，单链表的尾插相比头插要复杂一些，于是我想到采用带头链表。
采用带头链表可以省去判断新链表是否为空，因为它一定带有头节点不为空，使代码更简洁。
注意：本题要求返回的链表不能带有头节点，所以在最后应该返回头节点的next。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
struct ListNode* guard, *tail;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); //动态开辟一个头结点
guard->next = NULL;
while (cur)
{if (cur->val != val)
{tail->next = cur;
tail = tail->next;
cur = cur->next;
}
else
{struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
tail->next = NULL;
struct ListNode* newhead = guard->next;
free(guard);
return newhead;
}
这种方法不用考虑多种情况，是我最喜欢的方法。
例题——反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
方法一：迭代法
这题其实很容易，我们只需要创建一个新链表，然后依次把原链表中的元素头插到新链表中即可。代码如下:
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;
struct ListNode* rhead = NULL;
while (cur)
{struct ListNode* next = cur->next;
cur->next = rhead;
rhead = cur;
cur = next;
}
return rhead;
}
方法二：递归法
这道题也可以采用递归的方法，不过有些难以理解。
struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL || head->next == NULL)
{return head;
}
struct ListNode* newhead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
}
三、双向带头循环链表的实现
双向带头循环链表虽然结构最复杂，但是实现起来可一点也不复杂，相信你通过前面对单链表的学习，一定能自己写出双向链表。
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
//动态申请一个结点
LTNode* BuyListNode(LTDataType x);
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//插入
void LTInsert(LTNode* phead, LTDataType x);
//删除
void LTErase(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//返回链表长度
size_t LTSize(LTNode* phead);
//销毁
void LTDestroy(LTNode* phead);
动态申请一个节点
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
初始化
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
打印
void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;
while (cur != phead)
{printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//LTInsert(phead, x);
}
尾删
void LTPopBack(LTNode* phead)
{assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
//LTErase(phead->prev);
}
头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);
LTNode* newnode = BuyListNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
//LTInsert(phead->next, x);
}
头删
void LTPopFront(LTNode* phead)
{assert(phead);
assert(phead->next != phead);
LTNode* first = phead->next;
LTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
//LTErase(phead->next);
}
查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{if (cur->data == x)
{ return cur;
}
cur = cur->next;
}
return NULL;
}
插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
删除
void LTErase(LTNode* pos)
{assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
free(pos);
prev->next = next;
next->prev = prev;
}
在实现插入、删除后，我们其实可以将其复用到尾插尾删头插头删中。
判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);
return phead->next == phead;
}
返回链表长度
size_t LTSize(LTNode* phead)
{assert(phead);
LTNode* cur = phead->next;
size_t size = 0;
while (cur != phead)
{++size;
cur = cur->next;
}
return size;
}
销毁
void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;
while (cur != phead)
{LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
四、总结
本文主要讲述了单链表和双向带头循环链表的实现，其中单链表尤为重要，在笔试和面试中经常会考到，建议各位读完本文多去刷一些有关单链表的题，它还有许多奥秘等待大家去探索。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
新闻名称：一篇文章带你学完链表基础（C语言）-创新互联
标题网址：
http://cdkjz.cn/article/icgig.html
