双链表-纯C语言（代码以及详细解释）

川长思鸟来 2023-09-27 21:42 81阅读 0赞

**目录**

简介：

使用 C 代码实现（可供CV大师参考）

代码详细介绍及讲解（知识点密集）

(可能错误，大佬们评论区指点)\[doge保命\]

1、动态申请一个节点

2、打印（遍历链表）

3、尾插数据

4、头插数据

5、头删数据

6、尾删数据

7、查找数组（返回查找数据的地址）

8、在链表X数据之后插入y

9、在链表X数据之前插入y

10、把链表中的X值修改为y

11、把链表中X值所在的结点删除

12、把链表中X值之前的一个结点删除

13、把链表中X值之后的一个结点删除

14、链表的销毁

--------------------

## 简介： ##

首先我们来了解一下什么是双线链表：

> **双链表顾名思义，就是链表由单向的链变成了双向链。 使用这种数据结构，**
> 
> **我们可以不再拘束于单链表的单向创建于遍历等操作，大大减少了在使用中存在的问题。**

双链表的简图如下：

![aba8670b0ba84fed8a396d2d73d6d6b6.png][]

![5c0855fce268427f9f5b6be1ac68fbba.png][]

![37b5386f0f464e76ab0223a8c7b2a2e7.png][]

## 使用 C 代码实现（可供CV大师参考） ##

友友们如果你们可以留下宝贵的**赞赞**那就**泰裤辣**

> 下面是全部代码其中分为：
> 
> 1、动态申请一个节点（返回新节点的地址）
> 
> 2、打印（遍历链表）
> 
> 3、尾插数据
> 
> 4、头插数据
> 
> 5、头删数据
> 
> 6、尾删数据
> 
> 7、查找数组（返回查找数据的地址）
> 
> 8、在链表X数据之后插入y
> 
> 9、在链表X数据之前插入y
> 
> 10、把链表中的X值修改为y
> 
> 11、把链表中X值所在的结点删除
> 
> 12、把链表中X值之前的一个结点删除
> 
> 13、把链表中X值之后的一个结点删除
> 
> 14、链表的销毁

#define _CRT_SECURE_NO_WARNINGS 1
    #include <stdlib.h>
    #include <assert.h>
    #include <stdio.h>
    typedef int DLTDateType;
    typedef struct DListNode
    {
        struct DListNode* prove;
        DLTDateType data;
        struct DListNode* next;
    }DListNode;
    
    
    
    DListNode* BuyDListNode(DLTDateType x)    // 动态申请一个节点
    {
        DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
        if (newnode == NULL)
        {
            perror("malloc fail");
            return NULL;
        }
        newnode->data = x;
        newnode->next = newnode;
        newnode->prove = newnode;
        return newnode;
    
    }
    void DListPrint(DListNode* head)  //打印链表
    {
        DListNode* cup = head->next;
        printf("header <—> ");
        while (cup != head)
        {
            printf("%d <—> ", cup->data);
            cup = cup->next;
        }
        printf("header\n");
    }
    void DListPushBack(DListNode* head, DLTDateType x)  //尾插
    {
        DListNode* newnode = BuyDListNode(x);
        DListNode* pro = head->prove;
        pro->next = newnode;
        newnode->prove = pro;
        newnode->next = head;
        head->prove = newnode;
    }
    void DListPushFront(DListNode* head, DLTDateType x)  //头插
    {
        DListNode* newnode = BuyDListNode(x);
        DListNode* next = head->next;
        newnode->next = next;
        newnode->prove = head;
        head->next = newnode;
        next->prove = newnode;    
    }
    void DListPopFront(DListNode* head)   //头删
    {
        assert(head);
        if (head->next == head)
        {
            printf("DEL error :Empty linked lists cannot be deleted");
            return;
        }
        DListNode* first = head->next;
        DListNode* second = first->next;
        head->next = second;
        second->prove = head;
        free(first);
        first = NULL;
    }
    void DListPopBack(DListNode* head)  //尾删
    {
        assert(head);
        if (head->next == head)
        {
            printf("DEL error :Empty linked lists cannot be deleted");
            return;
        }
        DListNode* Headprove = head->prove;
        DListNode* proveProve = Headprove->prove;
        proveProve->next = head;
        head->prove = proveProve;
    }
    DListNode* DListFind(DListNode* head, DLTDateType x)   //查找
    {
        DListNode* cup = head->next;
        while (cup != head)
        {
            //cup = cup->next;
            if (cup->data == x)
            {
                return cup;
            }
            cup = cup->next;
        }
        printf("Not found\n");
        return NULL;
    }
    void DListInsertAfter(DListNode* head, DLTDateType x, DLTDateType y)   //x位置之后插入y
    {
        DListNode* pos = DListFind(head, x);
        DListNode* newnode = BuyDListNode(x);
        newnode->data = y;
        DListNode* next = pos->next;
        next->prove = newnode;
        newnode->next = next;
        newnode->prove = pos;
        pos->next = newnode;
    }
    void DListInsertBefor(DListNode* head, DLTDateType x, DLTDateType y)   //x位置之前插入y
    {
    
        DListNode* pos = DListFind(head, x);
        DListNode* newnode = BuyDListNode(x);
        newnode->data = y;
        DListNode* prove = pos->prove;
        prove->next = newnode;
        newnode->prove = prove;
        newnode->next = pos;
        pos->prove = newnode;
    }
    void DListChange(DListNode* head, DLTDateType x, DLTDateType y)  //把链表中的X数据改为y
    {
        DListNode* pos = DListFind(head, x);
        assert(pos);
        pos->data = y;  
    }
    void DListErase(DListNode* head, DLTDateType x)  // 链表删除X位置的值
    {
        DListNode* pos = DListFind(head, x);
        assert(pos);
        DListNode* prove = pos->prove;
        DListNode* next = pos->next;
        prove->next = next;
        next->prove = prove;
    }
    void DListEraseBefore(DListNode* head, DLTDateType x)  // 链表删除X位置之前的值
    {
        DListNode* pos = DListFind(head, x);
        assert(pos);
        DListErase(head, pos->prove->data);
    }
    void DListEraseAfter(DListNode* head, DLTDateType x)  // 链表删除X位置之后的值
    {
        DListNode* pos = DListFind(head, x);
        assert(pos);
        DListErase(head, pos->next->data);
    }
    void DListDestroy(DListNode* head)  // 链表的销毁
    {
        DListNode* cup = head->next;
        while (cup != head)
        {
            DListNode* pos = cup;
            cup = cup->next;
            free(pos);
            pos = NULL;
        }
    }

## 代码详细介绍及讲解（知识点密集） ##

### (可能错误，大佬们评论区指点)\[doge保命\] ###

#### 1、动态申请一个节点 ####

二话不说先上代码：

typedef int DLTDateType;    //定义一个类型，方便后续更改链表里面的数据类型
    typedef struct DListNode
    {
    	struct DListNode* prove;  //储存前一个节点的地址
    	DLTDateType data;         //储存这个节点的值
    	struct DListNode* next;   //储存下一个节点的地址
    }DListNode;   //新定义结构体的名字
    
    
    DListNode* BuyDListNode(DLTDateType x)    // 动态申请一个节点
    {
    	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));  //malloc 开辟空间
    	if (newnode == NULL)
    	{
    		perror("malloc fail");
    		return NULL;
    	}
    	newnode->data = x;          //设置新空间的初始值
    	newnode->next = newnode;    //新节点的next 指向他自己
    	newnode->prove = newnode;   //新节点的prove也指向他自己
    	return newnode;   //返回新节点的地址

代码解释：

1.   **这个代码首先有很好的可读性，创建一个新的结点（方便复用）在后续的各种插入过程中，要经常创建一个新的结点进行插入，所以在开头我们可以先将其制作成一个函数，方便代码的复用，这是很重要的工程项目思维。**
2.  **创建新的结点，其实就是向内存申请一块空间，用malloc即可**
3.  **防止野指针问题，每次创建的新结点的prev和next指针我们都置空。之后将这个节点的地址返回即可，因为该节点的空间是在堆上的，函数栈帧销毁不会影响这段空间**。
    
    --------------------

#### 2、打印（遍历链表） ####

代码：

void DListPrint(DListNode* head)  //打印链表
    {
    	DListNode* cup = head->next;  //设置一个局部变量保存链表表头的位置
    	printf("header <—> ");  //  打印连接标志（为了美观）
    	while (cup != head)     //遍历列表
    	{
    		printf("%d <—> ", cup->data);  //打印数据
    		cup = cup->next;   //变量自增
    	}
    	printf("header\n");  //最后换行

代码解释：

1.  打印函数我们首先使用了一个局部变量储存链表头部的位置，因为有哨兵位的存在所以代码的头部在哨兵位的后一位。即 **cup = head->next** 
2.  后面我们打印了连接标志 **<—> (为了打印出来的链表更加的直观) 大概就是下面这样：**
    
    ![120ab5d02af7477aab25dd0718871918.png][]
3.  局部变量自增的时候使用代码  **cup = cup->next** 巧妙的使用结构体让 **cup** 增加

--------------------

#### 3、尾插数据 ####

代码：

void DListPushBack(DListNode* head, DLTDateType x)  //尾插数据
    {
    	DListNode* newnode = BuyDListNode(x);   // 使用函数创建新的节点
    	DListNode* pro = head->prove;   //使用局部变量记录尾结点的地址
    	pro->next = newnode;  //改变尾结点的 next 指针的指向
    	newnode->prove = pro; //连接新节点和尾结点 
    	newnode->next = head; //产生新的尾结点
    	head->prove = newnode;

代码解释：

1.  尾插的时候我们第一想到的是要有一个节点可以尾插，我们用 BuyDListNode( X ) 函数向内存申请一个新的节点来储存要插入的数据。
2.  有了新的节点以后紧接着就是找尾部节点了，对于双向链表来说它的优势就是可以直接从头节点一步找到尾部节点了，不用再去遍历链表。大大节省了计算机的运算时间。
3.  接下来就是最重要的插入、连接环节了。![87c8463bcb9b4fac8695104bdd31646c.png][]
4.  利用如图所示的四行代码就可以完成插入、连接的步骤了

--------------------

#### 4、头插数据 ####

void DListPushFront(DListNode* head, DLTDateType x)  //头插数据
    {
    	DListNode* newnode = BuyDListNode(x);   // 使用函数创建新的节点
    	DListNode* next = head->next;   //使用局部变量记录头结点的地址
    	newnode->next = next;    //改变新结点的 next 指针的指向
    	newnode->prove = head;   //连接新节点和头结点
    	head->next = newnode;
    	next->prove = newnode;	
    }

代码解释：

1.  尾插的时候我们第一想到的是要有一个节点可以尾插，我们用 BuyDListNode( X ) 函数向内存申请一个新的节点来储存要插入的数据。
2.  有了新的节点以后紧接着就是找头节点了，头节点在哨兵位的下一个位置
3.  接下来就是最重要的插入、连接环节了 详见代码。

--------------------

#### 5、头删数据 ####

代码：

void DListPopFront(DListNode* head)   //头删数据
    {
    	assert(head);  //首先要判定一下传入的head 是不是空指针
    	if (head->next == head)  // 判断是不是空链表
    	{
    		printf("DEL error :Empty linked lists cannot be deleted");//如果是空链表则不能删除
    		return;
    	}
    	DListNode* first = head->next;   //头删数据
    	DListNode* second = first->next;
    	head->next = second;
    	second->prove = head;
    	free(first);
    	first = NULL;
    }

代码解释：

1.  要想进行头删数据，肯定要先找到链表的头部，因为这个是有哨兵位的双向链表，链表的头直接通过哨兵位就能直接找到了。
2.  找到了之后肯定要判断一下是不是空链表，如果空链表的话就提示用户不能删除。
3.  判断完成之后就可以进行删除步骤了。（改变指针方向，链接，删除）

--------------------

#### 6、尾删数据 ####

代码：

void DListPopBack(DListNode* head)  //尾删数据
    {
    	assert(head);    //首先要判定一下传入的head 是不是空指针
    	if (head->next == head)  // 判断是不是空链表
    	{
    		printf("DEL error :Empty linked lists cannot be deleted");//如果是空链表则不能删除
    		return;
    	}
    	DListNode* Headprove = head->prove;  //尾删数据
    	DListNode* proveProve = Headprove->prove;//改变指针的方向
    	proveProve->next = head;
    	head->prove = proveProve;

代码解释：

1.  要想删除肯定要确保链表里面有东西可以删除，所以先判断一下是不是空链表，如果空链表的话就提示用户不能删除。
2.  尾删数据的时候，最关键的还是找尾部节点（这个步骤跟上面的尾插一样的）
3.  找到尾部节点以后进行删除。
    
    --------------------

#### 7、查找数组（返回查找数据的地址） ####

代码：

DListNode* DListFind(DListNode* head, DLTDateType x)   //查找链表中的X值，返回该节点的地址
    {
    	DListNode* cup = head->next;  //利用局部变量来记录链表的表头，方便后面的遍历
    	while (cup != head)     //遍历链表
    	{
    		//cup = cup->next;
    		if (cup->data == x)
    		{
    			return cup;
    		}
    		cup = cup->next;   //局部变量自增
    	}
    	printf("Not found\n");
    	return NULL;
    }

--------------------

#### 8、在链表X数据之后插入y ####

代码：

void DListInsertAfter(DListNode* head, DLTDateType x, DLTDateType y)   //X位置之后插入y
    {
    	DListNode* pos = DListFind(head, x);
    	DListNode* newnode = BuyDListNode(x);
    	newnode->data = y;
    	DListNode* next = pos->next;
    	next->prove = newnode;
    	newnode->next = next;
    	newnode->prove = pos;
    	pos->next = newnode;
    }

--------------------

#### 9、在链表X数据之前插入y ####

代码：

void DListInsertBefor(DListNode* head, DLTDateType x, DLTDateType y)   //X位置之前插入y
    {
    
    	DListNode* pos = DListFind(head, x);
    	DListNode* newnode = BuyDListNode(x);
    	newnode->data = y;
    	DListNode* prove = pos->prove;
    	prove->next = newnode;
    	newnode->prove = prove;
    	newnode->next = pos;
    	pos->prove = newnode;
    }

--------------------

#### 10、把链表中的X值修改为y ####

代码；

DListChange(DListNode* head, DLTDateType x, DLTDateType y)   修改在X位置的值
    {
    	DListNode* pos = DListFind(head, x);
    	assert(pos);
    	pos->data = y;  
    }

--------------------

#### 11、把链表中X值所在的结点删除 ####

void DListErase(DListNode* head, DLTDateType x)  // 链表删除pos位置的值
    {
    	DListNode* pos = DListFind(head, x);
    	assert(pos);
    	DListNode* prove = pos->prove;
    	DListNode* next = pos->next;
    	prove->next = next;
    	next->prove = prove;
    }

#### 12、把链表中X值之前的一个结点删除 ####

void DListEraseBefore(DListNode* head, DLTDateType x)  // 链表删除pos位置之前的值
    {
    	DListNode* pos = DListFind(head, x);
    	assert(pos);
    	DListErase(head, pos->prove->data);
    }

#### 13、把链表中X值之后的一个结点删除 ####

void DListEraseAfter(DListNode* head, DLTDateType x)  // 链表删除pos位置之后的值
    {
    	DListNode* pos = DListFind(head, x);
    	assert(pos);
    	DListErase(head, pos->next->data);
    }

#### 14、链表的销毁 ####

void DListDestroy(DListNode* head)  // 链表的销毁
    {
    	DListNode* cup = head->next;
    	while (cup != head)
    	{
    		DListNode* pos = cup;
    		cup = cup->next;
    		free(pos);
    		pos = NULL;
    	}
    }

[aba8670b0ba84fed8a396d2d73d6d6b6.png]: https://img-blog.csdnimg.cn/aba8670b0ba84fed8a396d2d73d6d6b6.png
[5c0855fce268427f9f5b6be1ac68fbba.png]: https://img-blog.csdnimg.cn/5c0855fce268427f9f5b6be1ac68fbba.png
[37b5386f0f464e76ab0223a8c7b2a2e7.png]: https://img-blog.csdnimg.cn/37b5386f0f464e76ab0223a8c7b2a2e7.png
[120ab5d02af7477aab25dd0718871918.png]: https://img-blog.csdnimg.cn/120ab5d02af7477aab25dd0718871918.png
[87c8463bcb9b4fac8695104bdd31646c.png]: https://img-blog.csdnimg.cn/87c8463bcb9b4fac8695104bdd31646c.png