精华内容
下载资源
问答
  • 双向链表(详解)

    千次阅读 多人点赞 2020-10-19 02:09:10
    双向链表操作 在学习了单链表之后,就顺带学习了双链表的操作。 什么是双链表? 双链表顾名思义,就是链表由单向的链变成了双向链。 使用这种数据结构,我们可以不再拘束于单链表的单向创建于遍历等操作,大大减少了...

    双向链表操作
    在学习了单链表之后,就顺带学习了双链表的操作。

    什么是双链表?
    双链表顾名思义,就是链表由单向的链变成了双向链。 使用这种数据结构,我们可以不再拘束于单链表的单向创建于遍历等操作,大大减少了在使用中存在的问题。
    在这里插入图片描述
    在单链表中,我们有一个数据域,还有一个指针域,数据域用来存储相关数据,而指针域则负责链表之间的“联系”。 而在双向链表中,我们需要有两个指针域,一个负责向后连接,一个负责向前连接。

    /* 单链表的结构 */
    struct List{
    	int data;				//  数据域
    	struct List *next;			//  指针域 
    };
    
    /* 双向链表的结构 */
    typedef struct List{
    	int data;			// 	数据域
    	struct List *next;		//  向后的指针
    	struct List *front;		//  向前的指针
    };
    
    typedef struct List* pElem;
    typedef struct List eElem;
    

    同单链表一样,对双向链表的操作也有创建,插入,遍历,删除,销毁。

    双向链表的创建
    在创建双向链表的时候,我们需要初始化的有两个指针。同单链表一样,我们需要一个头指针来标志链表的信息。因此我们可以写出该函数的定义:

    pElem CreatList(){
    	pElem head = (pElem)malloc( sizeof(eElem) );
    	assert( head != NULL );		//  包含于标准库<assert.h>
    	head->next = head->front = NULL;		//  初始化链表,指针置空
    	return head;
    }
    

    双向链表的插入
    在单向链表的头插法中,最主要的语句自然就是tmp->next = head->next, 而在双向链表中,自然也是一样,只不过多了连接一个向前的指针而已。

    void InsertElem( pElem head , int data ){
    	if( head == NULL ){
    		printf("The list is empty.\n");		//  头结点为空,则无法插入
    		return;
    	}
    	pElem tmpHead = head;		//  创建一个临时的头结点指针
    	if( tmpHead->next == NULL ){
    		/*  当双向链表只有一个头结点时 */		
    		pElem addition = (pElem)malloc( sizeof(eElem) );
    		assert( addition != NULL );
    		addition->data = data;		//  数据域赋值
    		addition->next = tmpHead->next;		//  后向指针连接
    		tmpHead->next = addition;
    		addition->front = tmpHead;			//  将插入结点的front 指向头结点
    	}
    	else{
    		/* 当双向链表不只一个头结点时 */
    		pElem addition = (pElem)malloc( sizeof(eElem) );
    		assert( addition != NULL );
    		addition->data = data;		//  数据域赋值
    		tmpHead->next->front = addition;		//  头结点的下一个结点的front 指针
    		addition->front = tmpHead;		//  插入的结点的front 指针指向头结点
    		addition->next = tmpHead->next;		//  插入结点的next 指针指向原本头指针的下一结点
    		tmpHead->next = addtion;		//  将头结点的next 指针指向插入结点
    	}
    }
    

    许多人肯定是被最后四条语句弄得一脸懵逼,都一样。但是当你画出图像时,你就会懂得一切。
    在这里插入图片描述
    我们创建一个新的结点addition, 此时链表中只有头结点,因此执行if中的程序,执行完毕之后就变成了:
    在这里插入图片描述
    而当链表中不只有一个头结点时,这时有点意思了。此时,head的next指针指向addition、front指针指向NULL,addition的next指向NULL、front 指针指向head。
    此时,我们要在链表中再插入一个新的结点。 此时,不只要对next 链进行断链,增链,还要对front 链进行同样操作。这样才能完成两条链的连接。

    双向链表的遍历
    不同于单链表的单向遍历,双向链表提供了操作的便捷性,可前可后的遍历方式简直聊咋咧… 因此在遍历中将实现next 的向后遍历,也会实现front的向前遍历。

    void IlluList( pElem head ){
    	printf("-------------------------------\n");
    	if( head == NULL ){
    		printf("The list is empty.\n");
    		return;
    	}
    	pElem tmpHead = head;
    	while( tmpHead->next != NULL ){
    		tmpHead = tmpHead->next;		//  头结点数据域为空,因此直接从头结点的下一结点开始遍历
    		printf("%d\n",tmpHead->data);
    	}
    	//  此时tmpHead 的地址在链表的最后一个结点处
    	while( tmpHead->front->front != NULL ){
    		printf("%d\n",tmpHead->data);		//	最后一个结点要输出
    		tmpHead = tmpHead->front;
    	}
    	printf("%d\n",tmpHead->data);
    	return;
    }
    

    当向后遍历完成之后,此时tmpHead的地址是链表的最后一个结点的地址,因此使用front 来进行向前的遍历。 如果判断条件是tmpHead->front != NULL 的话,会将头结点的数据域也输出,然头结点的数据域未使用,因此会输出一个不确定的值。 正因如此将判断条件定为tmpHead->front->front != NULL

    删除一个结点
    当删除一个结点的时候,我们要判断在链表中是否存在与之匹配的结点,有的话删除成功,否则失败。
    在这里插入图片描述
    就像这幅图一样,当删除addition结点时,先讲addition的下一个结点与head相连,而下一个结点是NULL , 因此可以得出函数为:

    void DeleteElem( pElem head , int data ){
    	if( head == NULL ){
    		printf(""The list is empty.\n);
    		return;
    	}
    	pElem tmpHead = head;
    	while( tmpHead->next != NULL ){
    		tmpHead = tmpHead->next;
    		if( tmpHead->data == data ){
    			tmpHead->front->next = tmpHead->next;		//  将被删结点的上一个结点的next 指针指向 被删结点的下一个结点
    			tmpHead->next->front = tmpHead->front;		//  将被删结点的下一个结点的 front 指针指向 被删结点的上一个结点
    			break;
    		}
    	}
    	free(tmpHead);		//  释放内存
    }
    

    销毁链表
    销毁一个双向链表的操作同单链表的相似。指针不断向后运动,每运动一个结点,释放上一个结点。

    void DestroyList( pElem head ){
    	pElem tmp;
    	while( head->next != NULL ){
    		tmp = head;		//  指针不断后移
    		head = head->next;
    		free(tmp);
    	}
    	free(head);
    }
    

    这里相对容易理解。
    在这里插入图片描述
    此时,tmp的地址就是head的地址,但当执行一个之后,就变成了这样。
    在这里插入图片描述
    上一次执行完之后,头结点已经被释放 ,此时头结点就在第一个数据结点处。 以此往后,最后循环结束,释放最后一个结点。

    这样就是双向链表的基本操作
    原文地址:https://blog.csdn.net/qq_41028985/article/details/84495300

    展开全文
  • 编写程序演示在双向链表上的插入和删除算法 问题分析1在双向链表上操作首先要生成一个双向链表 1>节点定义structDuLNode{ ElemTypedata; DuLNode *prior; DuLNode *next; }; 2> 创建双列表 L (DuLinkList)malloc...
  • 前言单向链表和双向链表的优缺点及使用场景双向链表的简单实现及图示分析 前言 之前写了一些文章简单地介绍顺序表,链表的基础知识,还总结了几道链表的笔试题,今天继续开干,向老铁们简单地介绍一下无头双向循环...

    🎓前言

    之前写了一些文章简单地介绍顺序表,链表的基础知识,还总结了几道链表的笔试题,今天继续开干,向老铁们简单地介绍一下无头双向循环链表及其代码的实现。
    为什么要引入无头双向循环链表呢?????
    我们可以简单地这样去思考,单向链表只能单向地从头节点去访问其他的节点,不能会退的访问其他的节点,也不能循环地访问,与单向链表不同,双向链表在插入删除的时候不需要寻找前驱节点,因为本身就能回到前面一个节点,**查找时,我们可以用二分发的思路,从首节点(head)向后查找操作和last(尾结点)向前查找操作同步进行,这样双链表的查找可以提高一倍,**在实现双向链表的增删改查的时候他们的操作也有不同,我们可以前后对比一下,就能更好地理解他们了。

    🎓单向链表和双向链表的优缺点及使用场景

    单向链表:只有一个指向下一个节点的指针。 优点:单向链表增加删除节点简单。遍历时候不会死循环
    缺点:只能从头到尾遍历。只能找到后继,无法找到前驱,也就是只能前进。 适用于节点的增加删除。

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

    下面是需要注意的地方:

    1、引入了前驱域,解决了单链表只能单向访问的痛点。
    2、对于双向链表来说,要注意:第一个节点的前驱是null和最后一个节点后继是null
    3、引入一个last,标志尾巴节点。

    📝双向链表的简单实现及图示分析

    双向链表的简单模型如图:
    在这里插入图片描述
    声明两个类一个 ListNode,节点这个类它的成员属性包括节点的数值data,prev前驱域,next后继域,一个 MyLinkedList链表这个类它的成员属性,包括头结点head,尾巴节点last,curNext节点等。
    代码如下:

    //节点类
     class ListNode {
    
            public int data;
            public ListNode prev;
            public ListNode next;
    
            public ListNode(int data) {
                this.data = data;
            }
        }
    //链表这个类
     public class MyLinkedList {
            public ListNode head;//头结点
            public ListNode last;//尾结点
            ListNode curNext;//记录下一个节点
    }
    
    

    头插法
    基本思路
    **新插入的节点是头结点,**如果是第一次插入,之前没有一个节点,新插入的节点就是头节点,如果在头插之前有节点,则使node的next指向头节点,head的prev指向node ,之后新的头结点变为新插入的节点即可。
    如图分析:
    在这里插入图片描述
    代码实现:

     //头插法
            public void addFirst(int data) {
                ListNode node = new ListNode(data);
                if (head == null) {
                    this.head = node;
                    this.last = node;//可写可不写
                } else {
                    node.next = head;
                    this.head.prev = node;
                    this.head = node;
    
                }
    
            }
    

    尾插法:
    插入的节点是尾巴节点,如果是第一插入,插入的节点既是头也是尾,如果不是第一插入,使最后一个节点的next指向node,node的prev指向last节点即可。
    如图:
    在这里插入图片描述

     //尾插法
            public void addLast(int data) {
                ListNode node = new ListNode(data);
                if (head == null) {
                    this.head = node;
                    this.last = node;
                } else {
                    last.next = node;
                    node.prev = last;
                    last = node;
                }
    
            }
    
    

    任意位置插入,第一个数据节点为0号下标:
    首先判断插入位置的合法性如果,插入位置index为负或者大于链表的长度,则输入的位置不合法,如果插入的位置等于链表的长度,则为尾插法,插入位置为0位置,则为头插法,中间的位置则正常插入。在插入的时候我们还用到一个查找某一位置的函数 findIndex,通过遍历的方式,寻找插入的位置,返回给插入函数。在插入的时候插入的节点和前后的节点要连起来,连接的顺序不管,但一定要连接对。
    图示分析:
    在这里插入图片描述
    代码实现:

    //任意位置插入,第一个数据节点为0号下标
            public void addIndex(int index, int data) {
                //判断位置的合法性,任意位置插入,第一个数据节点为0号下标
                if (index < 0 || index > size()) {
                    System.out.println("输入的位置不合法");
                    return;
                } else {
                    if (index == 0) {
                        addFirst(data);
                        return;
                    }
                    if (index == size()) {
                        addLast(data);
                    } else {
                        ListNode node = new ListNode(data);
                        ListNode cur;
                        cur = findIndex(index);
                        cur.prev.next = node;//当index==size时,如果不采用尾插法,会出现空指针异常
                         node.prev = cur.prev;
                        cur.prev = node;
                       
                        node.next = cur;
                    }
                }
    
            }
    
     //找到某一位置的节点
     //从头节点开始,要到0位置走0步,要到n位置走n步
            public ListNode findIndex(int index) {
                ListNode cur = head;
                while (index != 0) {
                    cur = cur.next;
                    index--;
    
                }
                return cur;
            }
    
    

    删除第一次出现关键字为key的节点
    大致思路就是,遍历链表寻找要删除的节点,如果找到删除就结束删除了,没找到一直遍历完链表,找到的节点又要分是头结点还是尾结点中间节点,找到头结点还要分是不是只有头结点一个节点还是有多个节点,尾结点不用再分了,中间节点正常删除即可。
    下面结合代码和图示再理解下:
    在这里插入图片描述
    在这里插入图片描述

     //删除第一次出现关键字为key的节点
            public void remove(int key) {
    
                ListNode cur = this.head;
                while (cur != null) {
                    //
                    if (cur.data == key) {
                        //判断是不是头结点
                        if (cur == this.head) {
                            this.head =this.head.next;
                            //头结点是唯一的一个节点
                            if (this.head == null) {
                                this.last = null;
    
                            } else {
                                //头结点不是唯一的节点
                                this.head.prev = null;
                            }
                        } else {
                            cur.prev.next = cur.next;
                            //判断是不是最后一个节点
                            if (cur.next == null) {
                                this.last = cur.prev;
                            } else {
                                cur.next.prev = cur.prev;
                            }
    
    
                        }
                        return;
    
                    } else {
                        cur = cur.next;
                    }
                }
    
            }
    

    删除所有值为key的节点
    这个思路和上面删除第一次出现的key值几乎一样,只是要删除所有出现的key值,我们只要在判断是否是key值if语句后面加个cur=cur.next,这样如果找到要删除的元素继续向后找了删除,没有找到也继续向后找,直到遍历完链表即可。

     //删除所有值为key的节点
            public void removeAllKey(int key) {
                ListNode cur = head;
                while (cur != null) {
                    //
                    if (cur.data == key) {
                        //判断是不是头结点
                        if (cur == this.head) {
                            this.head = this.head.next;
                            //头结点是唯一的一个节点
                            if (cur.next == null) {
                                this.last = null;
    
                            } else {
                                //头结点不是唯一的节点
                                this.head.prev = null;
                            }
                        } else {
                            cur.prev.next = cur.next;
                            //判断是不是最后一个节点
                            if (cur.next == null) {
                                this.last = cur.prev;
                            } else {
                                cur.next.prev = cur.prev;
                            }
    
    
                        }
    
                    }
                    cur = cur.next;继续往后走  不要停 直到为null 的时候
                }
            }
    
    

    得到单链表的长度:
    这个就很简单,遍历链表节点不为空,计数器count加一,一直遍历完即可。

     //得到单链表的长度
            public int size() {
                ListNode cur =this.head;
                int count = 0;
                while (cur != null) {
                    count++;
                    cur = cur.next;
                }
                return count;
            }
    
    

    打印链表

     public void display() {
    
                ListNode cur = this.head;
                while (cur != null) {
                    System.out.print(cur.data + " ");
                    cur = cur.next;
    
                }
                System.out.println();
    
            }
    

    查找是否包含关键字key是否在单链表当中

    //查找是否包含关键字key是否在单链表当中
            public boolean contains(int key) {
                /
                if(this.head==null) return false;
                ListNode cur = this.head;
                while (cur != null) {
                    if (cur.data == key) {
                        return true;
                    }
                    cur=cur.next;
    
                }
                //return false;
                return false;
            }
    

    清空链表
    清空链表不能简单的把head置为null,last置为null,要遍历链表把每个节点的前驱后继都置为null,但要注意在把节点的值置为null的时候要提前记录下一个节点的位置。

    在这里插入图片描述

       public void clear() {
                ListNode cur =  this.head;
    
                while (cur != null) {
                    curNext = cur.next;
                    cur.prev = null;
                    cur.next = null;
                    cur = curNext;//提前记录下一个节点的位置
    
                }
                this.head = null;
                this.last = null;
    
    
            }
    

    完整代码:
    MyLinkedList.java

     class ListNode {
    
            public int data;
            public ListNode prev;
            public ListNode next;
    
            public ListNode(int data) {
                this.data = data;
            }
        }
    
        public class MyLinkedList {
            public ListNode head;//头结点
            public ListNode last;//尾结点
            ListNode curNext;//记录下一个节点
    
            //找到某一位置的节点
            public ListNode findIndex(int index) {
                ListNode cur = head;
                while (index != 0) {
                    cur = cur.next;
                    index--;
    
                }
                return cur;
            }
    
    
            //头插法
            public void addFirst(int data) {
                ListNode node = new ListNode(data);
                if (head == null) {
                    this.head = node;
                    this.last = node;//可写可不写
                } else {
                    node.next = head;
                    this.head.prev = node;
                    this.head = node;
    
                }
    
            }
    
            //尾插法
            public void addLast(int data) {
                ListNode node = new ListNode(data);
                if (head == null) {
                    this.head = node;
                    this.last = node;
                } else {
                    last.next = node;
                    node.prev = last;
                    last = node;
                }
    
            }
    
            //任意位置插入,第一个数据节点为0号下标
            public void addIndex(int index, int data) {
                //判断位置的合法性,任意位置插入,第一个数据节点为0号下标
                if (index < 0 || index > size()) {
                    System.out.println("输入的位置不合法");
                    return;
                } else {
                    if (index == 0) {
                        addFirst(data);
                        return;
                    }
                    if (index == size()) {
                        addLast(data);
                    } else {
                        ListNode node = new ListNode(data);
                        ListNode cur;
                        cur = findIndex(index);
                        cur.prev.next = node;//当index==size时,如果不采用尾插法,会出现空指针异常
                        node.prev = cur.prev;
                        cur.prev = node;
    
                        node.next = cur;
                    }
                }
    
            }
    
            //查找是否包含关键字key是否在单链表当中
            public boolean contains(int key) {
                //修改错误
                if(this.head==null) return false;
                ListNode cur = this.head;
                while (cur != null) {
                    if (cur.data == key) {
                        return true;
                    }
                    cur=cur.next;
    
                }
                //return false;
                return false;
            }
    
            //删除第一次出现关键字为key的节点
            public void remove(int key) {
    
                ListNode cur = this.head;
                while (cur != null) {
                    //
                    if (cur.data == key) {
                        //判断是不是头结点
                        if (cur == this.head) {
                            this.head =this.head.next;
                            //头结点是唯一的一个节点
                            if (cur.next == null) {
                                this.last = null;
    
                            } else {
                                //头结点不是唯一的节点
                                this.head.prev = null;
                            }
                        } else {
                            cur.prev.next = cur.next;
                            //判断是不是最后一个节点
                            if (cur.next == null) {
                                this.last = cur.prev;
                            } else {
                                cur.next.prev = cur.prev;
                            }
    
    
                        }
                        return;
    
                    } else {
                        cur = cur.next;
                    }
                }
    
            }
    
            //删除所有值为key的节点
            public void removeAllKey(int key) {
                ListNode cur = head;
                while (cur != null) {
                    //
                    if (cur.data == key) {
                        //判断是不是头结点
                        if (cur == this.head) {
                            this.head = this.head.next;
                            //头结点是唯一的一个节点
                            if (cur.next == null) {
                                this.last = null;
    
                            } else {
                                //头结点不是唯一的节点
                                this.head.prev = null;
                            }
                        } else {
                            cur.prev.next = cur.next;
                            //判断是不是最后一个节点
                            if (cur.next == null) {
                                this.last = cur.prev;
                            } else {
                                cur.next.prev = cur.prev;
                            }
    
    
                        }
    
                    }
                    cur = cur.next;继续往后走  不要停 直到为null 的时候
                }
            }
    
            //得到单链表的长度
            public int size() {
                ListNode cur =this.head;
                int count = 0;
                while (cur != null) {
                    count++;
                    cur = cur.next;
                }
                return count;
            }
    
            public void display() {
    
                ListNode cur = this.head;
                while (cur != null) {
                    System.out.print(cur.data + " ");
                    cur = cur.next;
    
                }
                System.out.println();
    
            }
    
            public void clear() {
                ListNode cur =  this.head;
    
                while (cur != null) {
                    curNext = cur.next;
                    cur.prev = null;
                    cur.next = null;
                    cur = curNext;
    
                }
                this.head = null;
                this.last = null;
    
    
            }
        }
    
    
    

    TestDemo.java

    public class TestDemo {
        public static void main(String[] args) {
            MyLinkedList myLinkedList =new MyLinkedList();
            myLinkedList.addFirst(1);
            myLinkedList.addFirst(2);
            myLinkedList.addFirst(3);
            myLinkedList.addFirst(4);
            myLinkedList.display();
            System.out.println(myLinkedList.contains(0));
            myLinkedList.remove(4);
            myLinkedList.display();
        }
    
    
    }
    

    🛣️过🉐小🧑🏽‍🤝‍🧑🏼如果9️⃣🉐🉑以🉐话记🉐点👍🏻🍹持👇🏻,🦀🦀

    展开全文
  • 双向链表结点的插入和删除算法

    万次阅读 多人点赞 2018-10-03 23:47:46
    双向链表的插入与删除 双向链表的结点定义 #define ElemType int //双向链表的存储结构 typedef struct DuLNode { ElemType data; DuLNode *prior; DuLNode *next; }DuLNode, *DuLinkList; 双向链表...

    双向链表的插入与删除

    双向链表的结点定义

    #define  ElemType int
    //双向链表的存储结构
    typedef struct DuLNode
    {
        ElemType data;
        DuLNode *prior;
        DuLNode *next;
    }DuLNode, *DuLinkList;
    

    双向链表的结点插入

    画图表示,并在上述双向链表中一个已知结点p之后插入一个结点s的四条语句,请标明先后顺序。

    在p之后插入结点s

    对应的代码片段为:

    //在第i个结点p之后插入s,数据域是e的结点
    void ListInsert_DuL(DuLinkList &L, int i,ElemType e)
    {    
        DuLNode *p;
        p = GetElem_DuL(L,i);//在L中确定第i个元素的位置指针p
        //新建一个结点
        DuLNode *s;
        s = new DuLNode;
        s->data = e;
        //插入
        s->prior = p;
        p->next->prior = s;
        s->next = p->next;
        p->next = s;
     }
    

    双向链表插入算法的注意事项:插入新结点的核心步骤为修改四个指针,要保证在插入的过程中不能断开链表原来的链,否则链表就断链了。

    双向链表的结点删除

    画图表示,并在上述双向链表中删除一个已知结点p的两条语句,请标明先后顺序。
    删除结点p
    对应的代码片段为:

    //在双向链表中删除第 i个结点
    void ListDelete_DuL(DuLinkList &L, int i)
    {
        DuLNode *p;
        p = GetELem_DuL(L,i);在L中确定第i个元素的位置指针p
        //重建链
        p->prior->next = p->next;
        p->next->prior = p->prior;
        //删除p结点
        delete p;
    }
    

    双向链表删除算法的注意事项:插入新结点的核心步骤为修改只需要修改两个指针,方法简单,注意释放结点p的空间即可。

    作者practical_sharp
    第一次写博客,有很多做的不周到地方,不喜勿喷。

    展开全文
  • 双向链表的插入

    2020-08-04 19:20:58
    双向链表的插入 参考来源:数据结构与算法基础(青岛大学-王卓)p38 算法实现: void ListInset_DuL(DuLinkList &L,int i,ElemType e){ if(!(p=GetElemp_DuL(L,i)))return error; s=new DuLnode; s->data = ...

    双向链表的插入

    参考来源:数据结构与算法基础(青岛大学-王卓)p38
    在这里插入图片描述

    算法实现:

    void ListInset_DuL(DuLinkList &L,int i,ElemType e){
    if(!(p=GetElemp_DuL(L,i)))return error;
    s=new DuLnode; s->data = e;
    s->prior = p->prior; //1
    p->prior->next = s; //2
    s->next = p; //3
    p->prior = s; //4

    return Ok;
    }

    在这里插入图片描述
    注:GetElemp_DuL(L,i) 返回插入位置i的地址值,并赋予给p

    展开全文
  • 目录 【链表】 【单向链表】 普通类结构的单向列表(以循环遍历数据) 内部类结构的单向列表(以递归遍历数据) 几个常见单向链表功能实现(以第一个源码例) ...分类:单向链表,双向链表,环形链表
  • 双向链表的插入与删除(c++实现)

    千次阅读 2020-04-30 16:28:13
    目录前言双向链表插入节点实现代码双向链表删除节点实现代码整个项目的完整代码运行截图总结 前言 本篇文章主要接着上文的双向链表的创建与遍历(c++实现) ...
  • 文章目录双向循环链表前言文件的创建双向链表结构的定义创建返回链表的头结点值传递时:地址传递:双向链表的销毁双向链表的打印开辟一个新结点双向链表的尾插双向链表的头插双向链表的尾删双向链表的头删双向链表...
  • 双向链表的基本概念 单链表的结点中,只有一个指针域,用来指示后继结点。由此,从某个结点出发只能顺时针向后寻找其他结点。若要寻找结点的前驱结点,则必须从表头指针出发。换言之,在单链表中,查找直接后继...
  • C++实现双向链表操作

    2020-02-03 23:44:09
    双向链表是在单链表的基础上为每个结点添加一个前趋指针域prior,这样形成的链表可有两个不同的方向。 双向链表一般也可由头指针唯一确定,其每一结点均有: 数据域(data) 左链域(prior):指向前趋结点. 右链域...
  • 插入排序需要从后往前遍历寻找可以插入的位置,所以会使用到双向链表 typedef struct Node//定义的结构体 { int data; struct Node* per; //记录前驱 struct Node* next; }*List; 创建带头节点的双链表 List ...
  • 一、向双向链表中插入新节点new 关于双向链表的插入问题,有些地方需要特别理解一下,有一个原则就是不能将原始链表弄丢,所以在断开原始连接之前, 我们应该先要将即将断开部分的前后连接保存下来,也就是链表...
  • 创建双向链表(详解)

    万次阅读 多人点赞 2018-11-25 16:18:46
    双向链表操作 在学习了单链表之后,就顺带学习了双链表的操作。 什么是双链表? 双链表顾名思义,就是链表由单向的链变成了双向链。 使用这种数据结构,我们可以不再拘束于单链表的单向创建于遍历等操作,大大减少...
  • 这一篇,说一下双链表的实现,双向链表一定是在单链表的基础上,进行优化,才能成为双链表,关于单链表的文章,可以看下面这个链接: https://blog.csdn.net/weixin_46726346/article/details/107687955 所以一些...
  • 双向链表的合并

    千次阅读 2019-10-13 11:59:55
    A 和 b 是两双向链表。其中每一个结点存放一个整数。试编函数,将链表 b 和链表 a 合并,且去除 其中整数值相同的结点,返回合并后的链表首地址。 【做错过的点】 1.在“r = r->next;”后面还加了一句“p = p-&...
  • 双向链表(一)

    2019-11-11 23:00:51
    双向链表(一) 双向链表是一个常用的数据结构,同时在STL中也占有一席之地,那么实现双向链表是一个很好的练习,那么下面就实现一个最简单的双向链表。 基本设置: 含有next prev指针,value值的node类。 ...
  • 双向链表这里不做赘述,其特性已经普及遍了。可以参考之前博客的单向链表进行回顾学习。 在这里记录一个问题点,就是双向链表的有序插入时,赋值顺序是什么? 首先什么是有序插入,插入分为头部插入和尾部插入和按...
  • 双向链表 双向链表:又称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。 特点: 在数据结构中具有双向指针 插入数据的时候需要考虑前后的方向的操作 同样,删除数据的是有...
  • 双向链表知识总结

    千次阅读 2019-06-05 15:11:56
    双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造...
  • 头插法建立双向链表

    千次阅读 2020-07-12 21:59:10
    单链表只能向后访问其他节点的数据,若需要寻找某节点前面节点的数据,则需要从表头开始,重新进行遍历,效率不高,为了克服单链表单向性的缺点,可以利用双向链表 双向链表有两个指针域,一个指向直接后继,一个...
  • Java实现--双向链表

    千次阅读 2018-09-29 12:14:17
    为什么要构造双向链表呢?有什么用呢?《Java数据结构和算法》一书给出了一个例子回答了这两个问题: “假设一个文本编辑器用链表来存储文本。屏幕上的每一行文字作为一个String对象存储在链结点中。当编辑器用户...
  • 3、单链表的插入只需要修改两个指针,而双链表需要修改四次指针,即p的前驱、后继,s的前驱、后继。 4、双链表删除节点时比单链表方便很多。因为单链表删除时需要进行一次循环来查找它上一个...
  • 引入:双向链表是在原来的单链表基础上增加了一个可以保存某节点的上一个节点的指针域的数据结构,相较于单链表而言,双向链表在查找数据的时候所花费的时间是要小于单链表的,因为其可进可退。其缺点就是增删节点比...
  • 双向链表实现两个多项式的加法与乘法 #include <iostream> using namespace std; template<typename E> class Link { //声明Link类,用于存放多项式的一项; private: static Link<E>* freelist;...
  • 作者最近做数据结构的习题时发现了好多关于双向链表的问题,诸如双向链表非空的判定条件,双向链表插入一个结点的四条基本语句双向链表删除一个结点的两条基本语句,判断双向链表是否为回文表的算法之类的练习题。...
  • 双向链表结点定义为: struct node { int data; struct node *front,*next; }; 有两个双向链表A,B,知道其头指针为:pHeadA,pHeadB,请写一函数将两链表中data值相同的结点删除。 答案: typedef ...
  • 单向链表和双向链表分析与操作

    万次阅读 2021-03-15 16:03:40
    单链表和双链表 链表结构: 优点: 1、在程序中使用数组之前,必须事先知道数组的大小,增加数组的大小是一个耗时的过程,在运行时几乎不可能扩展数组的大小。而链表不需要提前声明链表的大小,链表的大小是随着使用...
  • 假设我们定位到了A节点,那么A.next就是B节点,这个是前提。 C.pre = A; C.next = A.next; A.next.pre = C; A.next = C;
  • printf("链表的长度:"); scanf("%d",&a); L1=create(a); printf("插入的位置以及数值:"); scanf("%d%d",&pos,&x); L1=Insert(L1,pos,x); show(L1); printf("输入删除的位置:"); scanf("%d",&y); ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,099
精华内容 12,439
关键字:

双向链表语句