开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构_双链表 -> 正文阅读

[数据结构与算法]数据结构_双链表

传送门：博客汇总帖

本文部分内容来自于公众号技术让梦想更伟大

文章目录

双链表
1、双链表节点的设计
2、双链表的创建
3、节点的插入
3.1、直接在尾部进行插入
3.2、指定位置进行插入

4、双链表的遍历
5、双链表的删除
6、源码

双链表

单链表是指结点中只有一个指向其后继的指针，具有单向性，但是有时需要搜索大量数据的时候，就需要多次进行从头开始的遍历，这样的搜索就不是很高效了。

在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表，就产生了双向链表的概念了。

双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

在这里插入图片描述

1、双链表节点的设计

在这里插入图片描述
其中，DATA表示数据，其可以是简单的类型也可以是复杂的结构体；

pre代表的是前驱指针，它总是指向当前结点的前一个结点，

next代表的是后继指针，它总是指向当前结点的下一个结点。

其代码实现如下：↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

typedef struct listNode
{
	int data;			// 	数据域
	struct listNode *next;		//  向后的指针
	struct listNode *previous;		//  向前的指针
    /* data */
}linklist,*linkptr;

2、双链表的创建

创建双向链表需要先创建头结点，将头节点的前驱、后继指针设置为NULL，并且返回节点指针，此时节点就创建好了。


/**
 * @description: 创建一个空链表（实际只包含了一个空节点）
 * @param {*}
 * @return {*}linkptr:链表指针
 */
linkptr link_create(void)
{
    linkptr list;
    if ((list = (linkptr)malloc(sizeof(linklist))) == NULL)   
    {
        printf("%s %d:malloc error\n",__FILE__,__LINE__);        
        return NULL;
        /* code */
    }
    list->next = list->previous = NULL;
    return list;
}

3、节点的插入

3.1、直接在尾部进行插入

由于双链表头节点可以有数据，所以这里我将头节点的前驱指针指向了自身。用来区分头节点和其他节点的不同，因为我是先创建了头节点（linkptr link_create(void)）。然后在在另一个函数进行节点的插入（void link_insert(linkptr list,int value)）。如果节点的前驱指针与后继指针都是NULL，证明此时链表只有一个空的头节点。

/**
 * @description: 将新数据插入到头结点后面
 * @param {linkptr} list 链表指针
 * @param {int} value   data
 * @return {*}  无
 */
void link_insert(linkptr list,int value)
{
    linkptr new_node;
    /** 首先判断头节点的 前驱指针和后继指针 是否为空，
     *  如果为空，证明此时双链表只有一个空的头节点，就将数据直接插入头节点即可
     */
    if ((list->next == NULL)&&(list->previous == NULL))   
    {
        list->data = value;
        list->previous = list;   //将头节点的前驱指针指向自己
        return ;
        /* code */
    }

    if ((new_node = (linkptr)malloc(sizeof(linklist))) == NULL)
    {
        printf("%s %d:malloc error\n",__FILE__,__LINE__);    
        return ;    
        /* code */
    }
    new_node->next = new_node->previous = NULL;
    new_node->data = value;
    while (list->next)
    {
        list = list->next;
        /* code */
    }
    list->next = new_node;
    new_node->previous = list;
    new_node->next = NULL;
}

3.2、指定位置进行插入


/**
 * @description: 在双向链表的固定位置插入节点（这里以位置1开始（头节点为位置0））(插入在位置一后面)
 * @param {linkptr} list : 链表指针
 * @param {int} local    ：要插入的位置
 * @param {int} value   ： 节点数据
 * @return {*}
 */
void link_insert_local(linkptr list, int local,int value)
{
    linkptr new_node;
    int j = 0;
    if ((new_node = (linkptr)malloc(sizeof(linklist))) == NULL)
    {
        printf("%s %d:malloc error\n", __FILE__, __LINE__);
        return;
        /* code */
    }
    while (j < local)
    {
        j+=1;
        list = list->next;
        /* code */
    }

    new_node->data = value;
    new_node->next = new_node->previous = NULL;

    if (list->next == NULL)   //这里判断一下，如果插入位置是在最后则下面的方法不适用，所以进判断。
    {
        list->next = new_node;
        new_node->previous = list;
        new_node->next = NULL;
        return;
        /* code */
    }
    new_node->next = list->next;
    list->next->previous = new_node;

    list->next = new_node;
    new_node->previous = list;
}

4、双链表的遍历

这里不能写list->next,因为最后一个节点的next指针为NULL。

/**
 * @description:  链表的遍历
 * @param {linkptr} list
 * @return {*}
 */
void link_show(linkptr list)
{
    while (list)
    {
        printf(" %d ", list->data);
        list = list->next;
        /* code */
    }
}

5、双链表的删除

在这里插入图片描述

删除操作的过程是：选择需要删除的结点->选中这个结点的前一个结点->将前一个结点的next指针指向自己的下一个结点->选中该节点的下一个结点->将下一个结点的pre指针修改指向为自己的上一个结点。

在进行遍历的时候直接将这一个结点给跳过了，之后，我们释放删除结点，归还空间给内存，

/**
 * @description: 删除节点
 * @param {linkptr} list
 * @param {int} local 位置（从0开始）
 * @return {*}
 */
void link_delete(linkptr list,int local)
{
    int j = 0;
    while (j < local)
    {
        j+=1;
        list = list->next;
        /* code */
    }
    list->previous->next = list->next;
    list->next->previous = list->previous;
    free(list);   //节点删除，应该free内存空间
}

6、源码


/*
 * @Author: Mr.Dragon
 * @Date: 2021-09-02 23:21:23
 * @LastEditTime: 2021-09-03 21:58:39
 * @LastEditors: Mr.Dragon
 * @Description: Fall_down:所念皆星河
 */
#include "stdio.h"
#include "stdlib.h"

typedef struct listNode
{
    int data;                  // 	数据域
    struct listNode *next;     //  向后的指针
    struct listNode *previous; //  向前的指针
    /* data */
} linklist, *linkptr;

/**
 * @description: 创建一个空链表（实际只包含了一个空节点）
 * @param {*}
 * @return {*}linkptr:链表指针
 */
linkptr link_create(void)
{
    linkptr list;
    if ((list = (linkptr)malloc(sizeof(linklist))) == NULL)
    {
        printf("%s %d:malloc error\n", __FILE__, __LINE__);
        return NULL;
        /* code */
    }
    list->next = list->previous = NULL;
    return list;
}

/**
 * @description: 将新数据插入到头结点后面
 * @param {linkptr} list 链表指针
 * @param {int} value   data
 * @return {*}  无
 */
void link_insert(linkptr list, int value)
{
    linkptr new_node;
    /** 首先判断头节点的 前驱指针和后继指针 是否为空，
     *  如果为空，证明此时双链表只有一个空的头节点，就将数据直接插入头节点即可
     */
    if ((list->next == NULL) && (list->previous == NULL))
    {
        list->data = value;
        list->previous = list; //将头节点的前驱指针指向自己
        return;
        /* code */
    }

    if ((new_node = (linkptr)malloc(sizeof(linklist))) == NULL)
    {
        printf("%s %d:malloc error\n", __FILE__, __LINE__);
        return;
        /* code */
    }
    new_node->next = new_node->previous = NULL;
    new_node->data = value;
    while (list->next)
    {
        list = list->next;
        /* code */
    }
    list->next = new_node;
    new_node->previous = list;
    new_node->next = NULL;
}
/**
 * @description:  链表的遍历
 * @param {linkptr} list
 * @return {*}
 */
void link_show(linkptr list)
{
    while (list)
    {
        printf(" %d ", list->data);
        list = list->next;
        /* code */
    }
}

/**
 * @description: 在双向链表的固定位置插入节点（这里以位置1开始（头节点为位置0））(插入在位置一后面)
 * @param {linkptr} list : 链表指针
 * @param {int} local    ：要插入的位置
 * @param {int} value   ： 节点数据
 * @return {*}
 */
void link_insert_local(linkptr list, int local,int value)
{
    linkptr new_node;
    int j = 0;
    if ((new_node = (linkptr)malloc(sizeof(linklist))) == NULL)
    {
        printf("%s %d:malloc error\n", __FILE__, __LINE__);
        return;
        /* code */
    }
    while (j < local)
    {
        j+=1;
        list = list->next;
        /* code */
    }

    new_node->data = value;
    new_node->next = new_node->previous = NULL;

    if (list->next == NULL)   //这里判断一下，如果插入位置是在最后则下面的方法不适用，所以进判断。
    {
        list->next = new_node;
        new_node->previous = list;
        new_node->next = NULL;
        return;
        /* code */
    }
    new_node->next = list->next;
    list->next->previous = new_node;

    list->next = new_node;
    new_node->previous = list;
    
}

/**
 * @description: 删除节点
 * @param {linkptr} list
 * @param {int} local 位置（从0开始）
 * @return {*}
 */
void link_delete(linkptr list,int local)
{
    int j = 0;
    while (j < local)
    {
        j+=1;
        list = list->next;
        /* code */
    }
    list->previous->next = list->next;
    list->next->previous = list->previous;
    free(list);   //节点删除，应该free内存空间
}

int main(void)
{
    linkptr link;
    link = link_create();

    printf("\n||----------插入数据测试(10,20,30)--------------||\n");
    link_insert(link, 10);
    link_insert(link, 20);
    link_insert(link, 30);
    link_show(link);

    printf("\n||------插入节点测试（在第一个节点(0开始)后面插入66）----------||\n");
    link_insert_local(link,1,66);
    link_show(link);

    printf("\n||------删除节点测试（删除第2个节点，就是data=66）----------||\n");
    link_delete(link,2);
    link_show(link);


    return 0;
}