双链表插入、删除操作单步解析(十四)

1.双链表定义 单链表只能向后操作,不能向前操作。双链表可以向前和向后操作。 双链表特点&#xf…

1.双链表定义

单链表只能向后操作,不能向前操作。双链表可以向前和向后操作。

双链表特点:以下图解释

一个前驱指针:ai的前驱指针,指向ai-1结点,即存放ai-1的地址。

数据域:存放数据

一个后驱指针:ai的后驱指针,指向ai+1结点,即存放ai+1的地址。

以上概念是是否能理解双向链表的关键。

2.插入操作

在第i个结点前面,插入一个e结点

分析:

<1>.p->prior->next = s;

p:表示指向ai结点的指针

p->prior:表示存放ai-1结点的地址。

p->prior->next:表示存放ai-1结点的地址的后驱指针,没插入e结点之前,是指向ai结点的,但是现在让它指向e结点的地址(指针s).

翻译:将ai-1结点后驱指针指向s,即保存了s结点的地址。

<2>.s->prior = p->prior;

s:指向要插入e结点的指针,即e结点的地址。

s->prior:e结点地址s的前驱指针,存放着上一个结点的地址。

p:表示指向ai结点的指针,即ai结点的地址。

p->prior:表示存放ai-1结点的地址。

翻译:s结点的前驱指针指向了ai-1的地址。

<3>.s->next = p;

s:指向要插入e结点的指针,即e结点的地址。

s->next:s结点的后驱指针;

p:表示指向ai结点的指针,即ai结点的地址。

翻译:s结点的后驱指针指向p结点,即s结点的后驱指针保存了ai结点的地址。

<4>.p->prior = s;

p:表示指向ai结点的指针,即ai结点的地址。

p->prior:表示存放ai-1结点的地址。

s:指向要插入e结点的指针,即e结点的地址。

翻译:指向ai结点的p指针的前驱指针指向e结点,即ai结点前驱指针保存了s结点的地址。

至此,将e结点插入在ai-1和ai结点之间。

3.删除操作

删除ai结点。

分析:

<1>.p->prior->next = p->next;

p:指向ai结点的指针。

p->prior:ai结点的前驱指针,保存了ai-1结点的地址。

p->prior->next:ai-1结点的后继指针域,实际存放着ai结点的地址。

p->next:ai结点的后继指针,存放着ai+1结点的地址。

翻译:将ai-1结点的后继指针指向ai结点的后继指针,因为ai的后继指针存放着ai+1的地址,其实就是ai-1结点的后指针指向了ai+1结点的地址,即保存了ai+1结点的地址,跳过了ai结点。

<2>.p->next->prior = p->prior;

p:指向ai结点的指针。

p->next:ai结点的后继指针,保存着ai+1结点的地址。

p->next->prior:ai+1结点的前驱指针,保存着ai结点的地址。

p->prior:ai结点的前驱指针,保存了ai-1结点的地址。

翻译:将ai+1结点的前驱指针,指向ai-1结点的地址。

至此,就删除了ai结点。

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/3410.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部