数据结构 —— 双向链表（超详细图解 & 接口函数实现）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构 —— 双向链表（超详细图解 & 接口函数实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

系列文章目录

数据结构 —— 顺序表
数据结构 —— 单链表
数据结构 —— 双向链表
数据结构 —— 队列
数据结构 —— 栈
数据结构 —— 堆
数据结构 —— 二叉树
数据结构 —— 八大排序

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一种十分优秀的解决实际问题的模板，是先进思想的结晶。博主将会用代码结合大量图解，对数据结构进行深度剖析，以便大家更好的学习数据结构的思想。

一、示例问题：城市对外回环交通

城市对外交通实现了从一个城市到另一个城市的道路，但今天所讨论的仅限于一个城市连接其他两个城市的回环交通结构。

1.城市回环交通

城市对外交通指的是城市与城市之间的交通，是连接城市与城市之间往返的重要路径

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

2.逻辑示意图

城市回环交通结构与本文将的内容极其相似，我们由城市的回环交通来引入双向带头循环链表

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

3.双向链表的引入

双向链表的引入：既能指向前一个节点又指向下一个节点存储内容地址

二、双向链表的概念

1.定义

链表：由 n 个节点链接成一个链表，即线性表的链式存储结构

双向链表：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱

节点：

我们把存储数据元素信息的域称为数据域。
存储数据元素之间的链接信息即下一个存储数据元素地址的部分称为指针域。
由数据域和指针域组成的数据元素a的存储映像称为节点。

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

2.结构

双向链表的结构类型

typedef int LTDateType;			//便于更改存储类型

typedef struct ListNode {		
    LTDateType data;			//数据域：存储数据元素信息
    struct ListNode *prev;		//指针域：存储上一个节点信息
    struct ListNode *next;		//指针域：存储下一个节点信息
} ListNode;

3.存储

存储：用动态开辟的sizeof(ListNode)大小的一块空间进行存储

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

三、双向链表的接口函数

1.动态申请空间

动态开辟一块sizeof(ListNode)大小的空间进行存储

// 动态申请一个结点
ListNode *BuyListNode(LTDateType x) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->data = x;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

2.创建哨兵位

创建返回链表的哨兵位

// 创建返回链表的哨兵位
ListNode *ListInit() {
    ListNode *pHead = BuyListNode(-1);
    pHead->prev = pHead;
    pHead->next = pHead;
    return pHead;
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

3.查找指定数据

双向链表查找指定数据

// 双向链表查找
ListNode *ListFind(ListNode *pHead, LTDateType x) {
    assert(pHead);

    ListNode *curr = pHead->next;
    while (curr != pHead) {
        if (curr->data == x) {
            return curr;
        }
        curr = curr->next;
    }
    return NULL;
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

4.指定位置插入

双向链表在指定位置 pos 插入 x

// 双向链表在pos位置插入x
void ListInsert(ListNode *pos, LTDateType x) {
    assert(pos);

    ListNode *newNode = BuyListNode(x);
    ListNode *prev = pos->prev;

    newNode->prev = prev;
    newNode->next = pos;
    prev->next = newNode;
    pos->prev = newNode;
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

5.指定位置删除

双向链表删除在指定位置 pos

// 双向链表在pos位置删除
void ListErase(ListNode *pos) {
    assert(pos);
    assert(pos != pos->next);

    pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

6.头部插入

双向链表在哨兵位之后的位置插入 x

// 双向链表头插
void ListPushFront(ListNode *pHead, LTDateType x) {
    ListInsert(pHead->next, x);
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

7.头部删除

双向链表删除哨兵位的后一个节点

// 双向链表头删
void ListPopFront(ListNode *pHead) {
    ListErase(pHead->next);
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

8.尾部插入

双向链表在哨兵位之前的位置插入 x

// 双向链表尾插
void ListPushBack(ListNode *pHead, LTDateType x) {
    ListInsert(pHead, x);
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

9.尾部删除

双向链表删除哨兵位的前一个节点

// 双向链表尾删
void ListPopBack(ListNode *pHead) {
    ListErase(pHead->prev);
}

数据结构 —— 双向链表（超详细图解 & 接口函数实现）

10.计算链表大小

计算双向链表的大小

// 计算大小
int ListSize(ListNode *pHead) {
    ListNode *curr = pHead->next;
    int size = 0;
    while (curr != pHead) {
        size++;
        curr = curr->next;
    }
    return size;
}

11.销毁链表

销毁双向链表，请手动置空

// 销毁(手动置空)
void ListDestory(ListNode *pHead) {
    ListNode *curr = pHead->next;
    while (curr != pHead) {
        ListNode *next = curr->next;
        free(curr);
        curr = next;
    }
    free(pHead);
}

四、总结

双向链表是解决实际问题时极其常用的一种数据结构，是非常重要的解决问题的方式。双向链表的各种接口的复现，有利于更好的学习数据结构的思想，有利于开阔视野，学习前辈的智慧结晶。对我们后续解决实际问题也会有很大帮助。文章来源地址https://www.toymoban.com/news/detail-502211.html

到了这里，关于数据结构 —— 双向链表（超详细图解 & 接口函数实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！