双向链表_双向链表删除 - CSDN
双向链表 订阅
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 展开全文
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
信息
类    别
链表
特    点
每个数据结点中都有两个指针
方    法
正序查找,逆序查找
中文名
双向链表
亦    称
双链表
应    用
孔子电路
双向链表链表的操作
线性表的双向链表存储结构:带头结点的双向循环链表的基本操作:销毁双向循环链表L:重置链表为空表:验证是否为空表 [1]  :
收起全文
精华内容
参与话题
  • 详细图文——双向链表

    千次阅读 2019-04-09 16:32:41
    前篇->有序链表    &...在传统链表中我们寻找下一...双向链表提供了反向遍历的能力。其秘密在于每个结点有两个指向其他结点的引用,一个指向前继结点,一个指向后继结点。下图显示

    前篇->有序链表
           在传统链表中我们寻找下一个结点是否方便,但是如果要追溯前面的结点是比较困难的。
           双向链表提供了反向遍历的能力。其秘密在于每个结点有两个指向其他结点的引用,一个指向前继结点,一个指向后继结点。下图显示了双向链表:
    在这里插入图片描述

    代码实现双向链表

    Link类(结点)的定义

    public class Link {
    	public int data;
    	public Link previous;
    	public Link next;
    	
    	public Link(int data){
    		this.data = data;
    	}
    	
    	public void displayLink(){
    		System.out.print(this.data + "  ");
    	}
    }
    

    结点插入

           结点的插入有三种情况:在首部插入,在尾部插入和任意位置插入。现在分别实现这三种情况的代码。

    首部插入

    在这里插入图片描述
    这是链表不为空时的插入顺序,当链表为空时插入结点需要注意last的更新。

    public class DoubleList {
    	private Link first;
    	private Link last;
    	
    	//判断链表是否为空
    	public boolean isEmpty(){
    		return first==null;
    	}
    	
    	/**
    	 * 从首部插入结点
    	 * @param data
    	 */
    	public void insertFirst(int data){
    		Link newNode = new Link(data);
    		if(isEmpty()){//当list为空时需要更新last
    			last = newNode;
    		}else{
    			first.previous = newNode;
    		}
    		newNode.next = first;
    		first = newNode;
    	}
    }
    

    尾部插入

    在这里插入图片描述
    注意链表为空时的插入。

    /**
     * 从尾部插入
     */
    public void insertLast(int data){
    	Link newNode = new Link(data);
    	if(isEmpty()){
    		first = newNode;
    	}else{
    		last.next = newNode;
    		newNode.previous = last;
    	}
    	last = newNode;
    }
    

    任意位置插入

    在这里插入图片描述

    /**
    	 * 将指定数据插入到指定结点后
    	 * @param key {指定结点的值}
    	 * @param data {待插入数据值}
    	 * @return boolean {成功插入返回true,否则返回false}
    	 */
    	public boolean insertAfter(int key,int data){
    		Link newNode = new Link(data);
    		Link current = first;
    		while(current!=null&&current.data!=key){
    			current = current.next;
    		}
    		if(current==null)
    			return false;
    		if(current==last){
    			last = newNode;
    		}else{
    			newNode.next = current.next;
    			current.next.previous = newNode;
    		}
    		newNode.previous = current;
    		current.next = newNode;
    		return true;
    	}
    

    结点删除

           结点的插入有三种情况:在首部删除,在尾部删除和任意位置删除。现在分别实现这三种情况的代码。

    首部删除

    在这里插入图片描述

    /**
     * 首部删除
     */
    public void deleteFirst(){
    	Link temp = first;
    	if(first.next == null)
    		last = null;//只有一个结点,删除后需要更新last
    	else
    		first.next.previous = null;
    	first = first.next;
    	return temp;
    }
    

    尾部删除

    在这里插入图片描述

    /**
    * 尾部删除
     */
    public void deleteLast(){
    	Link temp = last;
    	if(first.next == null)
    		first = null;
    	else
    		last.previous.next = null;
    	last = last.previous;
    	return temp;
    }
    

    任意位置删除

    在这里插入图片描述

    /**
    * 任意位置删除
     */
    public Link deleteKey(int key){
    	Link current=first;
    	while(current!=null&&current.data!=key){
    		current = current.next;
    	}
    	if(current==null)
    		return null;
    	if(first==current)
    		first = current.next;
    	else
    		current.previous.next = current.next;
    		
    	if(current==last)
    		last = current.previous;
    	else
    		current.next.previous = current.previous;
    	return current;
    }
    

    链表遍历

           双向链表的遍历有两种情况:从前向后和从后向前。现在实现这两种情况的代码。

    public void displayForward(){
    	System.out.println("first-->last:");
    	Link current = first;
    	while(current!=null){
    		current.displayLink();
    		current = current.next;
    	}
    	System.out.println();
    }
    
    public void displayBackward(){
    	System.out.println("last-->first:");
    	Link current = last;
    	while(current!=null){
    		current.displayLink();
    		current = current.previous;
    	}
    	System.out.println();
    }
    

    链表测试

    public class TestMain {
    	public static void main(String[] args) {
    		DoubleList list = new DoubleList();
    		list.insertFirst(1);
    		list.insertFirst(2);
    		list.insertFirst(3);
    		list.insertLast(4);
    		list.insertLast(5);
    		list.insertAfter(3, 6);
    		list.displayForward();
    		list.displayBackward();
    		
    		//删除
    		System.out.println("delete first:");
    		list.deleteFirst();
    		list.displayForward();
    		System.out.println("delete last:");
    		list.deleteLast();
    		list.displayBackward();
    		System.out.println("delete key==4:");
    		list.deleteKey(4);
    		list.displayBackward();
    	}
    }
    

    在这里插入图片描述

    展开全文
  • c中的双向链表实现

    千次阅读 2018-08-10 11:52:46
    1、之前在培训公司学习了用C语言实现双向链表的知识,现在有空重新写一遍。首先定义一下头文件list.h。 1 #ifndef __LIST_H__ 2 #define __LIST_H__ 3 4 #include <stdio.h> 5 #include &...

    1、之前在培训公司学习了用C语言实现双向链表的知识,现在有空重新写一遍。首先定义一下头文件list.h。

      1 #ifndef __LIST_H__
      2 #define __LIST_H__
      3
      4 #include <stdio.h>
      5 #include <stdlib.h>
      6 #include <string.h>
      7
      8 //双向循环列表
      9 struct list
     10 {
     11         struct list *prev, *next;
     12         void *dat;
     13         int size;
     14 };
     15
     16 //比较函数类型
     17 typedef int (*cmp_t)(void *dat1, void *dat2);
     18
     19 //打印函数类型
     20 typedef void (*print_t)(void *dat);
     21
     22 struct list *list_create(int size);
     23 int list_addtail(struct list *head, void *dat);
     24 int list_addhead(struct list *head, void *dat);
     25 struct list *list_find(struct list *head, void *dat, cmp_t cmp);
     26 void list_delnode(struct list *head, void *dat, cmp_t cmp);
     27 void list_print(struct list *head, print_t print);
     28 void list_destroy(struct list **entry);
     29
     30 #endif /* __LIST_H__ */
    

    在头文件中,主要是定义了一个结构体的链表list,里面定义了指向前prev跟指向后的next指针,还有保存数据的变量dat及大小size。其他都是函数的声明。

    2、接下来看一下list.c的函数具体实现。

    1 #include "list.h"
      2
      3 //分配一个头结点
      4 struct list *list_create(int size)
      5 {
      6         struct list *head = NULL;
      7         head = calloc(1, sizeof(*head));
      8         if (NULL == head)
      9         {
     10                 perror("calloc head");
     11                 return NULL;
     12         }
     13         head->prev = head->next = head;
     14         head->size = size;
     15         return head;
     16 }
     17
     18 //把一个结点加入链表尾
     19 int list_addtail(struct list *head, void *dat)
     20 {
     21         struct list *tmp, *new;
     22
     23         //分配新的结点
     24         new = calloc(1, sizeof(*new));
     25         if(new == NULL)
     26         {
     27                 perror("calloc new");
     28                 return -1;
     29         }
     30
     31         //为结点分配数据的空间
     32         new->dat = calloc(1, head->size);
     33         if(new->dat == NULL)
     34         {
     35                 perror("calloc dat");
     36                 free(new);
     37                 return -1;
     38         }
     39         memcpy(new->dat, dat, head->size);
     40
     41         //把新结点加入链表中
     42         new->next = head;
     43         new->prev = head->prev;
     44         head->prev->next = new;
     45         head->prev = new;
     46         return 0;
     47 }
     48
     49
     50 //把一个结点加入链表头
     51 int list_addhead(struct list *head, void *dat)
     52 {
     53         struct list *tmp, *new;
     54
     55         //分配新的结点
     56         new = calloc(1, sizeof(*new));
     57         if(new == NULL)
     58         {
     59                 perror("calloc new");
     60                 return -1;
     61         }
     62
     63         //为结点分配数据的空间
     64         new->dat = calloc(1, head->size);
     65         if(new->dat == NULL)
     66         {
     67                 perror("calloc dat");
     68                 free(new);
     69                 return -1;
     70         }
     71         memcpy(new->dat, dat, head->size);
     72
     73         //把新结点加入链表中
     74         new->prev = head;
     75         new->next = head->next;
     76         head->next->prev = new;
     77         head->next = new;
     78         return 0;
     79 }
     80
     81 //在链表中查找某个结点
     82 struct list *list_find(struct list *head, void *dat, cmp_t cmp)
     83 {
     84         struct list *tmp;
     85         for (tmp = head->next; tmp != head; tmp = tmp->next)
     86         {
     87                 if (!cmp(tmp->dat, dat))
     88                 {
     89                         return tmp;
     90                 }
     91         }
     92         return NULL;
     93 }
     94
     95 //删除某个指定的结点
     96 void list_delnode(struct list *head, void *dat, cmp_t cmp)
     97 {
     98         struct list *tmp;
     99         tmp = list_find(head, dat, cmp);
    100         if (tmp != NULL)
    101         {
    102                 tmp->prev->next = tmp->next;
    103                 tmp->next->prev = tmp->prev;
    104                 free(tmp->dat);
    105                 free(tmp);
    106         }
    107 }
    108
    109 //打印链表的内容
    110 void list_print(struct list *head, print_t print)
    111 {
    112         struct list *tmp;
    113         for (tmp = head->next; tmp != head; tmp = tmp->next)
    114         {
    115                 print(tmp->dat);
    116         }
    117         printf("\n");
    118 }
    119
    120 //销毁链表,释放链表占据的所有空间
    121 void list_destroy(struct list **entry)
    122 {
    123         struct list *head, *tmp, *next;
    124
    125         if (entry != NULL)
    126         {
    127                 head = *entry;
    128                 for (tmp = head->next; tmp != head; tmp = next)
    129                 {
    130                         next = tmp->next;
    131                         free(tmp->dat);
    132                         free(tmp);
    133                 }
    134                 free(head);
    135                 *entry = NULL;
    136         }
    137
    138 }
    

    首先是定义头结点 *list_create(int size),在这个函数里面会分配内存空间,并且让前后指针都指向头head。

    3、通过测试test.c来测试一下刚才写的双向链表。

    1 #include <stdio.h>
      2 #include "list.h"
      3
      4 //此程序用于测试双向循环链表
      5 int ar[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
      6 void print_int(void *dat);
      7 int cmp_int(void *dat1, void *dat2);
      8
      9 int main(void)
     10 {
     11         int i = 0;
     12         struct list *tmp;
     13         struct list *head = list_create(sizeof(int));
     14         if (NULL == head)
     15         {
     16                 return -1;
     17         }
     18
     19         for (i; i < 10; i++)
     20         {
     21                 list_addtail(head, &ar[i]);
     22         }
     23
     24         list_print(head, print_int);
     25         tmp = list_find(head, &ar[3], cmp_int);
     26         if (tmp != NULL)
     27         {
     28                 print_int(tmp->dat);
     29                 printf("\n");
     30         }
     31
     32         list_delnode(head, &ar[4], cmp_int);
     33         list_print(head, print_int);
     34
     35         ar[4] = 100;
     36         list_delnode(head, &ar[4], cmp_int);
     37         list_print(head, print_int);
     38
     39         list_destroy(&head);
     40         return 0;
     41
     42
     43 }
     44
     45 void print_int(void *dat)
     46 {
     47         printf("%d ", *(int *)dat);
     48 }
     49
     50 int cmp_int(void *dat1, void *dat2)
     51 {
     52         return *(int *)dat1 - *(int *)dat2;
     53 }

    运行程序的结果:

     

     

     

     

    展开全文
  • 创建双向链表(详解)

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

    双向链表操作

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

    什么是双链表?

    双链表顾名思义,就是链表由单向的链变成了双向链。 使用这种数据结构,我们可以不再拘束于单链表的单向创建于遍历等操作,大大减少了在使用中存在的问题。

    在这里插入图片描述

    在单链表中,我们有一个数据域,还有一个指针域,数据域用来存储相关数据,而指针域则负责链表之间的“联系”。 而在双向链表中,我们需要有两个指针域,一个负责向后连接,一个负责向前连接

    /* 单链表的结构 */
    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中的程序,执行完毕之后就变成了:
    在这里插入图片描述

    具体步骤有以前的博客《创建单链表的头插法与尾插法详解》。

    而当链表中不只有一个头结点时,这时有点意思了。

    此时,headnext指针指向additionfront指针指向NULLadditionnext指向NULLfront 指针指向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的地址,但当执行一个之后,就变成了这样。
    在这里插入图片描述
    上一次执行完之后,头结点已经被释放 ,此时头结点就在第一个数据结点处。 以此往后,最后循环结束,释放最后一个结点。

    这样就是双向链表的基本操作

    展开全文
  • 双向链表的基本操作

    万次阅读 多人点赞 2017-07-28 18:42:07
    学过单向链表的小伙伴都知道单向链表中的每一个节点有且只有一个指针,这个指针就是用来指向下一个节点的,单向链表顾名思义就是链表方向是单方向的,而本文要介绍的双向链表就是链表方向是双方向的,也就是双向链表...

       学过单向链表的小伙伴都知道单向链表中的每一个节点有且只有一个指针,这个指针就是用来指向下一个节点的,单向链表顾名思义就是链表方向是单方向的,而本文要介绍的双向链表就是链表方向是双方向的,也就是双向链表中的每一个节点有两个指针,一个指针用来指向上一个节点(前驱),另一个指针用指向下一个节点(后继)。

      本文主要是总结一下自己对双向链表的基本操作,当然我也只是写了几个比较简单的操作,其中包括双向链表的创建,插入节点,删除节点,还有输出节点的数据等。学习这个双向链表总的感受就是特别绕,因为涉及多个指针的操作,对于指针没有学好的人儿来说,理解双向链表还是比较困难的。不过功夫不负有心人,只要肯花时间,我觉得一切都不是问题的。下面贴上自己写的代码:

    /*********************************************************************************
     *      Copyright:  (C) 2017 zoulei
     *                  All rights reserved.
     *
     *       Filename:  link.c
     *    Description:  This file
     *
     *        Version:  1.0.0(2017年07月26日)
     *         Author:  zoulei <zoulei121@gmail.com>
     *      ChangeLog:  1, Release initial version on "2017年07月26日 18时51分00秒"
     *
     ********************************************************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    typedef struct DoubleLinkNode
    {
       int data;
       struct DoubleLinkNode *prev;
       struct DoubleLinkNode *next;
    }Node;
     /* 创建一个带头节点的双向链表 */
    Node*Create_Double_link()
    {
       Node*head;
       Node*pnext;
       Node*plast;
       int i,n;
       head=(Node*)malloc(sizeof(Node));
       assert(NULL != head);
       head->prev=NULL;
       head->next=NULL;
    
       printf("please input the length of the double linked list:");
       scanf("%d",&n);
       while(n!=0)
       {
          plast=head;
          for(i=0;i<n;i++)
          {
             pnext=(Node*)malloc(sizeof(Node));
             printf("向第%d个节点输入数据:",i+1);
             scanf("%d",&pnext->data);
             plast->next=pnext;
             pnext->prev=plast;
             plast=plast->next;
          }
          pnext->next=NULL;
          break;
       }
       return head;
    }
    /* 输出每一个节点的数据 */
    void print(Node*head)
    {
      Node*temp;
      int j=0;
      temp=head;
      while(temp->next!=NULL)
      {
         j++;
         printf("输出第%d个节点的数据:%d\n",j,temp->next->data);
         temp=temp->next;
      }
      printf("输出第%d个节点的数据:%p\n",j+1,temp->next);
    }
    /* 插入节点 */
    int InsertNode(Node* head)
    {
       Node*new;
       Node*pnext=head;
       int i=0;
       int n;
    
       printf("please input the location which is inserted:");
       scanf("%d",&n);
    
       while((i<n) && (pnext!=NULL))
       {
          i++;
          pnext=pnext->next;
    
       }
       if(pnext==NULL)
       {
         return 1;
       }
       else
       {
            new=(Node*)malloc(sizeof(Node));
            printf("请在新插入的节点中输入数据:");
            scanf("%d",&new->data);
    
            new->next=pnext->next;
            if(n=0)
            {
              pnext->next=new;
              new->next=NULL;
            }
            else
            {
              pnext->next=new;
              pnext->next->prev=new;
              new->prev=pnext;
            }
       }
       return 0;
    }
    /*删除节点 */
    int DeleteNode(Node*head)
    {
       Node*pnext=head;
       Node*ptr;
       int n;
       int i=0;
       printf("please input the node that you will delete:");
       scanf("%d",&n);
       while((i<n-1) && (pnext!=NULL))
       {
          i++;
          pnext=pnext->next;
       }
       if(pnext->next->next!=NULL)
       {
           ptr=pnext->next;
           ptr->next->prev=pnext;
           pnext=ptr->next;
           free(ptr);
       }
       else
       {
         ptr=pnext->next;
         free(ptr);
       }
      return 0;
    }
     /* 主函数 */
    int main(int argc,char**argv)
    {
       Node* head;
       head=Create_Double_link();
       InsertNode(head);
       DeleteNode(head);
       print(head);
       return 0;
    }

    代码分析:

    1.创建原链表如图所示:



    头节点的一个指针初始化时指向NULL,分析一下核心代码吧!plast是我定义的一个临时指针,通过这个临时指针将所有节点连接起来,首先将plast指向头结点,pnext是指向新增节点的指针,所以用plast->next指向新增节点,新增节点的pnext->prev指向前一节点,由于是新增第一个节点,所以第一个节点也就指向头结点,而头节点的head->next指向第一个节点,最后再将临时指针指向第一个节点,这样不断的循环下去,就可以创建指定长度的链表了。不过最后一个节点指向下一个节点的指针必须赋值为为NULL,对应代码就是源文件中的 pnext->next=NULL;

    2.在原链表的指定位置插入一个节点,如下图:


    这里在原链表的指定位置插入一个节点,整体思想是:先循环遍历到要插入的位置,再把插入的节点的一个指针用来指向下一个节点,即将插入的节点的另一个指针指向上一个节点,不过首先要把插入的那个位置的节点与之相连的下一个节点断开。代码怎么来实现这个逻辑呢?假设以上图为例,我的目的是想在第一个节点与第二个节点之间插入一个新的节点,代码实现是这样的:首先用一个while循环遍历到第一个节点的位置,然后用一个指针pnext指向第一个节点,pnext->next指针就是指向第二个节点,然后new是一个指向新增节点地址的指针,在我们要断开第一个节点与第二个节点之前,用新增节点的指针new->next指向第二个节点的地址,这样后面我们才能操作第二个节点的地址,也就是对应 new->next=pnext->next;这段代码;接着将原先指向第二个节点的指针pnext->next指向新增节点的地址也就是指向new;然后将原先指向第一个节点的指针pnext->next->prev现在改为指向新增节点的地址(new是指向新增节点的内存地址的指针,这里prev指向new也就指向了新增节点的内存地址);最后将新增节点的另一个指针prev指向第一个节点的地址,这样就将第一个节点与第二个节点断开了,同时也将新节点插入到了指定位置。

    3.删除原链表中指定的节点,如图所示:


    删除指定节点过程也就是插入指定节点的逆过程。看图就明白了,这里就不分析了。

    测试结果(只贴上删除节点的):










    展开全文
  • 双向链表及其用法

    万次阅读 多人点赞 2018-05-25 13:40:46
    转载自:https://blog.csdn.net/fk5431/article/details/45072935一、双向链表的定义双向链表也...二、双向链表的存储结构双向链表也是采用的链式存储结构,它与单链表的区别就是每个数据结点中多了一个指向前驱元素...
  • 双向链表

    2020-10-08 17:44:56
    双向链表 双向链表数据结构 具有前后指针的链表结构 题目链接 https://www.acwing.com/problem/content/829/ 操作分析 注意: 插入操作默认是从k的后面插入 0 和 1 是左右边界,不是具体的值 0是左边界, 1 是右边...
  • 双向链表(详解)

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

    千次阅读 2018-09-16 09:04:17
    双向链表 单链表的一个优点是结构简单,但是它也有一个缺点,即在单链表中只能通过一个结点的引用访问其后续结点,而无法直接访问其前驱结点, 要在单链表中找到某个结点的前驱结点,必须从链表的首结点出发依次向...
  • 双向链表:有两个指针,一个指向前一个节点,一个后一个节点。 优点:可以找到前驱和后继,可进可退; 缺点:增加删除节点复杂,需要多分配一个指针存储空间。 适用于需要双向查找节点值的情况。 ...
  • 双向链表的插入及删除图解

    万次阅读 多人点赞 2015-05-06 20:25:54
    双向链表的插入第一步:首先找到插入位置,节点 s 将插入到节点 p 之前 第二步:将节点 s 的前驱指向节点 p 的前驱,即 s->prior = p->prior; 第三步:将节点 p 的前驱的后继指向节点 s 即 p->prior->next = s; ...
  • 【数据结构】双向循环链表

    万次阅读 2018-08-09 23:14:20
    双向循环链表的结构体定义 初始化双向循环链表 尾插法构建双向循环链表 双向循环链表的后序遍历操作 主函数调用 目录: 目录: 各部分实现: ...双向链表的每个结点需要连接前一个结点和后一个结...
  • 前段时间学习
  • 双向链表的插入和删除

    万次阅读 多人点赞 2018-09-21 17:23:50
    双向链表的插入 第一步:首先找到插入位置,节点 s 将插入到节点 p 之前 第二步:将节点 s 的前驱指向节点 p 的前驱,即 s-&gt;prior = p-&gt;prior; 第三步:将节点 p 的前驱的后继指向节点 s 即 p-&...
  • 双向链表存储结构中,删除p所指的结点时需修改指针的操作为 p-&gt;next-&gt;prior=p-&gt;prior; p-&gt;prior-&gt;next=p-&gt;next; p-&gt;next=p-&gt;next-&gt;next;p-&...
  • 双向链表 循环单链表的出现,虽然能够实现从任一结点出发沿着链能找到其前驱结点,但时间耗费是O(n)。如果希望从表中快速确定某一个结点的前驱,另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的...
  • 题目描述:Java 中的 LinkedList 是单向链表还是双向链表? 是双向链表,你可以检查 JDK 的源码。在 Eclipse,你可以使用快捷键 Ctrl + T,直接在编辑器中打开该类。 于是对于LinkedList的实现做了进一步的探索,...
  • 浅谈单链表与双链表的区别

    万次阅读 多人点赞 2018-11-13 17:18:25
    昨天面试官面试的时候问了我一道关于链表的问题:情境如下 面试官:请说一下链表跟数组的区别? 我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),...
  • 双向链表结点的插入和删除算法

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

    千次阅读 2017-11-11 18:01:25
    双向链表 循环单链表的出现,虽然能够实现从任一结点出发沿着链能找到其前驱结点,但时间耗费是O(n)。如果希望从表中快速确定某一个结点的前驱,另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的...
  • 简单实现一个双向循环链表

    千次阅读 2020-09-13 19:47:20
    和单链表类同,双向链表也有带头结点结构和不带头结点结构两种,带头结点的双向链表更为常用;另外,双向链表也可以有循环和非循环两种结构,循环结构的双向链表更为常用。 双向循环链表数据结构 在双向链表中,每个...
1 2 3 4 5 ... 20
收藏数 126,315
精华内容 50,526
关键字:

双向链表