Python数据结构与算法学习第四天

1043-李同学

发表文章数:31

热门标签

首页 » 数据结构 » 正文

一.单项循环列表

单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。
Python数据结构与算法学习第四天
操作:
1.is_empty() 判断链表是否为空
2.length() 返回链表的长度
3.travel() 遍历
4.add(item) 在头部添加一个节点
5.append(item) 在尾部添加一个节点
6.insert(pos, item) 在指定位置pos添加节点
7.remove(item) 删除一个节点
8.search(item) 查找节点是否存在

代码实现:
Python数据结构与算法学习第四天
上图代码为定义节点。
Python数据结构与算法学习第四天
上图为创建列表,最后节点的next不再指向None,而是指向第一个元素,如果只有一个元素,则指向元素本身。

(1) is_empty() 链表是否为空
Python数据结构与算法学习第四天
上图代码为测试链表是否为空,与测试单链表是否为空代码一样。

(2)length() 链表长度
Python数据结构与算法学习第四天
上图代码为计算列表长度。与计算单项列表不同之处在于count是从1开始计算。这是因为当cur指针指到最后一个元素时,就不再进入循环计算计数。

(3)travel() 遍历整个链表
Python数据结构与算法学习第四天
上图代码为遍历整个链表,首先先判断是否为空链表,如果不是,则进入循环,当cur指到最后一个元素时,不再进入循环,所以不会输出最后一个元素,就需要在函数的最后单独写输出最后一个元素的代码。

(4)add(item) 链表头部添加元素
Python数据结构与算法学习第四天
上图代码为在头部添加元素,首先考虑特殊情况,当链表为空,添加头元素时,则将head指向新添加的node,node.next指向自己本身。在一般情况下,需要先将将cur指向到最后一个元素,这是因为添加头元素后,需要将最后一个元素指向第一个新元素。当cur指向最后一个元素时,将cur.next指向新的node,再讲头元素指向新node。

(5)append(item) 链表尾部添加元素
Python数据结构与算法学习第四天
上图代码是在尾部添加元素,首先考虑特殊情况,如果是空链表,则添加头元素时,则将head指向新添加的node,node.next指向自己本身。在一般情况下需要cur指针指到最后一个元素,新的node.next先指向最后一个元素的next值,即第一个元素,再讲最后一个元素的next指向新node。

(6)insert(pos, item) 指定位置添加元素
Python数据结构与算法学习第四天
上图为在指定位置添加元素,与单项链表一致。

(7)remove(item) 删除节点
Python数据结构与算法学习第四天
上图代码为删除元素,是最为复杂的一个函数。首先,先判断是否为空元素,若不是,就进入循环进行遍历,在考虑特殊情况,若删除的元素为头元素,则定义rear指针,让rear指向最后一个元素,因为cur正在指向第一个元素,所以将最后一个元素的next区域指向cur的next区域,即第二个元素,head也指向cur.next,完成第一个元素的删除。一般情况下,则进行else中的语句。另外两个特殊情况是当列表中只有一个元素和对尾部元素进行删除,在这两个情况下,cur指针都指向最后一个或者第一个元素,不进入循环,当列表中只有一个元素时,将head直接指向None即可。当对尾部元素进行删除时,则将倒数第二个元素,即pre指向的元素的next区域指向最后一个元素的next区域即可。

(8)search(item) 查找节点是否存在Python数据结构与算法学习第四天
上图代码为查询链表中是否有该元素,进入循环进行判断。特殊情况为当cur指向最后一个元素时,不再进入循环进行判断,则需要手动添加一行代码判断最后一个元素是否与item相等。

二.双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
Python数据结构与算法学习第四天
操作:
is_empty() 链表是否为空
length() 链表长度
travel() 遍历链表
add(item) 链表头部添加
append(item) 链表尾部添加
insert(pos, item) 指定位置添加
remove(item) 删除节点
search(item) 查找节点是否存在

代码实现:
Python数据结构与算法学习第四天
首先定义节点,prev及next都默认指向None。

Python数据结构与算法学习第四天
上图代码为创建列表。

(1) is_empty() 链表是否为空
Python数据结构与算法学习第四天
上图代码为判断该链表是否为空,即判断头元素的指向。

(2)length() 链表长度
Python数据结构与算法学习第四天
上图代码为计算列表的长度,与单向链表代码一样。

(3)travel() 遍历整个链表
Python数据结构与算法学习第四天
上图代码为编列整个链表,与单向链表代码一样。

(4)add(item) 链表头部添加元素
Python数据结构与算法学习第四天
上图代码为在头部添加元素,首相新节点的next区域指向head,即指向原来第一个元素,再将node.next.prev即原来第一个元素的prev区域指向新节点,再将head指向新node,就完成了头部元素的添加。

(5)append(item) 链表尾部添加元素
Python数据结构与算法学习第四天
上图代码是为尾部添加元素,首先判断该链表是否为空,若为空,则将head直接指向新node。一般情况下,利用cur进行循环,将cur指向当前最后一个元素,将cur.next指向新node,新的node.prev指向cur,完成最后一个元素添加。

(6)insert(pos, item) 指定位置添加元素
Python数据结构与算法学习第四天
上图代码为在指定位置添加元素。当pos小于或者大于链表长度时的特殊情况,与单向链表一样。在一般情况下,首先找到插入位置的元素,将新node.prev指向cur指向的prev区域,即指向前一个元素,再将node.next指向cur。将cur.prev.next即前一个元素指向新node,在将cur的prev区域指向新node。

(7)remove(item) 删除节点
Python数据结构与算法学习第四天
上图为删除元素代码,先考虑特殊情况,当删除元素为头元素是直接将head指向第一个元素的next,即第二个元素,如果列表只有一个元素的话,则将head指向None,如果不是的话,则将第二个原色的prev指向None。一般情况下,则将cur的前一个元素的next指向cur的next区域,如果cur的next区域存在,则将后一个元素的prev元素指向cur的前一个元素。如果不存在,就是将前一个元素的next直接指向None。

(8)search(item) 查找节点是否存在
Python数据结构与算法学习第四天
上图代码为查询是否有该元素,与单向循环代码相同。

未经允许不得转载:作者:1043-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法学习第四天》 发布于2020-06-04

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录