（数据结构）链表讲解和链表实现

矫情吗；* 2023-02-14 15:41 148阅读 0赞

**什么是链表？**  
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。  
**链表的优缺点：**  
**优点：**  
1.任意位置插入删除时间复杂度为O(1)  
2.没有增容问题，插入一个开辟一个空间  
**缺点：**  
以节点为单位存储，不支持随机访问

如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]  
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.  单向、双向
2.  带头、不带头
3.  循环、非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。  
2 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

**链表的实现：**  
**无头单向非循环链表**  
SList.h

#pragma once
    
    typedef int SLDataType;
    
    typedef struct SListNode
    {
        
    	struct SListNode* next;//指向下一个节点的地址
    	SLDataType data;//存储该节点的数据
    }SListNode;
    
    //如果想要在函数中改变头指针的指向，形参必须为二级指针
    void SListPushBack(SListNode** head, SLDataType data);
    void SListPopBack(SListNode** head);
    void SListPushFront(SListNode** head, SLDataType data);
    void SListPopFront(SListNode** head);
    
    void SListInsertAfter(SListNode* pos, SLDataType data);
    void SListEraseAfter(SListNode* pos);
    
    int SListSize(SListNode* head);
    int SListEmpty(SListNode* head);
    
    SListNode* SListFind(SListNode* head, SLDataType data);
    
    void SListDestroy(SListNode** head);

SList.c

#include "SList.h"
    #include <malloc.h>
    #include <stdio.h>
    #include <assert.h>
    
    //申请新节点
    SListNode* BuySListNode(SLDataType data)
    {
        
    	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    	if (NULL == newNode)
    	{
        
    		assert(0);  //调试宏，参数为0宏就会触发，非0不会触发
    		return NULL;
    	}
    	newNode->next = NULL;
    	newNode->data = data;
    	return newNode;
    }
    //尾插
    void SListPushBack(SListNode** head, SLDataType data)
    {
        
    	assert(head);
    	//空链表
    	SListNode* newNode = BuySListNode(data);
    	if (NULL == *head)
    	{
        
    		*head = newNode;
    	}
    	else
    	{
        
    		//1.找到链表中的最后一个节点
    		SListNode* cur = *head;
    		while (cur->next)
    		{
        
    			cur = cur->next;
    		}
    		//2.插入新节点
    		cur->next = newNode;
    	}
    }
    //尾删
    void SListPopBack(SListNode** head)
    {
        
    	assert(head);//检测非法情况
    	if (NULL == *head)
    	{
        
    		//空链表
    		return;
    	}
    	else if (NULL == (*head)->next)
    	{
        
    		//链表中只有一个节点
    		free(*head);
    		*head = NULL;
    	}
    	else
    	{
        
    		//链表非空---链表中至少有一个节点
    		SListNode* cur = *head;
    		SListNode* prev = NULL;
    		while (cur->next)
    		{
        
    			prev = cur;
    			cur = cur->next;
    		}
    		prev->next = NULL;
    		//删除该节点
    		free(cur);
    	}
    }
    //头插
    void SListPushFront(SListNode** head, SLDataType data)
    {
        
    	assert(head);
    	SListNode* newNode = BuySListNode(data);
    	newNode->next = *head;
    	*head = newNode;
    }
    //头删
    void SListPopFront(SListNode** head)
    {
        
    	assert(head);
    	SListNode* delNode = NULL;
    	if (NULL == *head)
    		return;
    	delNode = *head;
    	*head = delNode->next;
    	free(delNode);
    }
    //任意位置插入
    void SListInsertAfter(SListNode* pos, SLDataType data)
    {
        
    	SListNode* newNode = NULL;
    	if (NULL == pos)
    		return;
    	newNode = BuySListNode(data);
    	newNode->next = pos->next;
    	pos->next = newNode;
    }
    //任意位置删除
    void SListEraseAfter(SListNode* pos)
    {
        
    	SListNode* delNode = NULL;
    	if (NULL == pos||NULL == pos->next)
    		return;
    	delNode = pos->next;
    	pos->next = delNode->next;
    	free(delNode);
    }
    //节点个数
    int SListSize(SListNode* head)
    {
        
    	SListNode* cur = head;
    	int count = 0;
    	while (cur)
    	{
        
    		count++;
    		cur = cur->next;
    	}
    	return count;
    }
    //判断链表是否为空
    int SListEmpty(SListNode* head)
    {
        
    	return NULL == head;
    }
    //查找节点
    SListNode* SListFind(SListNode* head, SLDataType data)
    {
        
    	SListNode* cur = head;
    	while (cur)
    	{
        
    		if (cur->data == data)
    			return cur;
    		cur = cur->next;
    	}
    	return NULL;
    }
    //销毁链表
    void SListDestroy(SListNode** head)
    {
        
    	assert(head);
    	while (*head)
    	{
        
    		SListNode* delNode = *head;
    		*head = delNode->next;
    		free(delNode);
    	}
    }
    //打印链表
    void PrintSList(SListNode* head)
    {
        
    	SListNode* cur = head;
    	while (cur)
    	{
        
    		printf("%d--->", cur->data);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }

**带头双向循环链表**  
DHCList.h

#pragma once
    
    typedef int DLDataType;
    typedef struct DHCListNode
    {
        
    	DLDataType data;
    	struct DHCListNode* next;//指向当前节点的下一个节点
    	struct DHCListNode* prev;//指向当前节点的前一个节点
    }DHCLNode;
    
    DHCLNode* DHCListInit();
    void DHCListPushBack(DHCLNode* pHead,DLDataType data);
    void DHCListPopBack(DHCLNode* pHead);
    void DHCListPushFront(DHCLNode* pHead,DLDataType data);
    void DHCListPopFront(DHCLNode*pHead);
    void DHCListInsert(DHCLNode* pos,DLDataType data);
    void DHCListErase(DHCLNode* pos);
    DHCLNode* DHCListFind(DHCLNode* pHead,DLDataType data);
    int DHCListSize(DHCLNode* pHead);
    int DHCListEmpty(DHCLNode* pHead);
    void DHCListClear(DHCLNode* pHead);
    void DHCListDestroy(DHCLNode** pHead);
    void TestDHCList();

DHCList.c

#include "DHCList.h"
    #include <malloc.h>
    #include <assert.h>
    #include <stdio.h>
    
    //申请新节点
    DHCLNode* BuyDHCListNode(DLDataType data)
    {
        
    	DHCLNode* newNode = (DHCLNode*)malloc(sizeof(DHCLNode));
    	if (NULL == newNode)
    	{
        
    		assert(0);
    		return NULL;
    	}
    	newNode->data = data;
    	newNode->next = NULL;
    	newNode->prev = NULL;
    	return newNode;
    }
    //初始化：只需将头结点申请好
    DHCLNode* DHCListInit()
    {
        
    	DHCLNode* head = BuyDHCListNode(0);
    	head->next = head;
    	head->prev = head;
    	return head;
    }
    //这里尾插，头插，任意位置插入原理是一样的
    //同样尾删，头删，任意位置删除也是一样的，掌握其中一个即可。
    //尾插
    void DHCListPushBack(DHCLNode* pHead, DLDataType data)
    {
        
    	assert(pHead);
    	DHCListInsert(pHead, data);
    }
    //尾删
    void DHCListPopBack(DHCLNode* pHead)
    {
        
    	if (DHCListEmpty(pHead))
    		return;
    	DHCListErase(pHead->prev);
    }
    //头插
    void DHCListPushFront(DHCLNode* pHead, DLDataType data)
    {
        
    	assert(pHead);
    	DHCListInsert(pHead->next, data);
    }
    //头删
    void DHCListPopFront(DHCLNode*pHead)
    {
        
    	if (DHCListEmpty(pHead))
    		return;
    	DHCListErase(pHead->next);
    }
    //任意位置插入
    void DHCListInsert(DHCLNode* pos, DLDataType data)
    {
        
    	DHCLNode* newNode;
    	if (NULL == pos)
    		return;
    	//申请新节点
        
    	newNode = BuyDHCListNode(data);
    	//先将新节点链接到原链表中
    	newNode->next = pos;
    	newNode->prev = pos->prev;
    	//断开链表
    	pos->prev = newNode;
    	newNode->prev->next = newNode;
    }
    //任意位置删除
    void DHCListErase(DHCLNode* pos)
    {
        
    	if (NULL == pos)
    		return;
    	pos->prev->next = pos->next;
    	pos->next->prev = pos->prev;
    	free(pos);
    }
    //查找节点
    DHCLNode* DHCListFind(DHCLNode* pHead, DLDataType data)
    {
        
    	assert(pHead);
    	DHCLNode* cur = pHead->next;
    	while (cur!=pHead)
    	{
        
    		if (data == cur->data)
    			return cur; 
    		cur = cur->next;
    	}
    	return NULL;
    }
    //节点个数
    int DHCListSize(DHCLNode* pHead)
    {
        
    	assert(pHead);
    	DHCLNode* cur = pHead->next;
    	int count = 0;
    	while (cur != pHead)
    	{
        
    		++count;
    		cur = cur->next;
    	}
    	return count;
    }
    //判断是否为空链表（只剩头节点）
    int DHCListEmpty(DHCLNode* pHead)
    {
        
    	assert(pHead);
    	return pHead->next == pHead;
    }
    //只是将链表中的有效节点删除，不删头节点
    void DHCListClear(DHCLNode* pHead)
    {
        
    	assert(pHead);
    	DHCLNode* cur = pHead->next;
    	while (cur != pHead)
    	{
        
    		pHead->next = cur->next;
    		free(cur);
    		cur = pHead->next;
    	}
    	//链表已经为空
    	pHead->next = pHead;
    	pHead->prev = pHead;
    }
    //需要将头结点和所有头结点全部删除
    void DHCListDestroy(DHCLNode** pHead)
    {
        
    	assert(pHead);
    	DHCListClear(*pHead);
    	free(*pHead);
    	*pHead = NULL;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603154850195.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200603155528759.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70