首页 > 代码库 > python——数据结构之单链表的实现
python——数据结构之单链表的实现
链表的定义：
链表(linked list)是由一组被称为结点的数据元素组成的数据结构，每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址 信息，所以用一个变量就能够访问整个结点序列。也就是说，结点包含两部分信息：一部分用于存储数据元素的值，称为信息域；另一部分用于存储下一个数据元素 地址的指针，称为指针域。链表中的第一个结点的地址存储在一个单独的结点中，称为头结点或首结点。链表中的最后一个结点没有后继元素，其指针域为空。
#!/usr/bin/python# -*- coding: utf-8 -*-class Node(object): def __init__(self,val,p=0): self.data = val self.next = 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 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 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.next = p 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 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 =http://www.mamicode.com/=value: p = p.next i+=1 if p.data =http://www.mamicode.com/= value: return i else: return -1l = LinkList()l.initlist([1,2,3,4,5])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)
python——数据结构之单链表的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。