Python数据结构之双向链表的定义与使用方法示例

时间:2021-05-22

本文实例讲述了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 = pclass 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 -1l = 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相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章