Python数据结构之双向链表的定义与使用方法示例
作者:yupeng 发布时间:2023-06-29 06:20:45
标签:Python,数据结构,双向链表
本文实例讲述了Python数据结构之双向链表的定义与使用方法。分享给大家供大家参考,具体如下:
和单链表类似,只不过是增加了一个指向前面一个元素的指针而已。
示意图:
python 实现代码:
#!/usr/bin/python
# -*- coding: utf-8 -*-
class Node(object):
def __init__(self,val,p=0):
self.data = val
self.next = p
self.prev = p
class LinkList(object):
def __init__(self):
self.head = 0
def __getitem__(self, key):
if self.is_empty():
print 'linklist is empty.'
return
elif key <0 or key > self.getlength():
print 'the given key is error'
return
else:
return self.getitem(key)
def __setitem__(self, key, value):
if self.is_empty():
print 'linklist is empty.'
return
elif key <0 or key > self.getlength():
print 'the given key is error'
return
else:
self.delete(key)
return self.insert(key)
def initlist(self,data):
self.head = Node(data[0])
p = self.head
for i in data[1:]:
node = Node(i)
p.next = node
node.prev = p
p = p.next
def getlength(self):
p = self.head
length = 0
while p!=0:
length+=1
p = p.next
return length
def is_empty(self):
if self.getlength() ==0:
return True
else:
return False
def clear(self):
self.head = 0
def append(self,item):
q = Node(item)
if self.head ==0:
self.head = q
else:
p = self.head
while p.next!=0:
p = p.next
p.next = q
q.prev = p
def getitem(self,index):
if self.is_empty():
print 'Linklist is empty.'
return
j = 0
p = self.head
while p.next!=0 and j <index:
p = p.next
j+=1
if j ==index:
return p.data
else:
print 'target is not exist!'
def insert(self,index,item):
if self.is_empty() or index<0 or index >self.getlength():
print 'Linklist is empty.'
return
if index ==0:
q = Node(item,self.head)
self.head = q
p = self.head
post = self.head
j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1
if index ==j:
q = Node(item,p)
post.next = q
q.prev = post
q.next = p
p.prev = q
def delete(self,index):
if self.is_empty() or index<0 or index >self.getlength():
print 'Linklist is empty.'
return
if index ==0:
q = Node(item,self.head)
self.head = q
p = self.head
post = self.head
j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1
if index ==j:
post.next = p.next
p.next.prev = post
def index(self,value):
if self.is_empty():
print 'Linklist is empty.'
return
p = self.head
i = 0
while p.next!=0 and not p.data ==value:
p = p.next
i+=1
if p.data == value:
return i
else:
return -1
l = LinkList()
l.initlist([1,2,3,4,5])
print "脚本之家测试结果:"
print l.getitem(4)
l.append(6)
print l.getitem(5)
l.insert(4,40)
print l.getitem(3)
print l.getitem(4)
print l.getitem(5)
l.delete(5)
print l.getitem(5)
l.index(5)
结果为;
和单链表结果一样。
PS:双向链表就是将链表首尾相接。
希望本文所述对大家Python程序设计有所帮助。
来源:https://www.cnblogs.com/yupeng/p/3413800.html
0
投稿
猜你喜欢
- 背景:有一个爬虫服务,需要定时从公开网站上拉取一些数据,为了避免被识别为爬虫(防爬虫的识别需要根据很多特征,时间仅仅是其中一个维度),需要在
- 上节我们提到解决赋值中等号两边参数不一致的方法可以通过切片,但在Python3中我们可以利用特定的语法更加方便的处理这种情况,如下示例。当带
- 导语:近年来,全世界都纷纷投身网络热潮。从小企业到大公司,再到网络学校和大学,大家都在努力提升自己的网络影响力,这样既免费为自身品牌做广告,
- Mysql数据库是一个多用户,多线程的关系型数据库,是一个客户机/服务器结构的应用程序。它是对个人用户和商业用户是免费的. Mysql数据库
- SQL Server所谓的分布式查询(Distributed Query)是能够访问存放在同一部计算机或不同计算机上的SQL Server或
- 这篇文章主要介绍了安装PyInstaller失败问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 前不久有个正要毕业的网友给我发邮件,他毕业设计需要实现锁屏的效果,但是他没有能看懂我之前发布的对话框源码,他问能不能把锁屏相关代码说明下,我
- var long2="1988-0w-07";alert(long2.substring(0,4)+"----
- Python 内置的四种常用数据结构:列表(list)、元组(tuple)、字典(dict)以及集合(set)。这四种数据结构一但都可用于保
- 本博文源于绘图基础,主要讲解如何用python的plot绘制气温的折线图。先讲解plot参数如何使用后给出一个气温折线图样例绘制使用plot
- 本文实例讲述了python模拟鼠标拖动操作的方法。分享给大家供大家参考。具体如下:pdf中的书签只有页码,准备把现有书签拖到一个目录中,然后
- PyCharm是Python著名的Python集成开发环境(IDE)conda有Miniconda和Anaconda,前者应该是类似最小化版
- 不错,这个是一个文章详细页,没有左右两栏布局,不过这里我重点要讲的是合理的布局,在稍后的文章中我会详细的介绍浮动元素。好,回到刚才的话题,大
- 当py文件中引用了库face_recognition但是python中没有安装这个库的时候,就会出现No module named '
- 实例如下所示:#!/usr/bin/python# -*- coding:utf8 -*-from selenium import webd
- 我想大多写web的朋友应该和我一样,正则是不可少的,可是每次到用时去百度一下,也麻烦,存在电脑里也得找半天~换了电脑还是得靠google了~
- 本文是小编针对js保留两位小数这个大家经常遇到的经典问题整理了在各种情况下的函数写法以及遇到问题的分析,以下是全部内容:一、我们首先从经典的
- 在IE7还不支持counter 和increment 属性之前,我从来没有用过它们,也从来没有使用过:before 伪元素和content
- 隐藏并修改文件的最后修改时间的asp-webshell。源码:<% '隐藏并修改文件的最后修改时间的aspshell '
- 程序运行效率程序的运行效率分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。时间复杂度主要