# Doubly-linked list routines # Useful for, e.g., equivalence "sets" # Note that several routines take as argument (or return as result) # a DNode instead of a datum. This facilitates middle-of-list # insertion and removal. class DNode: def __init__(self, initdata): self.data = initdata self.next = self # circular linking simplifies list manipulation self.prev = self def isSingleton(self): return self.next == self def insertBefore(self, other): assert other.isSingleton() other.prev = self.prev other.next = self self.prev.next = other self.prev = other def insertAfter(self, other): assert other.isSingleton() other.prev = self other.next = self.next self.next.prev = other self.next = other def remove(self): assert not self.isSingleton() self.prev.next = self.next self.next.prev = self.prev self.next = self self.prev = self def __str__(self): return str(self.data) class DList: def __init__(self): self.headNode = DNode(None) def isEmpty(self): return self.headNode.isSingleton() def addFront(self, node): # inserts node, not data self.headNode.insertAfter(node) def addBack(self, node): # inserts node, not data self.headNode.insertBefore(node) def length(self): current = self.headNode count = 0 while current.next != self.headNode: count = count + 1 current = current.next return count def search(self, item): # returns node, or None if not found current = self.headNode.next while current != self.headNode: if current.data == item: return current else: current = current.next return None def remove(self, item): # returns node, or None if not found node = self.search(item) if node != None: node.remove() return node return node def __str__(self): rtn = "" current = self.headNode.next while current != self.headNode: rtn += (" " + str(current)) current = current.next return rtn def clone(self): rtn = DList() current = self.headNode.next while current != self.headNode: rtn.addBack(DNode(current.data)) current = current.next return rtn def merge(self, other): # allows duplicates rtn = self.clone() current = other.headNode.next while current != other.headNode: rtn.addBack(DNode(current.data)) current = current.next return rtn class Deque: def __init__(self): self.L = DList() def insertFront(self, val): self.L.addFront(DNode(val)) def insertBack(self, val): self.L.addBack(DNode(val)) def isEmpty(self): return self.L.isEmpty() def removeFront(self): if self.isEmpty(): return None rtn = self.L.headNode.next rtn.remove() return rtn.data def removeBack(self): if self.isEmpty(): return None rtn = self.L.headNode.prev rtn.remove() return rtn.data