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

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结点。