189 8069 5689

一篇文章带你学完链表基础（C语言）-创新互联

链表，也称线性表的链式存储结构，其元素在内存空间上不是连续的，通过指针链接来决定元素的次序。
链表

创新互联是一家成都网站制作、成都网站设计，提供网页设计，网站设计，网站制作，建网站，按需网站开发，网站开发公司，从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://cdxtjz.cn/article/icgig.html

其他资讯