双链表插入、删除操作单步解析(十四)
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结点。
相关文章
- 通俗易懂!一文看懂手机Root的操作与防护
- Oracle归档日志文件操作指南(oracle归档日志文件)
- 操作Linux操作实现中控考勤机全套管理(中控考勤机linux)
- Linux中的目录操作函数解析(linux目录操作函数)
- Oracle操作入门:50道常见操作题解析(oracle操作题)
- Oracle操作日志:深入解析(oracle操作日志)
- Git 分支操作介绍
- 轻松安装绿色版MySQL,操作更简便(绿色版的mysql安装)
- 灵活操作Oracle数据库:脚本技术指南(oracle数据库脚本)
- 解析Linux权限Mask:实现安全操作(linux权限mask)
- PeaZip是跨平台基于FreePascal的免费绿色便携的解压缩软件。可以运行在Linux系统和Windows系统。支持鼠标右键操作。
- Linux微型系统:一次有效的低耗操作体验(linux 微型 系统)
- MySQL死锁解析并避免数据库并发操作中的问题(mysql中什么是死锁)
- MySQL数据库操作中的去重操作(mysql中不重复的命令)
- MySQL实现两表间去重操作(mysql 两表间去重)
- MySQL汉化包下载,让数据库操作更便捷(mysql下载汉化包)
- java对XML文件的解析、节点的增加、删除操作总结
- 解析PHP中常见的mongodb查询操作
- C字符串操作函数的实现详细解析
- C语言文件操作函数freopen详细解析
- C++中队列的建立与操作详细解析