精华内容
下载资源
问答
  • 文章目录前言一、双向带头循环链表1.双向带头循环链表结构1....今天就用C语言来实现一下带头双向链表的增删查改。 一、双向带头循环链表 1.双向带头循环链表结构 首先:来看一下双向带头循环链表的结构


    前言

    链表的结构有很多种,其中用的比较多的就是单向不带头不循环链表和双向带头循环链表,这两种链表都有各自应用的场合。
    双向带头循环链表结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。今天就用C语言来实现一下带头双向链表的增删查改。


    一、双向带头循环链表

    1.双向带头循环链表结构

    首先:来看一下双向带头循环链表的结构

    在这里插入图片描述
    可以看到双向带头循环链表的每一个节点都与前后相连接,因此组成了一个循环,要实现该结构,需要先创造一个头结点,该头结点的尾指针指向自己,头指针也指向自己,在此基础上实现其他节点的插入和删除。

    1.双向带头循环链表实现代码

    以下是代码部分:
    头文件
    ListNode.h

    #define pragama once
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    
    //typedef方便修改结构体变量的类型
    typedef int LTDataType;
    
    //构建链表结构体,结构体变量包括头指针,尾指针及data值
    typedef struct ListNode {
    	
    	struct ListNode* pre;
    	struct ListNode* next;
    	LTDataType data;
    
    }ListNode;
    
    //创建新节点
    ListNode* BuyListNode(LTDataType x);
    //链表初始化->创造头结点
    ListNode* InitListNode();
    //打印链表
    void ListPrint(ListNode* phead);
    //销毁链表
    void ListDistory(ListNode* phead);
    
    //增删查改
    void ListPushBack(ListNode* phead, LTDataType x);
    void ListPushFront(ListNode* phead, LTDataType x);
    void ListPopBack(ListNode* phead);
    void ListPopFront(ListNode* phead);
    ListNode* ListFind(ListNode* phead, LTDataType x);
    void ListInsert(ListNode* pos, LTDataType x);
    void ListErase(ListNode* pos);
    void Listchange(ListNode* pos, LTDataType x);
    

    主体
    ListNode.c

    #include"ListNode.h"
    
    
    
    ListNode* BuyListNode(LTDataType x)
    {
    	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    	newnode->data = x;
    	newnode->next = NULL;
    	newnode->pre = NULL;
    
    
    	return newnode;
    }
    
    
    ListNode* InitListNode()
    {
    	//构造头结点
    	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    	phead->next = phead;
    	phead->pre = phead;
    
    	return phead;
    }
    
    void ListPrint(ListNode* phead)
    {
    	assert(phead);
    
    	//从头结点后开始,到头结点结束
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		printf("%d", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    
    void ListDistory(ListNode* phead)
    {
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		ListNode* next = cur->next;
    		ListErase(cur);
    		cur = next;
    	}
    	free(phead);
    	phead = NULL;
    }
    
    //以下注释掉的代码段和留下的代码功能是一样的
    void ListPushBack(ListNode* phead, LTDataType x)
    {
    	/*assert(phead);
    
    	ListNode* newnode = BuyListNode(x);
    	ListNode* tail = phead->pre;
    
    	tail->next = newnode;
    	newnode->pre = tail;
    	newnode->next = phead;
    	phead->pre = newnode;*/
    	ListInsert(phead, x);
    }
    
    void ListPushFront(ListNode* phead, LTDataType x)
    {
    	/*assert(phead);
    
    	ListNode* next = phead->next;
    	ListNode* newnode = buyListNode(x);
    
    	newnode->next = next;
    	next->pre = newnode;
    	phead->next = newnode;
    	newnode->pre = phead;*/
    	ListInsert(phead->next, x);
    
    }
    
    void ListPopBack(ListNode* phead)
    {
    	/*assert(phead);
    	assert(phead->next != phead);
    	
    	ListNode* tail = phead->pre;
    	ListNode* tailpre = tail ->pre;
    	
    	tailpre->next = phead;
    	phead->pre = tailpre;
    	
    	free(tail);*/
    	ListErase(phead->pre);
    }
    
    void ListPopFront(ListNode* phead)
    {
    	/*assert(phead);
    	assert(phead->next != phead);
    	
    	ListNode* next = phead->next;
    	ListNode* newnext = next ->next;
    	
    	phead->next = newnext;
    	newnext->pre = phead;
    
    	free(next);*/
    	ListErase(phead->next);
    }
    
    ListNode* ListFind(ListNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		if (cur->data == x)
    		{
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }
    
    //POS之前插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
    	assert(pos);
    	ListNode* pospre = pos->pre;
    	ListNode* newnode = BuyListNode(x);
    	
    	pospre->next = newnode;
    	newnode->pre = pospre;
    	newnode->next = pos;
    	pos->pre = newnode;
    
    }
    //pos不能是phead! 否则会破坏双向链表的结构;
    void ListErase(ListNode* pos)
    {
    	assert(pos);
    	ListNode* pospre = pos->pre;
    	ListNode* posnext = pos->next;
    
    	pospre->next = posnext;
    	posnext->pre = pospre;
    	free(pos);
    }
    void Listchange(ListNode* pos, LTDataType x)
    {
    	assert(pos);
    	pos->data = x;
    }
    

    测试代码
    test.c

    #include"ListNode.h"
    
    
    void test()
    {
    	ListNode* phead = InitListNode();
    	ListPushBack(phead, 1);
    	ListPushBack(phead, 2);
    	ListPushBack(phead, 3);
    	ListPushBack(phead, 4);
    	ListPushBack(phead, 5);
    	ListPushFront(phead, 6);
    	ListPrint(phead);
    
    	ListNode* pos = ListFind(phead, 2);
    	ListInsert(pos, 8);
    	ListErase(pos);
    	ListPrint(phead);
    	ListNode* pos2 = ListFind(phead, 4);
    	Listchange(pos2, 9);
    
    	//ListDistory(phead);
    	ListPrint(phead);
    
    }
    int main()
    {
    	test();
    	return 0;
    }
    

    运行结果
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210202194546953.png

    二、双向带头循环链表优缺点

    以下双向循环列表的优缺点都是与顺序表和单向不循环链表相比较的,因此同时总结了了下顺序表的优缺点。

    1.双向带头循环链表优缺点

    • 优点:支持任意位置时间复杂度为O(1)的插入和删除,不需要扩容、不存在空间浪费。
    • 缺点:不支持随机访问,缓存命中率相对低。

    2.顺序表优缺点

    优点:

    • 相对而言空间利用率更高,不需要额外空间,占用空间小(链表需要存指针)。
    • 物理空间是连续的。支持随机访问,可以用下标访问(最大优势);缓存命中率较高。

    缺点:

    • 头部或中间插入或删除数据,需要一个一个挪动数据,时间复杂度是O(N)。
    • 空间不够时需要增容,一般增容是按照倍数增加的、因此可能存在一定内存浪费。
    展开全文
  • Java 双向链表总结

    2019-10-18 16:25:48
    1.双向链表的操作分析和实现 1.管理单向链表的缺点分析 1)单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找 2)单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面...

    1.双向链表的操作分析和实现

    1.管理单向链表的缺点分析
    1)单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找
    2)单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面我们单链表删除节点,总是找到temp,temp是待删除节点的前一个节点。
    2.思路分析
    在这里插入图片描述
    1)遍历和单链表不一样,不止可以向前,也可以向后查找
    2)添加(默认添加到双向链表的最后)
    ① 先找到双向链表的最后这个节点
    ②temp.next = newHeroNode
    ③newHeroNode.pre = temp;
    3)修改思路和单链表一样
    4)删除
    ①因为是双向链表,因此我们可以实现自我删除某个节点
    ②直接找到要删除的这个节点,比如temp
    ③temp.pre.next = temp.next;
    ④ temp.next.pre = temp.pre;

    package com.atguigu.linkedlist;
    
    public class DoubleLinkedListDemo {
        public DoubleLinkedListDemo() {
        }
    
        public static void main(String[] args) {
            //测试
            System.out.println("双向链表的测试");
            //先创建节点
            HeroNode2 hero1=new HeroNode2(1,"宋江","及时雨");
            HeroNode2 hero2=new HeroNode2(2,"吴用","智多星");
            HeroNode2 hero3=new HeroNode2(3,"李逵","黑旋风");
            HeroNode2 hero4=new HeroNode2(4,"林冲","豹子头");
            //创建一个双向链表
            DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
            doubleLinkedList.add(hero1);
            doubleLinkedList.add(hero2);
            doubleLinkedList.add(hero3);
            doubleLinkedList.add(hero4);
    
            doubleLinkedList.list();
    
            //修改
            HeroNode2 newHeroNode = new HeroNode2(4,"公孙胜","入云龙");
            doubleLinkedList.update(newHeroNode);
            System.out.println("修改后的链表情况");
            doubleLinkedList.list();
    
            //删除
            doubleLinkedList.del(3);
            System.out.println("删除后的链表情况");
            doubleLinkedList.list();
        }
    
    
    }
    
    //创建一个双向链表的类
    class DoubleLinkedList{
        //先初始化一个头节点,头节点不要动,不存放具体的数据
        private HeroNode2 head = new HeroNode2(0,"","");
        //返回头节点
        public HeroNode2 getHead()
        {
            return head;
        }
        //遍历双向链表
        //显示链表【遍历】
        public void list(){
            //判断链表是否为空
            if (head.next == null){
                System.out.println("链表为空");
                return;
            }
            //因为头节点不能动,因此我们需要一个辅助遍量来遍历
            HeroNode2 temp = head.next;
            while (true){
                //判断是否到链表最后
                if (temp == null){
                    break;
                }
                //输出节点的信息
                System.out.println(temp);
                //将next后移,一定
                temp = temp.next;
            }
        }
        //添加一个节点到双向链表的最后
        public void add(HeroNode2 heroNode){
            //head不能动,因此我们需要一个辅助遍历temp
            HeroNode2 temp = head;
            //遍历链表,找到最后
            while (true){
                //找到链表的最后
                if (temp.next == null){
                    break;
                }
                //如果没有找到最后,将temp后移
                temp = temp.next;
            }
            //当退出while循环时,temp就指向了链表的最后
            //形成一个双向链表
            temp.next = heroNode;
            heroNode.pre = temp;
        }
    
        //修改一个节点的内容,可以看到双向链表的系欸点内容修改和单向链表一样
        public  void update(HeroNode2 newHeroNode){
            //判断是否空
            if (head.next == null){
                System.out.println("链表为空~");
                return;
            }
            //找到需要修改的节点,根据no编号
            //定义一个辅助变量
            HeroNode2 temp = head.next;
            boolean flag = false;//表示是否找到该节点
            while (true){
                if (temp == null){
                    break;//已经遍历完链表
                }
                if (temp.no == newHeroNode.no){
                    //找到
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            //根据flag判断是否找到要修改的节点
            if (flag){
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
    
            }else {
                System.out.printf("没有找到编号 %d 的节点,不能加入 \n",newHeroNode.no);
            }
        }
    
        //删除节点
        //对于双向链表,我们直接找到要删除的节点,找到后自我删除即可
        public void del(int no) {
    
            //判断当前链表是否为空
            if (head.next == null) {//空链表
                System.out.println("链表为空,无法删除");
                return;
            }
            HeroNode2 temp = head.next;//辅助指针
            boolean flag = false;//标志是否找到待删除节点的
            while (true) {
                if (temp == null) {//已经到链表的最后
                    break;
                }
                if (temp.no == no) {
                    //找到的待删除节点的前一个节点temp
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            //判断flag
            if (flag) {//找到
                //可以删除
                //temp.next = temp.next.next;
                temp.pre.next = temp.next;
                //有问题:如果是最后一个节点,就不需要执行下面这句话,否则出现空指针
                // temp.next=null.next
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                } else {
                    System.out.printf("要删除的 %d 节点不存在", no);
                }
    
            }
        }
    
    //定义HeroNode2,每个HeroNode对象就是一个节点
     class HeroNode2 {
    
        public int no;
        public String name;
        public String nickname;
        public HeroNode2 next; //指向下一个节点,默认为null
        public HeroNode2 pre;//指向下一个节点,默认为null
    
        //构造器
        public HeroNode2(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }
    
    
        @Override
        public String toString() {
            return "HeroNode2{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
    }
    
    展开全文
  • 单向链表和双向链表优缺点及使用场景

    万次阅读 多人点赞 2018-09-28 16:16:39
    双向链表:有两个指针,一个指向前一个节点,一个后一个节点。 优点:可以找到前驱和后继,可进可退; 缺点:增加删除节点复杂,需要多分配一个指针存储空间。 适用于需要双向查找节点值的情况。 ...

    单向链表:只有一个指向下一个节点的指针。

    优点:单向链表增加删除节点简单。遍历时候不会死循环;

    缺点:只能从头到尾遍历。只能找到后继,无法找到前驱,也就是只能前进。

    适用于节点的增加删除。

     

    双向链表:有两个指针,一个指向前一个节点,一个后一个节点。

    优点:可以找到前驱和后继,可进可退;

    缺点:增加删除节点复杂,需要多分配一个指针存储空间。

    适用于需要双向查找节点值的情况。

    展开全文
  • 1、指向不bai同:单向链表只有du一个指向下一结点的指针,zhi双向链表除了有一个指dao向下一结点的指针外,还有一个指向前一结点的指针。...双向链表优缺点: 1、优点:可以找到前驱和后继,可进可退

    1、指向不bai同:单向链表只有du一个指向下一结点的指针,zhi双向链表除了有一个指dao向下一结点的指针外,还有一个指向前一结点的指针。

    2、功能不同:单向链表只能next ,双向链表可以return。

    3、单双向不同:单链表只能单向读取,双向链表可以通过prev()快速找到前一结点。

    单向链表优缺点:

    1、优点:单向链表增加删除节点简单。遍历时候不会死循环;

    2、缺点:只能从头到尾遍历。只能找到后继,无法找到前驱,也就是只能前进。

    双向链表优缺点:

    1、优点:可以找到前驱和后继,可进可退;

    2、缺点:增加删除节点复杂,多需要分配一个指针存储空间。

    展开全文
  • 线性表 遍历查找比较简便 插入删除很复杂 链表 跟线性表相反 链表的分类有,单链表,双向链表,循环链表 双向链表就是每一个结点有两个指针pre和next指针,分别指向前驱结点和后继结点
  • 顺序表优点: 1.按下标进行随机访问(比如二分查找,和方便一些排序) 顺序表缺点 1.空间不够需要增容(增容其实算是...链表缺点 1.不支持按下标随机访问 总结:两数据结构是相辅相成的,没有谁是完美的...
  • 数据结构之双向链表地 Java 实现 单链表只能从前往后遍历 ,如果链表地长度较大 , 遍历到链表后半部分地时候想 要往前查找 ,就只能回到开头 ,重新遍历了 . 双向链表提供了这个能力 , 即允许前向遍历 , 也允许后向遍历...
  • 数组与链表优缺点

    2020-10-19 11:03:39
    数组和链表是我们在开发过程中最常见的数据结构(树:“有被冒犯到!”),面试种惊颤有提到的数组查询快,增删慢;链表查询慢,增删快 那么,为什么哪?我们今天就来一个追根探底。 首先,我们需要明确一点,数组...
  • 双向链表的使用

    2020-11-05 15:59:23
    1.单向链表和双向链表优缺点的分析 1.单向链表查找的方向只能是一个方向,而双向链表可以向前或者向后查找 2.单向链表不能自我删除,需要借助辅助节点,而双向链表,则可以实现自我删除,所以,单链表删除节点时,...
  • 前言单向链表和双向链表优缺点及使用场景双向链表的简单实现及图示分析 前言 之前写了一些文章简单地介绍顺序表,链表的基础知识,还总结了几道链表的笔试题,今天继续开干,向老铁们简单地介绍一下无头双向循环...
  • java实现双向链表

    2020-08-16 15:31:04
    单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以在单链表删除时节点,总是找到temp,temp是待删除节点的前一个节点。 双向链表的操作分析与实现: 遍历方法和单链表一样,只是可以向前...
  • JavaScript实现双向链表

    2020-08-14 14:22:29
    双向链表缺点: 每次在插入或删除某个节点时,都需要处理四个引用,而不是两个,实现起来会困难些; 相对于单向链表,所占内存空间更大一些; 但是,相对于双向链表的便利性而言,这些缺点微不足道。 双向链表...
  • 关于双向链表和二叉树链表的区别

    千次阅读 2020-10-13 13:10:56
    双向链表和二叉树链表区别为:指针不同、指向du不同、访问不同。双zhi向链表和二叉树链表都能dao从链表中的任何一个结点出发能找到任何其他结点。都用来存放线性表中的数据元素。 一、节点指针数量不同 1、双向...
  • linux中双向链表与普通双向链表优缺点 双向循环链表作为一种最常用的数据结构,对程序员来说应该是不陌生的,但很少有人知 道,linux中的双向链表与我们平常使用的双向链表其实是不同的。本文章详细的对linux中的...
  • 链表 B.单循环链表 C.带头结点的双循环链表 D.顺序表 想要存取任一指定序号的元素,链表实现这个功能的代价很大 本来顺序表的弱点在于插入和删除元素,但是题目要求只最后进行插入和删除运算,所有顺序表是最好的...
  • 图解Java数据结构之双向链表

    千次阅读 2019-08-08 13:39:46
    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 增删改查思路...
  • 顺序表: 优点: 1.空间连续 ...链表双向带头循环) 优点: 1.任意位置插入,删除效率高 2.空间利用率高(用就申请不用不申请) 缺点: 1.空间不连续,容易造成内存碎片 2.不能随机访问 ...
  • 双向链表 单向链表的缺点分析 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找 单向链表不能自我删除,需要靠辅助节点,而双向链表,则可以自我删除,所以前面删除单向链表节点时,需要找到...
  • 文章目录链表不同链表的特点单链表(单端链表)双端链表双向链表 链表 上面是一个单链表的存储原理图,head为头节点,它不存放任何的数据,只是充当一个指向链表中真正存放数据的第一个节点的作用,而每个节点中都...
  • 创建双向链表

    2020-11-27 18:29:18
    使用双向链表可以避免单项链表这种单项性的缺点。 顾名思义,双向链表的节点有两个指针域,一个指向其直接后继;另一个指向其直接前驱。`` #include<stdio.h> #include<malloc.h> #include<string...
  • 1.1 什么是链表链表是有序的列表,但是它在内存中是存储如下 特点如下: 链表是以节点的方式来存储,是链式存储 每个节点包含 data 域, next 域:指向下一个节点. 如图:发现链表的各个节点不一定是连续存储....
  • 昨天面试官面试的时候问了我一道关于链表的问题:情境...根据以上分析可得出数组和链表优缺点如下:   数组的优点 随机访问性强(通过下标进行快速定位)查找速度快 数组的缺点 插入和删除效率低(插入和...
  • 图文详解双向链表原理

    千次阅读 2019-10-13 18:44:23
    双向链表 双向链表的主要优点: 对于任意给的结点,都可以很轻易的获取其前结点和后结点。 其主要缺点:每个结点需要保存next和prev两个属性,因此需要更多的空间开销,同时结点的插入与删除操作也将更加耗时,因为...
  • 双向链表(c++实现)

    千次阅读 2018-02-02 18:14:36
    单向链表缺点:逆序访问单向链表中的数据元素,效率低下。   若从头节点开始依次访问单向链表的元素,可使用m_current游标,但是逆序访问,只能通过下面代码实现访问: int main(void) { LinkListint> ll; ...
  • 为克服单链表这种单向性的缺点,可利用 双向链表 (Double Linked List)。 1.1 双向链表的结点(DuLNode) 结点 = 前驱指针域 + 数据域 + 后继指针域 前驱指针域:用来指向结点的直接前驱...
  • 数组与链表优缺点

    万次阅读 多人点赞 2015-03-14 14:05:50
    链表,内存地址上可以是不连续的,每个链表的节点包括原来的内存和下一个节点的信息(单向的一个,双向链表的话,会有两个).  数组优于链表的:  1.内存空间占用的少,因为链表节点会附加上一块或两块下一个节点的信息....
  • 队列2-双向链表

    2019-01-27 16:43:08
    可以看到它们都有一定的缺点,单向链表缺点是无法从任意一个位置随意的往前往后访问,而双向链表也有一个缺点,就是每次都得自行定义并实现一个特定类型的结构体,这个属于两种类型链表的共同缺点了,下面介绍下一个...
  • 文章目录双向循环链表前言文件的创建双向链表结构的定义创建返回链表的头结点值传递时:地址传递:双向链表的销毁双向链表的打印开辟一个新结点双向链表的尾插双向链表的头插双向链表的尾删双向链表的头删双向链表...
  • 在单链表中,有了next指针,这就使得要查找的下一个结点的时间复杂度为O(1),可是要查找是上一个结点的话,最坏的时间复杂度是O(n)了,所以为了克服这一缺点提出双向链表双向链表双向链表是在单链表的每个结点...
  • 双向链表与循环链表

    万次阅读 多人点赞 2018-09-16 00:06:56
    双向链表 单链表的一个优点是结构简单,但是它也有一个缺点,即在单链表中只能通过一个结点的引用访问其后续结点,而无法直接访问其前驱结点, 要在单链表中找到某个结点的前驱结点,必须从链表的首结点出发依次向...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,834
精华内容 13,933
关键字:

双向链表优缺点