coinor.blimpy.LinkedList'

56 '''implementation of link list data structure. 57 The behavior is designed to be the same as a Python list. 58 For efficiency when using the list as a stack, the list is stored 59 such that the last item in the list is the head node. Thus, the 60 append, push, pop, and most other methods are efficient, but 61 forward iteration is not. Reverse iteration is efficient, however, 62 pre: Node is the head node of a linked list and length is the length of 63 that list 64 post: creates a LinkedList type object 65 ''' 66

67 - def __init__(self, Node=None, length = 0):

68 ''' constructor method of the class 69 pre: self''' 70 self.head = Node 71 self.length = length

72

73 - def __contains__(self, item):

74 ''' sequential search method 75 pre: self, item to be searched 76 post: True if list contains the item, False otherwise''' 77 current = self.head 78 while current != None: 79 if current.getData() == item: 80 return True 81 else: 82 current = current.getNext() 83 return False

84

85 - def remove(self, item):

86 ''' class method that removes the first occurrence of the given item 87 if there is one 88 pre: self, item ''' 89 current = self.head 90 previous = None 91 found = False 92 while not found and current != None: 93 if current.getData() == item: 94 found = True 95 else: 96 previous = current 97 current = current.getNext() 98 99 if not found: 100 return False 101 elif previous == None: 102 self.head = current.getNext() 103 else: 104 previous.setNext(current.getNext()) 105 self.length -= 1 106 return True

107

108 - def __delitem__(self, position):

109 if self.pop(position) == None: 110 raise KeyError, "Index out of bounds"

111

112 - def insert(self, position, item):

113 ''' class method that inserts item to the given position 114 pre: self, position, item 115 position should not be greater than length of the list''' 116 previous = None 117 current = self.head 118 for i in range(self.length - position): 119 previous = current 120 current = current.getNext() 121 tmp = Node(item, current) 122 if previous == None: 123 self.head = tmp 124 else: 125 previous.setNext(tmp) 126 self.length += 1

127

128 - def peek(self, index = None):

129 ''' class method that retrieves, but does not remove, 130 the head (first element) of this list 131 pre: self 132 post: the data of the head of the list or None if the list is empty''' 133 if self.head == None: 134 return None 135 elif index == None: 136 return self.head.getData() 137 else: 138 return self[index]

139

140 - def pop(self, index = None):

141 ''' class method that removes the item at the given position 142 in the list, and returns it. If no index is specified 143 removes and returns the last item in the list 144 pre: self, position (optional), position should be less than length 145 of the list, list should not be empty 146 post: return the item at given index or last item if not specified''' 147 if (index is not None and 148 (index > self.length -1 or index < 0)): 149 return None 150 previous = None 151 current = self.head 152 if index == None: 153 current = self.head 154 self.head = self.head.getNext() 155 else: 156 for i in range(self.length - index - 1): 157 previous = current 158 current = current.getNext() 159 if previous == None: 160 self.head = current.getNext() 161 else: 162 previous.setNext(current.getNext()) 163 self.length -= 1 164 return current.data

165

166 - def __len__(self):

167 ''' class method that returns the number of items in the list 168 pre: self 169 post: returns number of items in the list''' 170 return self.length

171

172 - def append(self, item):

173 ''' class method that appends the given item at the end of the list 174 pre: self, item''' 175 current = self.head 176 self.head = Node(item) 177 self.head.nextNode = current 178 self.length += 1

179

180 - def extend(self, otherLinkedList):

181 ''' class method that extends the list by adding otherLinkedList at the 182 end of the self 183 pre: self, otherLinkedList''' 184 #if self.head==None: 185 # self.head = otherLinkedList.head 186 # return 187 #if otherLinkedList.head==None: 188 # return 189 for item in otherLinkedList: 190 self.append(item)

191

192 - def index(self, item):

193 ''' class method that returns the index of the first occurance of 194 item, returns None if there is no any item. 195 pre: self, item 196 post: item index or None''' 197 current = self.head 198 for index in range(self.length, 0 , -1): 199 if current == None: 200 break 201 if current.getData() == item: 202 return index 203 current = current.getNext() 204 return None

205

206 - def count(self, item):

207 ''' class method that counts the number of occurances of item 208 in the list 209 pre: self, item 210 post: number of occurances of item in the list''' 211 count = 0 212 current = self.head 213 while current != None: 214 if current.getData() == item: 215 count += 1 216 return count

217

218 - def __getitem__ (self, index):

219 ''' replace built-in class method that returns the item for the given 220 index 221 pre: self, index, index should be less than length of list, list 222 should not be empty 223 post: return item for the given index''' 224 if isinstance(index, slice): 225 if index.start == None or index.start < 0: 226 start = 0 227 else: 228 start = index.start 229 if index.stop == None or index.stop > self.length: 230 stop = self.length 231 else: 232 stop = index.stop 233 current = self.head 234 for i in range(self.length - stop): 235 current = current.getNext() 236 newHead = Node(deepcopy(current.data)) 237 previous = newHead 238 for i in range(stop - start -1): 239 if current.getNext() == None: 240 break 241 current = current.getNext() 242 previous.setNext(Node(deepcopy(current.data))) 243 previous = previous.getNext() 244 return LinkedList(newHead, stop - start) 245 else: 246 current = self.head 247 if index < 0: 248 if -index > self.length: 249 raise IndexError 250 return self[self.length+index] 251 else: 252 i = self.length - 1 253 while True: 254 if current == None: 255 raise IndexError 256 if i <= index: 257 break 258 current = current.getNext() 259 i -= 1 260 return current.getData()

261

262 - def __iter__(self):

263 ''' built-in class method, makes LinkedList objects iterable 264 pre: self 265 post: self.head, first Node on the list''' 266 return self.forward()

267

268 - def __reversed__(self):

269 ''' built-in class method, makes LinkedList objects reverse iterable 270 pre: self 271 post: self.head, first Node on the list''' 272 return self.backward()

273

274 - def __repr__(self):

275 s = ']' 276 current = self.head 277 while current != None: 278 if current.getNext() == None: 279 s = '['+str(current.getData())+s 280 return s 281 s = ', '+str(current.getData())+s 282 current = current.getNext() 283 return '[]'

284

285 - def forward(self):

286 for i in range(self.length): 287 yield self[i]

288

289 - def backward(self):

290 current = self.head 291 while current != None: 292 yield current.getData() 293 current = current.getNext()

294

295 - def __add__(self, otherLinkedList):

296 new_list = self.__class__() 297 new_list.extend(self) 298 new_list.extend(otherLinkedList) 299 return new_list

Source Code for Module coinor.blimpy.LinkedList'