python实现双链表
作者:我的加奈 发布时间:2022-06-20 01:47:48
标签:python,双链表
本文实例为大家分享了python实现双链表的具体代码,供大家参考,具体内容如下
实现双链表需要注意的地方
1、如何插入元素,考虑特殊情况:头节点位置,尾节点位置;一般情况:中间位置
2、如何删除元素,考虑特殊情况:头结点位置,尾节点位置;一般情况:中间位置
代码实现
1.构造节点的类和链表类
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.previous = None
class DoubleLinkList:
'''双链表'''
def __init__(self, node=None):
self._head = node
以下方法均在链表类中实现
2. 判断链表是否为空
def is_empty(self):
return self._head is None
3. 输出链表的长度
def length(self):
count = 0
if self.is_empty():
return count
else:
current = self._head
while current is not None:
count += 1
current = current.next
return count
4. 遍历链表
def travel(self):
current = self._head
while current is not None:
print("{0}".format(current.data), end=" ")
current = current.next
print("")
5.头插法增加新元素
def add(self, item):
node = Node(item)
# 如果链表为空,让头指针指向当前节点
if self.is_empty():
self._head = node
# 注意插入的顺序,
else:
node.next = self._head
self._head.previous = node
self._head = node
6. 尾插法增加新元素
def append(self, item):
node = Node(item)
# 如果链表为空,则直接让头指针指向该节点
if self.is_empty():
self._head = node
# 需要找到尾节点,然后让尾节点的与新的节点进行连接
else:
current = self._head
while current.next is not None:
current = current.next
current.next = node
node.previous = current
7. 查找元素是否存在链表中
def search(self, item):
current = self._head
found = False
while current is not None and not found:
if current.data == item:
found = True
else:
current = current.next
return found
8. 在某个位置中插入元素
def insert(self, item, pos):
# 特殊位置,在第一个位置的时候,头插法
if pos <= 0:
self.add(item)
# 在尾部的时候,使用尾插法
elif pos > self.length() - 1:
self.append(item)
# 中间位置
else:
node = Node(item)
current = self._head
count = 0
while count < pos - 1:
current = current.next
count += 1
# 找到了要插入位置的前驱之后,进行如下操作
node.previous = current
node.next = current.next
current.next.previous = node
current.next = node
# 换一个顺序也可以进行
def insert2(self, item, pos):
if pos <= 0:
self.add(item)
elif pos > self.length() - 1:
self.append(item)
else:
node = Node(item)
current = self._head
count = 0
while count < pos:
current = current.next
count += 1
node.next = current
node.previous = current.previous
current.previous.next = node
current.previous = node
9. 删除元素
def remove(self, item):
current = self._head
if self.is_empty():
return
elif current.data == item:
# 第一个节点就是目标节点,那么需要将下一个节点的前驱改为None 然后再将head指向下一个节点
current.next.previous = None
self._head = current.next
else:
# 找到要删除的元素节点
while current is not None and current.data != item:
current = current.next
if current is None:
print("not found {0}".format(item))
# 如果尾节点是目标节点,让前驱节点指向None
elif current.next is None:
current.previous.next = None
# 中间位置,因为是双链表,可以用前驱指针操作
else:
current.previous.next = current.next
current.next.previous = current.previous
# 第二种写法
def remove2(self, item):
"""删除元素"""
if self.is_empty():
return
else:
cur = self._head
if cur.data == item:
# 如果首节点的元素即是要删除的元素
if cur.next is None:
# 如果链表只有这一个节点
self._head = None
else:
# 将第二个节点的prev设置为None
cur.next.prev = None
# 将_head指向第二个节点
self._head = cur.next
return
while cur is not None:
if cur.data == item:
# 将cur的前一个节点的next指向cur的后一个节点
cur.prev.next = cur.next
# 将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
10. 演示
my_list = DoubleLinkList()
print("add操作")
my_list.add(98)
my_list.add(99)
my_list.add(100)
my_list.travel()
print("{:#^50}".format(""))
print("append操作")
my_list.append(86)
my_list.append(85)
my_list.append(88)
my_list.travel()
print("{:#^50}".format(""))
print("insert2操作")
my_list.insert2(66, 3)
my_list.insert2(77, 0)
my_list.insert2(55, 10)
my_list.travel()
print("{:#^50}".format(""))
print("insert操作")
my_list.insert(90, 4)
my_list.insert(123, 5)
my_list.travel()
print("{:#^50}".format(""))
print("search操作")
print(my_list.search(100))
print(my_list.search(1998))
print("{:#^50}".format(""))
print("remove操作")
my_list.remove(56)
my_list.remove(123)
my_list.remove(77)
my_list.remove(55)
my_list.travel()
print("{:#^50}".format(""))
print("remove2操作")
my_list.travel()
my_list.remove2(100)
my_list.remove2(99)
my_list.remove2(98)
my_list.travel()
来源:https://blog.csdn.net/CSDNwg/article/details/122492275


猜你喜欢
- 因为神奇的中文有时也是会遇到国外同学都不知道原因导致一些神奇滴问题,所以要用更神奇的英文来解决问题。Mac OS的一些:华文细黑:STHei
- 一、访问者模式(Visitor Pattern)数据结构中保存着许多元素,当我们希望改变一种对元素的处理方式时,要避免重复的修改数据结构。那
- 具体编译过成与正常的Python源代码在x86平台上的过程无异,此篇随笔仅当用作复制黏贴的备忘录。不得不说在一个老旧系统上安装一个老旧的Py
- 本文实例讲述了Python迭代器定义与简单用法。分享给大家供大家参考,具体如下:一、什么是迭代器迭代,顾名思义就是重复做一些事很多次(就现在
- 今天来说说编程语言中的动态类型语言与鸭子类型。动态语言 * 对动态语言的定义:动态编程语言是一类在运行时可以改变其结构的语言:例如新的函数
- MySQL为开源数据库,因此可以基于源码实现安装。基于源码安装有更多的灵活性。也就是说我们可以针对自己的硬件平台选用合适的编译器来优化编译后
- Rex 是 Perl 编写的基于 SSH 链接的集群配置管理系统,语法上类似 Puppet DSL。官网中文版见 http://rex.pe
- 限制访问可以基于某种权限,某些检查或者为login视图提供不同的位置,这些实现方式大致相同。一般的方法是直接在视图的 request.use
- 本文实例讲述了python使用webbrowser浏览指定url的方法。分享给大家供大家参考。具体如下:这段代码提示用户输入关键词,通过we
- 前言mysql查询使用select命令,配合limit,offset参数可以读取指定范围的记录。本文将介绍mysql查询时,offset过大
- 最近开始实习,工作技术栈主要Python和Golang,目前的任务把Python模块重构为GO模块,然后出现了一个问题,就是要将一个结构体按
- 本文实例讲述了Python使用win32 COM实现Excel的写入与保存功能。分享给大家供大家参考,具体如下:很久之前通过东拼西凑实现过使
- 前言大家好,说起动态条形图,之前推荐过两个 Python 库,比如Bar Chart Race、Pandas_Alive,都可以实现。今天就
- MySQL超长字符截断又名"SQL-Column-Truncation",是安全研究者Stefan Esser在2008
- 我们都知道,python可以通过threading module来创建新的线程,然而在创建线程的线程(父线程)关闭之后,相应的子线程可能却没
- 万维网联盟(W3C)发布了HTML 5规格说明书的草稿 ,这是自HTML 4在十多年前发布以来的第一个主要的修订版.在这期间,随着开发者逐渐
- 很久之前曾经总结过一篇博客“MySQL如何找出未提交事务信息”,现在看来,这篇文章中不少知识点或观点都略显肤浅,或者说不够深入,甚至部分结论
- 常见面试题Vue 如何监控数组defineProperty 真的不能监测数组变化吗?Vue 是如何追踪数据发生变化在 Vue 中当我们把一个
- 本文实例讲述了使用symfony命令创建项目的方法。分享给大家供大家参考,具体如下:概况这一章节描述一个Symfony项目的合理结构框架,并
- 在这系列视觉设计的文章间隙插一篇字体单位的文章。前文说了,字体单位应该用em而不用px,原因简单来说就是支持IE6下的字体缩放,在页面中按c