python 实现无序列表

  1 # -*- coding:utf-8 -*-
  2 class Node:
  3     def __init__(self, initdata):
  4         self.data = initdata
  5         self.next = None
  6 
  7     def getData(self):
  8         return self.data
  9 
 10     def getNext(self):
 11         return self.next
 12 
 13     def setData(self, newdata):
 14         self.data = newdata
 15 
 16     def setNext(self, newnext):
 17         self.next = newnext
 18 
 19 
 20 class UnorderedList:
 21     def __init__(self):
 22         self.head = None
 23 
 24     def isEmpty(self):
 25         return self.head == None
 26 
 27     def add(self, item):
 28         temp = Node(item)
 29         temp.setNext(self.head)
 30         self.head = temp
 31 
 32     def size(self):
 33         current = self.head
 34         count = 0
 35         while current != None:
 36             count = count + 1
 37             current = current.getNext()
 38         return count
 39 
 40     def travel(self):
 41         current = self.head
 42         while current != None:
 43             print current.getData()
 44             current = current.getNext()
 45 
 46     def search(self, item):
 47         current = self.head
 48         found = False
 49         while current != None and not found:
 50             if current.getData() == item:
 51                 found = True
 52             else:
 53                 current = current.getNext()
 54         return found
 55 
 56     def remove(self, item):
 57         current = self.head
 58         previous = None
 59         found = False
 60         while not found:
 61             if current.getData() == item:
 62                 found = True
 63             else:
 64                 previous = current
 65                 current = current.getNext()
 66         if previous == None:
 67             self.head = current.getNext()
 68         else:
 69             previous.setNext(current.getNext())
 70 
 71     def append(self, item):
 72         temp = Node(item)
 73         if self.isEmpty():
 74             self.head = temp
 75         else:
 76             current = self.head
 77             while current.getNext() != None:
 78                 current = current.getNext()
 79             current.setNext(temp)
 80 
 81     def index(self, item):
 82         current = self.head
 83         count = 0
 84         found = False
 85         while current != None and not found:
 86             count += 1
 87             if current.getData() == item:
 88                 found = True
 89             else:
 90                 current = current.getNext()
 91         if found:
 92             return count
 93         else:
 94             raise ValueError, '%s is not in this unorderedList' %item
 95 
 96     def insert(self, pos, item):
 97         if pos <= 1:
 98             self.add(item)
 99         elif pos > self.size():
100             self.append(item)
101         else:
102             temp = Node(item)
103             count = 1
104             previous = None
105             current = self.head
106             while count < pos:
107                 count += 1
108                 previous = current
109                 current = current.getNext()
110             previous.setNext(temp)
111             temp.setNext(current)
112 
113 if __name__ == '__main__':
114     t = UnorderedList()
115     for i in range(10):
116         t.append(i)
117     print t.size()
118     t.travel()
119     print t.search(5)
120     print t.index(3)
121     t.remove(8)
122     t.travel()
123     t.insert(2, 12)
124     t.travel()