0
0

【数据结构】双向链表详解

在这里插入图片描述
当我们学习完单链表后，双向链表就简单的多了，双向链表中的头插，尾插，头删，尾删，以及任意位置插，任意位置删除比单链表简单，今天就跟着小张一起学习吧！！

双向链表的分类

双向不带头链表

在这里插入图片描述

双向带头循环链表

在这里插入图片描述

还有双向带头不循环链表，双向不带头循环链表，着重使用双向带头循环链表，带头也就是有哨兵位。

双向带头循环链表

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

双向循环链表的接口实现

ListNode*ListCreate(int x)//创建新结点
ListNode*createhead()//创建哨兵位voidListPushBack(ListNode* phead,int x)//尾插voidSListPrint(ListNode* phead)//打印链表voidSListPushFront(ListNode* phead,int x)//头插voidSListPopBack(ListNode* phead)//尾删voidSListPopFront(ListNode* phead)//头删voidSListInsert(ListNode* pos,int x)//pos前插voidSListErase(ListNode* pos)//删除pos;
ListNode*SListFind(ListNode* phead,int x)//查找链表中第一个x

0.结点结构体创建

typedefstructListNode{int data;//数据structListNode* next;//下个结点地址structListNode* prev;//上个结点地址}ListNode;

1.创建一个新结点

ListNode*ListCreate(int x)//创建新结点{
    ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));//给新结点申请空间if(newnode ==NULL){perror("malloc error");//没申请到，malloc返回NULL给newnode}
    newnode->data = x;//新结点的数据给x
    newnode->next =NULL;//新结点的下一个结点地址为空
    newnode->prev =NULL;//新结点的上一个结点地址为空return newnode;//新结点的地址返回回去}

2.创建哨兵位

该哨兵位作为链表的头结点，不存数据

ListNode*createhead(){
    ListNode* head =ListCreate(-1);//哨兵位结点的数据随便给个-1
    head->next = head;
    head->prev = head;return head;//返回哨兵位的头结点地址}

在这里插入图片描述当没有带数据的新结点时，先让他上一个结点地址，和下一关结点地址都存入head自己的地址

3.尾插

voidListPushBack(ListNode* phead,int x)//尾插{
    ListNode* newnode =ListCreate(int x);
    ListNode* tail = phead->prev;//记录尾结点的地址
    newnode->prev =tail;//新结点的prev存放尾结点的地址-1
    newnode->next = phead;//新结点的next存放头结点哨兵位的地址->2
    phead->prev = newnode;//头结点的prev存放新结点的地址->4
    tail->next = newnode;//尾结点的next存放新节点的地址->3}

分析：在这里插入图片描述
由于使用tail记录了尾结点的地址，所以1，2，3，4可以任意切换顺序，如果没有记录，记得先将新结点的prev,next,先保存，然后在修改head->prev, head->prev->next;防止修改过程中，尾结点的地址丢失。
在这里插入图片描述
同样适用于在哨兵位后插新结点

4.打印双链表

voidSListPrint(ListNode* phead)//打印链表{
    ListNode* cur = phead->next;while(cur != phead){printf("%d->", cur->data);
        cur = cur->next;}printf("\n");}

分析：定义一个指针cur遍历整个链表，由于是循环链表，肯定会指向哨兵位，哨兵位结点的数据不使用，所以cur指针从头节点哨兵位的下一个结点开始遍历，直到cur==phead,循环结束，每次打印cur->data,然后移动cur到下一个结点。

5.头插

voidSListPushFront(ListNode* phead,int x)//头插{
    ListNode* newnode =ListCreate(x);
    
    newnode->next = phead->next;
    phead->next->prev = newnode;
    newnode->prev = phead;
    phead->next = newnode;}

分析：在这里插入图片描述
注意：先保存newnode->next;和newnode->prev;
此时如果先进行4的话，phead->next的地址就变成了newnode,之前的phead->next地址丢失掉。
还有一种方法是先保存* next=phead->next;然后1，2，3，4，顺序可以调换。

6.尾删

voidSListPopBack(ListNode* phead)//尾删{
    ListNode* last = phead->prev->prev;//记录尾结点的上一个结点的地址
    phead->prev = last;//头节点哨兵位的prev存入last的地址
    last->next = phead;//last的next存入phead的地址}

分析：在这里插入图片描述当要删除尾结点，我们可以先记录尾结点的上一个结点的地址，因为要删除尾结点，改变就是将尾结点的上一个结点last的next存phead的地址，phead的prev存入的是last的地址
在这里插入图片描述除哨兵位还有一个结点的尾删剩下一个哨兵位头结点，同样适用上面的代码

7.头删

voidSListPopFront(ListNode* phead)//头删{
    ListNode* next = phead->next;
    phead->next = next->next;
    next->next->prev = phead;}

分析：在这里插入图片描述先保存哨兵位的下一个结点地址到next,然后将phead的next中存入next->next;将next->next->prev存入phead的首地址

8.pos指针指向的结点前插

voidSListInsert(ListNode* pos,int x)//pos前插{
    ListNode* newnode =ListCreate(x);//申请新结点将地址存放在newnode变量中
    newnode->next = pos;//新结点的下一个结点保存pos指针指向节点的地址
    newnode->prev = pos->prev;//新结点的prev保存pos指针指向的节点的上一个节点的地址
    pos->prev->next=newnode;//pos指针指向的节点的前一个结点的next保存newnode指针指向的结点
    pos->prev = newnode;//pos指针指向的结点的prev保存newnode指针指向结点的地址}

分析：在这里插入图片描述

9.删除pos指针指向的结点

voidSListErase(ListNode* pos)//删除pos;{
    ListNode* last = pos->prev;//记录pos指针指向结点的前一个结点地址
    ListNode* next = pos->next;//记录pos指针指向结点的后一个结点地址
    last->next = next;//操作1
    next->prev = last;//操作2}

分析：在这里插入图片描述

10.查找链表第一个出现的x

ListNode*SListFind(ListNode* phead,int x){
    ListNode* cur = phead->next;//cur指针先指向phead的下一个结点的位置while(cur != phead)//循环遍历{if(cur->data == x)//第一次找到{return cur;返回结点数据等于x的地址

        }
        cur = cur->next;//cur指针指向下一个结点}returnNULL;}

分析：类似于打印打印链表，遍历循环，从phead->next开始遍历，当cur不等于phead继续循环，如果cur->datax,就return cur的内容，也就是datax的结点地址，循环结束没有找到的话，就是该链表没有等于x的结点返回NULL;

11.双向链表的销毁

voidDestroy(ListNode* phead){
    
    ListNode* cur = phead->next;while(cur != phead){
        ListNode* next = cur->next;free(cur);
        cur = next;}free(phead);}

分析，定义一个指针cur先指向phead的下一个结点，开始遍历，先保存cur指向结点的下一个结点的地址到next,然后释放掉cur指针指向的空间，然后让cur指向已经保存在next中下一个结点的地址，依次循环释放掉所有的结点，循环结束，释放掉哨兵位。

12.完整源码

#include<stdio.h>#include<stdlib.h>typedefstructListNode{int data;structListNode* next;structListNode* prev;}ListNode;
ListNode*ListCreate(int x)//创建新结点{
    ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));if(newnode ==NULL){perror("malloc error");//return;}
    newnode->data = x;
    newnode->next =NULL;
    newnode->prev =NULL;return newnode;}
ListNode*createhead(){
    ListNode* head =ListCreate(-1);
    head->next = head;
    head->prev = head;return head;}voidListPushBack(ListNode* phead,int x)//尾插{
    ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));
    newnode->data = x;
    ListNode* tail = phead->prev;
    newnode->prev =tail;
    phead->prev = newnode;
    tail->next = newnode;
    newnode->next = phead;}voidSListPrint(ListNode* phead)//打印链表{
    ListNode* cur = phead->next;while(cur != phead){printf("%d->",cur->data);
        cur = cur->next;}printf("\n");}voidSListPushFront(ListNode* phead,int x)//头插{
    ListNode* newnode =ListCreate(x);
    
    newnode->next = phead->next;
    phead->next->prev = newnode;
    newnode->prev = phead;
    phead->next = newnode;}voidSListPopBack(ListNode* phead)//尾删{
    ListNode* last = phead->prev->prev;
    phead->prev = last;
    last->next = phead;}voidSListPopFront(ListNode* phead)//头删{
    ListNode* next = phead->next;
    phead->next = next->next;
    next->next->prev = phead;}voidSListInsert(ListNode* pos,int x)//pos前插{
    ListNode* newnode =ListCreate(x);
    

    newnode->next = pos;
    newnode->prev = pos->prev;
    pos->prev->next=newnode;
    pos->prev = newnode;}voidSListErase(ListNode* pos)//删除pos;{
    ListNode* last = pos->prev;
    ListNode* next = pos->next;
    last->next = next;
    next->prev = last;}
ListNode*SListFind(ListNode* phead,int x){
    ListNode* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}//双链表的销毁voidDestroy(ListNode* phead){
    
    ListNode* cur = phead->next;while(cur != phead){
        ListNode* next = cur->next;free(cur);
        cur = next;}free(phead);}intmain(){
    ListNode* list;
    list =createhead();printf("尾插:");ListPushBack(list,1);ListPushBack(list,2);ListPushBack(list,3);ListPushBack(list,4);SListPrint(list);printf("头插:");SListPushFront(list,8);SListPushFront(list,7);SListPushFront(list,6);SListPushFront(list,5);SListPrint(list);printf("尾删:");SListPopBack(list);SListPopBack(list);SListPrint(list);printf("头删:");SListPopFront(list);SListPopFront(list);SListPopFront(list);SListPrint(list);printf("插入pos指向结点前面:");SListInsert(list->next->next,1000);SListPrint(list);printf("删除pos指向的结点:");SListErase(list->next->next);SListPrint(list);printf("查找第一个x的位置并打印出来:");
    ListNode* p=SListFind(list,8);printf("%d", p->data);printf("修改查找到的结点:\n");
    p->data =10000;SListPrint(list);printf("销毁打印销毁后哨兵位的下一个结点的数据,如果为随机值说明已经被销毁：");Destroy(list);printf("%d",list->data);}

13.编译运行

在这里插入图片描述

标签： 数据结构 链表
本文转载自: https://blog.csdn.net/yyqzjw/article/details/132812838
版权归原作者 嘎嘎旺 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【数据结构】双向链表详解”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航