# LList.py from ListNode import ListNode class LList(object): #------------------------------------------------------------ def __init__(self, seq=()): """create an LList. member variables are self.head and self.size post: creates a list containing items in seq""" self.head = None if seq != (): #There are nodes to insert # Insert the nodes starting from the last sequence element for k in range(-1, -len(seq) -1, -1): self.insertathead(seq[k]) self.size = len(seq) #------------------------------------------------------------ def insertathead(self, data): '''creates a new ListNode with item data, and inserts it at the head of the LList post: new ListNode with data added at head of LList''' n = ListNode(data, self.head) self.head = n #------------------------------------------------------------ def __len__(self): '''post: returns number of items in the list''' return self.size #------------------------------------------------------------ def _find(self, position): '''private method that returns node that is at location position in the list (0 is first item, size-1 is last item) pre: 0 <= position < self.size post: returns the ListNode at the specified position in the list''' assert 0 <= position < self.size node = self.head # move forward until we reach the specified node for i in range(position): node = node.link return node #------------------------------------------------------------ def append(self, x): '''appends x onto end of the list post: x is appended onto the end of the list''' # create a new node containing x newNode = ListNode(x) # link it into the end of the list if self.head is not None: # non-empty list node = self._find(self.size - 1) node.link = newNode else: # empty list # set self.head to new node self.head = newNode self.size += 1 #------------------------------------------------------------ def __getitem__(self, position): '''return data item at location position pre: 0 <= position < size post: returns data item at the specified position''' node = self._find(position) return node.item #------------------------------------------------------------ def __setitem__(self, position, value): '''set data item at location position to value pre: 0 <= position < self.size post: sets the data item at the specified position to value''' node = self._find(position) node.item = value #------------------------------------------------------------ def __delitem__(self, position): '''delete item at location position from the list pre: 0 <= position < self.size post: the item at the specified position is removed from the list''' assert 0 <= position < self.size self._delete(position) #------------------------------------------------------------ def _delete(self, position): #private method to delete item at location position from the list # pre: 0 <= position < self.size # post: the item at the specified position is removed from the list # and the item is returned (for use with pop) if position == 0: # save item from the initial node item = self.head.item # change self.head to point "over" the deleted node self.head = self.head.link else: # find the node immediately before the one to delete prev_node = self._find(position - 1) # save the item from node to delete item = prev_node.link.item # change predecessor to point "over" the deleted node prev_node.link = prev_node.link.link self.size -= 1 return item #------------------------------------------------------------ def pop(self, i=None): '''returns and removes at position i from list; the default is to return and remove the last item pre: self.size > 0 and ((i is None or (0 <= i < self.size)) post: if i is None, the last item in the list is removed and returned; otherwise the item at position i is removed and returned''' assert self.size > 0 and (i is None or (0 <= i < self.size)) # default is to delete last item # i could be zero so need to compare to None if i is None: i = self.size - 1 return self._delete(i) #------------------------------------------------------------ def insert(self, i, x): '''inserts x at position i in the list pre: 0 <= i <= self.size post: x is inserted into the list at position i and old elements from position i..oldsize-1 are at positions i+1..newsize-1''' assert 0 <= i <= self.size if i == 0: # insert before position 0 requires updating self.head self.head = ListNode(x, self.head) else: # find item that node is to be insert after node = self._find(i - 1) node.link = ListNode(x, node.link) self.size += 1 #------------------------------------------------------------ def __copy__(self): '''post: returns a new LList object that is a shallow copy of self''' a = LList() node = self.head while node is not None: a.append(node.item) node = node.link return a #------------------------------------------------------------ ## def __iter__(self): ## # generator version works in both Python2 and Python3 ## node = self.head ## while node is not None: ## yield node.item ## node = node.link #------------------------------------------------------------ def __iter__(self): return LListIterator(self.head) #------------------------------------------------------------ class LListIterator(object): #------------------------------------------------------------ def __init__(self, head): self.currnode = head #------------------------------------------------------------ # Python2 version def next(self): if self.currnode is None: raise StopIteration else: item = self.currnode.item self.currnode = self.currnode.link return item #------------------------------------------------------------ # Python3 version def __next__(self): if self.currnode is None: raise StopIteration else: item = self.currnode.item self.currnode = self.currnode.link return item