双向链表

最新推荐文章于 2021-08-13 20:02:15 发布
最新推荐文章于 2021-08-13 20:02:15 发布
阅读量644 收藏 5
点赞数
分类专栏： 数据结构 文章标签： 链表 单链表 结构 双向链表 线性表
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/forwardyzk/article/details/53573897
版权

双向链表

  • 定义
  • 结构体
  • 创建一个双向链表
  • 展示双向链表中的数据元素
  • 查找双向链表中指定位置的结点
  • 向双向链表中指定位置插入结点
  • 删除双向列表指定位置的的结点

1.定义

循环链表和双向链表是对单链表的改进,仍属于链存储结构


双向链表的结点包括一个数据域和两个指针域,后继指针和前继指针域


双向链表的后继链和前继首尾相连,为空双向链表,又称双向循环链表


双向链表是一种对称结构,提供了向前搜索和向后搜索两种机会,操作插入和删除操作更加便利

前驱指针结点数据后继指针

2.结构体

创建结构类型,在DoubleCs.c文件中

/*
 双向链表结构体
 */
typedef struct dnode{
    int data;
    struct  dnode *prior,*next;
}DOUBLELINKLIST;

3.创建一个双向链表

在DoubleLinkList.h写出方法声明

#include "DoubleCs.c"

/*
 创建一个双向链表
 */
DOUBLELINKLIST * createDoubleLinkList();

在DoubleLinkList.c中实现此方法


#include "DoubleLinkList.h"
#include <stdlib.h>
#include <stdio.h>

/*
 创建一个双向链表
 */
DOUBLELINKLIST * createDoubleLinkList(){
    //1.创建一个头结点
    DOUBLELINKLIST * SQ;
    SQ=(DOUBLELINKLIST *) malloc(sizeof(DOUBLELINKLIST));
    SQ->data=-1;
    SQ->prior=NULL;
    SQ->next=NULL;

    //2.将其赋值给一个结点,供返回
    DOUBLELINKLIST *headDoubleLinkList=NULL;
    //3.循环添加结点
    DOUBLELINKLIST *tempNode;
    int  x=1;
    while (x<=10) {
        //3.1初始化添加的结点
        tempNode=(DOUBLELINKLIST *)malloc(sizeof(DOUBLELINKLIST));
        //3.2设置data数据
        tempNode->data=x;
        //3.3设置添加结点的前指针域值为SQ
        tempNode->prior=SQ;
        //3.4设置添加结点的后指针域值为NULL
        tempNode->next=NULL;
        //3.5设置链表的后指针域值为添加的结点
        SQ->next=tempNode;
        if(x==1){
            //这是为了保存了头结点,供后面返回
            headDoubleLinkList=SQ;
        }
        //3.6将临时结点赋给SQ,为了继续在后面继续添加(尾插入加载)
        SQ=tempNode;
        //4.数据自增
        x++;
    }
    return headDoubleLinkList;
}

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include "DoubleLinkList.h"
int main(int argc, const char * argv[]) {
    //创建一个双向链表
    printf("创建一个双向链表\n");
    DOUBLELINKLIST *createList=createDoubleLinkList();
    if(createList!=NULL){
        printf("创建双向链表成功success\n");
    }
}

打印结果:

创建一个双向链表
创建双向链表成功success

4.展示双向链表中的数据元素

在DoubleLinkList.h写出方法声明

#include "DoubleCs.c"
/*
 展示双向链表中的数据元素
 */
void showDoubleLinkList(DOUBLELINKLIST *SQ);

在DoubleLinkList.c中实现此方法


#include "DoubleLinkList.h"
#include <stdlib.h>
#include <stdio.h>

void showDoubleLinkList(DOUBLELINKLIST *SQ){
    if(SQ==NULL){
        printf("list=[链表为NULL]");
        return;
    }

    printf("list=[");
    printf("%d",SQ->data);
    while (SQ->next!=NULL) {
        SQ=SQ->next;
        printf(",%d",SQ->data);
    }
    printf("]\n");

}

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include "DoubleLinkList.h"
int main(int argc, const char * argv[]) {
    //展示链表中数据
    printf("输出双向链表数据\n");
    showDoubleLinkList(createList);
    printf("\n");
}

打印结果:

输出双向链表数据
list=[-1,1,2,3,4,5,6,7,8,9,10]

5.查找双向链表中指定位置的结点

在DoubleLinkList.h写出方法声明

#include "DoubleCs.c"
/*
 查找双向链表中指定位置的结点 
 */
DOUBLELINKLIST * findDoubleLinkListByPosition(DOUBLELINKLIST *SQ, int  position);

在DoubleLinkList.c中实现此方法


#include "DoubleLinkList.h"
#include <stdlib.h>
#include <stdio.h>
DOUBLELINKLIST * findDoubleLinkListByPosition(DOUBLELINKLIST *SQ, int  position){
    //1.保证SQ是使用的头结点指针,这样才能保证是顺序查找指定位置的节点
    if(SQ==NULL || SQ->next==NULL || position<=0){
        return NULL;
    }
    int  i=0;

    while (SQ!=NULL && position!=i) {
        i++;
        SQ=SQ->next;
    }
    return SQ;
}

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include "DoubleLinkList.h"
int main(int argc, const char * argv[]) {
   //查找双向链表中指定位置的结点
    printf("查找双向链表中指定位置的结点\n");
    DOUBLELINKLIST *findList=createDoubleLinkList();
    showDoubleLinkList(findList);
    int  findPosition=3;
    DOUBLELINKLIST *findNode=findDoubleLinkListByPosition(findList, findPosition);

    if(findNode==NULL){
        printf("list中不存在 %d 结点\n",findPosition);
    }else{
        printf("list中已经找到 %d 位置的结点,data=%d\n",findPosition,findNode->data);
    }
    printf("\n");
}

打印结果:

查找双向链表中指定位置的结点
list=[-1,1,2,3,4,5,6,7,8,9,10]
list中已经找到 3 位置的结点,data=3

6.向双向链表中指定位置插入结点

在DoubleLinkList.h写出方法声明

#include "DoubleCs.c"


/*
 向双向链表中指定位置插入结点
 */
DOUBLELINKLIST *insterDoubleLinkListByPosition(DOUBLELINKLIST *SQ,int position,int insterData);

在DoubleLinkList.c中实现此方法


#include "DoubleLinkList.h"
#include <stdlib.h>
#include <stdio.h>
DOUBLELINKLIST *insterDoubleLinkListByPosition(DOUBLELINKLIST *SQ,int position,int insterData){
    //1.链表的头结点赋给临时结点
    DOUBLELINKLIST *temp;
    temp=SQ;
    //2.查找到指定位置的节点
    DOUBLELINKLIST *Q2=findDoubleLinkListByPosition(temp, position);
    if(Q2==NULL){
        printf("未找到第 %d 结点",position);
        printf("添加失败failure\n");

        return SQ;
    }
    //3.找到插入位置的前一个结点
    DOUBLELINKLIST *Q1=Q2->prior;
    //4.模拟插入的节点
    DOUBLELINKLIST *P=(DOUBLELINKLIST *)malloc(sizeof(DOUBLELINKLIST));
    P->data=insterData;
    P->next=NULL;
    P->prior=NULL;
    //5.操作指针,将P插入链表中
    //5.1.把P的next指针指向Q2
    P->next=Q2;
    //5.2.把Q2的priop指针指向P
    Q2->prior=P;
    //5.3.把P的prior指针指向Q1
    P->prior=Q1;
    //5.4.把Q1的next指针指向P
    Q1->next=P;

    printf("添加成功\n");
    return SQ;
}

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include "DoubleLinkList.h"
int main(int argc, const char * argv[]) {
   //向双向链表中添加数据
    printf("向双向链表中添加数据\n");
    DOUBLELINKLIST *insertList=createDoubleLinkList();
    showDoubleLinkList(insertList);

    DOUBLELINKLIST *insertSuccessList= insterDoubleLinkListByPosition(insertList,7,77);
    showDoubleLinkList(insertSuccessList);
    printf("\n");
}

打印结果:

向双向链表中添加数据
list=[-1,1,2,3,4,5,6,7,8,9,10]
添加成功
list=[-1,1,2,3,4,5,6,77,7,8,9,10]

7.删除双向列表指定位置的的结点

在DoubleLinkList.h写出方法声明

#include "DoubleCs.c"
/*
 删除双向列表指定位置的的结点
 */
DOUBLELINKLIST * deleteDoubleLinkListByPosition();

在DoubleLinkList.c中实现此方法


#include "DoubleLinkList.h"
#include <stdlib.h>
#include <stdio.h>

/*
 删除双向列表指定位置的的结点
 */
DOUBLELINKLIST * deleteDoubleLinkListByPosition(DOUBLELINKLIST *SQ,int position){

    //1.链表的头结点赋给临时结点
    DOUBLELINKLIST *temp;
    temp=SQ;
    //2.查找到指定位置的节点
    DOUBLELINKLIST *deleteNode=findDoubleLinkListByPosition(temp, position);
    if(deleteNode==NULL){
        printf("未找到第 %d 结点\n",position);
        printf("删除失败failure\n");
        return SQ;
    }
    //3.获取删除结点的前一个结点
    DOUBLELINKLIST *Q1=deleteNode->prior;

    //4.获取删除节点的后一个结点
    DOUBLELINKLIST *Q3=deleteNode->next;

    //5.操作指针,删除deleteNode结点
     //5.1.将Q1的next指针指向deleteNode的后一个结点
    Q1->next=deleteNode->next;
    //5.2.将Q3的prior的指针指向Q1
    if(Q3==NULL){
        //表示删除的是最后一个节点,则不用操作Q3的pripr指针
    }else{
        Q3->prior=deleteNode->prior;
    }
    //6.释放删除的结点deleteNode
    free(deleteNode);

    printf("删除成功success\n");

    return SQ;
}

在main.c中的main方法(int main(int argc, const char * argv[]) {})调用此方法,并且进行判断

#include "DoubleLinkList.h"
int main(int argc, const char * argv[]) {

    //删除双向链表指定位置的结点
    printf("删除双向链表指定位置的结点\n");
    DOUBLELINKLIST *deleteList=createDoubleLinkList();
    showDoubleLinkList(deleteList);

    DOUBLELINKLIST *deleteSuccessList= deleteDoubleLinkListByPosition(deleteList,6);
    showDoubleLinkList(deleteSuccessList);
    printf("\n");
    }

打印结果:

删除双向链表指定位置的结点
list=[-1,1,2,3,4,5,6,7,8,9,10]
删除成功success
list=[-1,1,2,3,4,5,7,8,9,10]


这是对双向链表的基本操作,如有改善的地方,请大家提出,互相学习和进步.如果有好的关于数据结构与算法的书籍,还往大家推荐!

源码下载

【数据结构】双向链表定义和基本操作
Z_sea的博客
12-18 6008
双向链表： 双向链表的定义： typedef struct DuLNode{ LElemType data; struct DuLNode *next; struct DuLNode *pre; DuLNode ( LElemType Data=0,struct DuLNode *Pre=NULL,struct DuLNode *Next=NULL){ ...
数据结构——双向循环链表
wry_sunny_的博客
03-15 739
双向循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。双向循环链表的操作和双向链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。双向循环链表的头结点的前驱指向最后一个结点，尾结点的后继指向头结点。 注意：双向循环链表中无其他结点，只有头结点时 ，头结点的前驱和后继度指向自身。 1、双向循环链表的存储结构 t...
双链表相关资料
苏嵌——杭天龙
07-12 3507
转载自http://blog.sina.com.cn/s/blog_65380c300100ij1s.html 双链表 (2010-04-25 21:42:44) 转载▼ 标签： 杂谈 分类：C/C++ 双向链表 双向链表中，每个结点都有两个指针域，一个指向其后继结点，另一个指针指向其前驱结点，如图1.1(a)所示，因此，可以从某个结
双向链表数据结构
木子皿--啥都不会的菜鸟
03-16 502
文章目录1 双向链表数据结构1.1 链表结构定义1.2 链表操作实现 1 双向链表数据结构 1.1 链表结构定义 对于双向链表的通常做法： 我们可以使用更好的方案： 思考一个问题：已知父结构，如何访问特定结点？ 1.2 链表操作实现 链表的定义如下： #ifndef TLIB_H #define TLIB_H // 标准头文件，里面包含了常用的类型定义，如uint32_t #incl...
数据结构——双向链表
09-26 690
双向链表定义双链表就是在单链表结点上增添了一个指针域，指向当前结点的前驱。这样就可以方便的由其后继来找到其前驱，而实现输出终端结点到开始结点的数据序列。 同样，双链表也分为带头结点的双链表和不带头结点的双链表，情况类似于单链表。带头结点的双链表 head->next 为null的时候链表为空。不带头结点的双链表head为null的时候链表为空。 代码展示 public static void m
基础数据结构——双向链表
Sauron7i的博客
08-13 324
双向链表双链表的定义程序清单Dlist.hDlist.cppmain.cpp运行结果总结 双链表的定义 为什么要有双向链表? 因为单链表有自身局限性（只能向后跑，不能向前跑），所以当我们需要向前跑的时候，就有了双向链表。 双向链表是个啥？ 和单链表相比，多了一个直接前驱指针。 示例： 单链表（假设地址为100 200 这些。。。） 双向链表 程序清单 Dlist.h 头文件中除了结构体的定义和单链表不同，其他操作基本一样。 #pragma once //结构体定义 typedef int ElemTy
操作系统课设-线程安全的双向链表
04-25
操作系统课程设计中实现线程安全的双向链表是一项重要的实践任务，这涉及到多线程编程、数据结构以及并发控制等核心知识点。在这个项目中，我们主要关注如何在多线程环境下构建一个能够正确操作（如插入、删除）而不...
Python单向链表和双向链表原理与用法实例详解
09-20
在Python中，我们可以自定义链表结构来实现单向链表和双向链表。 单向链表（Single Linked List）的特点是每个节点只包含一个指向下一个节点的引用。在单向链表中，遍历只能从头节点开始，按顺序访问每个节点，无法...
创建双向链表_双向链表_
09-30
双向链表是一种特殊类型的数据结构，与常见的单向链表相比，它具有更丰富的操作能力，可以支持前后两个方向的遍历。本篇文章将深入探讨如何创建双向链表以及其在增加和删除操作中的应用。 双向链表的每个节点不仅...
双向链表.cpp 双向链表类定义及测试代码 c++
12-02
双向链表类定义及测试文件 对应于数据机构与算法分析（c++版）第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
python双向链表实现实例代码
12-25
python双向链表实现代码： 复制代码 代码如下:#!/usr/bin/python# -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList...
双向链表(结构体+指针)
肘子的博客
08-02 6138
首先当然得了解单向链表了 传送门 首先，表中的各个元素称作“结点”。双向链表的结点时结构体，有数据本体，指向前一元素的指针prev以及指向后一元素的指针next组成。这些结构体通过指针构成一个链表，就形成了双向链表。 struct node{ int key; node *prev,*next;//注意不是node *prev,next }; 另外，在表头设置一个特殊...
创建双向链表（详解）
热门推荐
Frank的博客
11-25 6万+
双向链表操作 在学习了单链表之后，就顺带学习了双链表的操作。 什么是双链表？ 双链表顾名思义，就是链表由单向的链变成了双向链。 使用这种数据结构，我们可以不再拘束于单链表的单向创建于遍历等操作，大大减少了在使用中存在的问题。 在单链表中，我们有一个数据域，还有一个指针域，数据域用来存储相关数据，而指针域则负责链表之间的“联系”。 而在双向链表中，我们需要有两个指针域，一个负责向后连接，一个负...
手写LinKedList双向链表 终于搞清了什么是链表结构
qq_33471403的博客
04-27 8452
之前对Collection这块底层实现和异同点一直模糊不清，最近手动写了个链表结构实现LinKedList ，发现很多知识还是要不断去实践，专研，才能不断提升。LinKedList 实现 List接口。链表结构图   a1,a2..都代表每个Node节点。1：新建一个自定义的节点package com.kiven.linKedList; public class Node&lt;E&gt; {...
数据结构学习之双向链表结构
落魄影子
12-10 1万+
注：本文的主要目的是为了记录自己的学习过程，也方便与大家做交流。转载请注明来自： http://blog.csdn.net/ab198604           在前面总结的单向链表结构的基础上，现在开始着手实践实践双向链表结构，如果充分理解了单向链表数据结构，那对双向链表结构的理解也就不再困难，换个角度而言，双向链表是单向链表的扩展，如果从数据结构代码的定义上来看，双向链表需要维护三个数据
数据结构之线性结构--双向链表
无_空
10-02 4560
一、双向链表在单链表中若需要查找某一个元素时，都必须从第一个元素开始进行查找，而双向链表除开头节点和最后一个节点外每个节点中储存有两个指针，这连个指针分别指向前一个节点的地址和后一个节点的地址，这样无论通过那个节点都能够寻找到其他的节点。 二、双向链表的基本操作双链表的删除除元素的时候需要注意的是，他有一个指向前驱指针和一个指向下一个节点的指针，当元素被删除时，上一个节点的指针会指向被删除节点的下
用结构体实现链表的创建、遍历、结点插入、结点删除、链表删除-----带菜单选项
smallgyy的专栏
03-08 5493
#include using namespace std; enum operation{create_List=1,print_List,insert_Node,delete_Node,delete_List,quit};//枚举类型，用于菜单选择结果 struct node //结点结构 { int data ; node * next; };
"双向链表"-数据结构算法-之通俗易懂,完全解析
农展飞的博客
06-21 1万+
1.节点的3个属性pre,data,next 2.头节点和尾节点head,rear 3.要完成迭代,需要让类继承Iterable,仿制迭代过程不可修改
数据结构：双向链表
qq_43824618的博客
03-09 622
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。 双向链表的实现代码 函数的声明：（头文件名DSeqList.h） #include<stdio.h> typedef int ElemType; typedef struct Node// 创建结点...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值