根据Problem Solving with Algorithms and Data Structures using Python 一书用python实现链表

书籍在线网址http://interactivepython.org/runestone/static/pythonds/index.html

中文翻译书籍：https://facert.gitbooks.io/python-data-structure-cn/

1 class Node:     #链表中单个节点的实现  2     def __init__(self,initdata):  3         self.data=initdata  4         self.next=None  5   6     def getDate(self):      #获取当前节点数据域值  7         return self.data  8   9     def getNext(self):      #获取指向下一个节点的指针域值 10         return self.next 11  12     def setData(self,newdata):  #重新设置当前节点数据域值 13         self.data=newdata 14  15     def setNext(self,newnext):  #重新设置当前节点指针域指针指向 16         self.next=newnext 17  18 class UnorderedList: 19     def __init__(self):     #初始化无序列空表 20         self.head=None 21  22     def isEmpty(self): 23         return self.head==None 24  25     def add(self,item):     #使用头插法将节点插入链表 26         temp=Node(item) 27         temp.setNext(self.head) 28         self.head=temp 29  30     def append(self,item):      #使用尾插法将节点插入链表 31         temp=Node(item) 32         if self.isEmpty():  #链表为空直接将头指针指向新的节点 33             self.head=temp 34         else: 35             current=self.head 36             while current.getNext()!=None:  #遍历一遍链表中节点 37                 current=current.getNext() 38             current.setNext(temp)           #最后将节点插入链表尾部 39  40     def size(self):        #统计节点数 41         current=self.head 42         count=0 43         while current!=None: 44             count+=1 45             current=current.getNext() 46         return count 47  48     def travel(self):   #遍历链表 49         print('遍历链表') 50         current=self.head 51         list1=[] 52         while current!=None: 53             list1.append(current.getDate()) 54             current=current.getNext() 55         print(list1) 56  57     def search(self,item):  #搜索节点，返回Boolean值类型 58         current=self.head 59         found=False 60         while current!=None and not found: 61             if current.getDate() ==item: 62                 found=True 63             else: 64                 current=current.getNext() 65         return found 66  67     def index(self,item): #搜索节点，返还节点所在索引值 68         current=self.head 69         count=0 70         found=None 71         while current!=None and not found: 72             count+=1 73             if current.getDate()==item: 74                 found=True 75             else: 76                 current=current.getNext() 77         if found: 78             return count 79         else: 80             str1='%s is not in theList'%item 81             return str1 82  83     def remove(self,item): 84         current=self.head 85         previous=None 86         found=False 87         while not found: 88             if current.getDate()==item: 89                 found=True 90             else: 91                 previous=current 92                 current=current.getNext() 93         if previous==None:      #删除的为第一个节点 94             self.head=current.getNext() 95         else:                   #删除的不是第一个节点 96             previous.setNext(current.getNext()) 97  98     def insert(self,pos,item):  #在链表指定位置插入节点 99         if pos<=1:              #需要在第一个索引处插入节点，只需使用头插法将节点插入链表100             self.add(item)101         elif pos>self.size():   #如果插入的位置大于链表长度，尾插法插入节点102             self.append(item)103         else:104             temp=Node(item)105             count=1106             pre=None107             current=self.head108             while count