【数据结构初阶】--双向链表(一)

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。  

前言：在前面几篇博客中，我们实现了单链表，但是我们的链表其实并不止有单链表这一种形式，严格来说，单链表应该是叫不带头单向不循环链表。那么这篇文章，主要是给大家分享一下链表的分类以及双向链表实现的部分内容，实现形式依旧和之前一样。

---

目录

一.链表的分类与说明

1.单向或者双向

2.带头或者不带头

3.循环或者不循环

二.双向链表的定义

 三.双向链表中哨兵位头节点的初始化

四.代码展现

List.h:

List.c： 

test.c：

---

一.链表的分类与说明

--链表的结构非常多样，总共能组合出来8种

我们来一起了解一下这些特性吧

1.单向或者双向

双向链表分为前驱节点和后继节点，不仅能找到当前节点的下一个节点还可以找到上一个节点，使用起来也是很方便的。

2.带头或者不带头

带头链中的头节点，不存储任何有效数据，只用来站岗放哨，我们也称之为"哨兵位" 

在之前的单链表学习中，我们有时候也会把第一个节点表述为头节点，其实这个称呼是不严谨的只是为了方便理解。

3.循环或者不循环

循环链表的尾节点不会指向空，而是指向了第一个节点

虽然有这么多的链表结构，但我们实际中最常用的其实还是两种：单链表(不带头单向不循环链表)和双向链表(带头双向循环链表) ，那我们一起来继续学习双向链表吧

---

二.双向链表的定义

双向链表中由一个一个的节点组成，这里的节点有三个组成部分，定义我们放在.h文件中

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//前驱指针,指向前一个指针struct ListNode* prev;//后继指针，指向后一个指针struct ListNode* next;
}ListNode;

---

 三.双向链表中哨兵位头节点的初始化

--我们在双向链表中哨兵位的头节点是需要初始化一下的，数据随便给个不用的，然后前驱指针和后继指针都指向自己就可以了，具体操作如下所示：

//头节点初始化
void LTInit(ListNode** pphead)
{ListNode* ph = (ListNode*)malloc(sizeof(ListNode));if (ph==NULL){perror("malloc fail!");exit(1);}*pphead = ph;(*pphead)->data = -1;//随便给个不用的就行(*pphead)->prev = *pphead;(*pphead)->next = *pphead;
}

--这里需要用二级指针是因为我们修改了形参且需要改变实参，把原来的空变成哨兵位。

--利用调试发现初始化没有问题

---

四.代码展现

List.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//前驱指针,指向前一个指针struct ListNode* prev;//后继指针，指向后一个指针struct ListNode* next;
}ListNode;//初始化头节点
void LTInit(ListNode** pphead);

List.c： 

#include"List.h"//头节点初始化
void LTInit(ListNode** pphead)
{ListNode* ph = (ListNode*)malloc(sizeof(ListNode));if (ph==NULL){perror("malloc fail!");exit(1);}*pphead = ph;(*pphead)->data = -1;//随便给个不用的就行(*pphead)->prev = *pphead;(*pphead)->next = *pphead;
}

test.c：

#include"List.h"void test1()
{ListNode* plist = NULL;LTInit(&plist);
}
int main()
{test1();return 0;
}

---

往期回顾： 

【数据结构初阶】--单链表(一)

【数据结构初阶】--单链表(二)

结语：这篇博客中为大家简单介绍了下双向链表，实现了一下哨兵位头节点的初始化，再次提醒一下，大家一定要注意啥时候用一级指针，啥时候用二级指针。在下篇博客中，博主会继续和大家一起实现双向链表中的一些其它接口，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持。