Software Engineering 470- Program 11 In this example, you are to implement a dou

Question

Software Engineering 470- Program 11

In this example, you are to implement a doubly-linked list in Python, using the template provided. :

Your program must:

Implement a doubly linked list ADT

Use the provided template

node: as is, except, additional methods may be added. You may use it as an external or inner class. This must be used as the sole internal data structure

linked_list: use/maintain class name, method signatures, and invariant

Methods must be implemented as described in template file

Provide direct access, addition, and removal to the first and last element of the list (so, it can be used as an efficient queue)

Allow for efficient insertion and removal of any given node in the list

Run in Python3

class node : def __init__(self, item, prev = None, next = None) : self.item = item self.prev = prev self.next = next def __str__(self) : return str(self.item) def __repr__(self) : return repr(self.item) ## linked_list # Implements a doubly-linked list ADT # @invariant (len == 0 and head == None and tail == None) # or (len != 0 and head != None and tail != None and head.prev == None and tail.next == None) # You do not have to call your data members head/tail, but should be descriptive names class linked_list : ## constructor - iterable is an iterable object that initializes # the linked_list in the order iterable is traversed def __init__(self, iterable = []) : pass ## constant time access to first/last node, respectively # @returns the first/last node, respectively def front(self) : pass def back(self) : pass ## constant time insertion of a data item (any element) # as the first/last (respectively) element def push_front(self, item) : pass def push_back(self, item) : pass ## constant time removal of the first/last (respectively) node/item # @returns the item (not the node) def pop_front(self) : pass def pop_back(self) : pass ## Turns list into a string representation. # Strings prints identical to how # it would if it were a Python list # @returns the string representation def __str__(self) : pass ## Provides an iterator over an instance of the linked list # iterator is a separate class (either external or inner) # that iterates from first to last. # __next__ returns a node # @returns an iterator def __iter__(self) : pass ## Generator function to iterate over the linked list from last to first. # Generates nodes. def __reversed__(self) : pass ## converts linked list to a bool # @returns False if empty, True otherwise def __bool__(self) : pass ## Computes length of linked list # @returns the length of the linked list def __len__(self) : pass ## implements Python sequence-style equality and less-then # (on the items held and not the nodes), respectively # Ensures other is another linked list, if not assertion fail # @returns True if equal/less-than, False otherwise def __eq__(self, other) : pass def __lt__(self, other) : pass ## implements in operator # @returns True if item is in linked-list, False otherwise def __contains__(self, item) : pass ## insert_after and remove are extra credit (5 points) # All or nothing, linked-list must function perfectly to be elligible # No partial credit ## constant time insertion of the data item (any element) after node # @pre (precondition) node is in the linked list (self) def insert_after(self, node, item) : pass ## constant time removal of node from the linked list (self) # @pre (precondition) node is in the linked list (self) def remove(self, node) : pass

Explanation / Answer

Code:

class node:
def __init__(self, item, prev = None, next = None):
self.item=item
self.prevNode=prev
self.nextNode=next
  
def __str__(self) :
return str(self.item)
      
def __repr__(self) :
return repr(self.item)
  
def getItem(self):
return self.item

def getNextNode(self):
return self.nextNode
  
def getPrevNode(self):
return self.prevNode

def setNextNode(self,val):
self.nextNode = val

def setPrevNode(self,val):
self.nextNode = val
    ## linked_list
    # Implements a doubly-linked list ADT
    # @invariant (len == 0 and head == None and self.tail == None)
    # or (len != 0 and head != None and tail != None and head.prev == None and tail.next == None)
    # You do not have to call your data members head/tail, but should be descriptive names
class linked_list :
      
    ## constructor - iterable is an iterable object that initializes
    # the linked_list in the order iterable is traversed
def __init__(self, iterable = []) :
self.len=len(iterable)
self.head=None
self.tail=None
for i in range(self.len):
newNode=node(iterable[i],self.tail,None)
if self.head==None:
self.head=newNode
self.tail=newNode
else:
self.tail.setNextNode(newNode)
self.tail=newNode
  
      
    ## constant time access to first/last node, respectively
    # @returns the first/last node, respectively
def front(self) :
return self.head
def back(self) :
return self.tail
      
    ## constant time insertion of a data item (any element)
    # as the first/last (respectively) element
def push_front(self, item) :
newNode=node(item,None,self.head)
self.head=newNode
  
def push_back(self, item) :
newNode=node(item,self.tail,None)
self.tail=newNode
      
    ## constant time removal of the first/last (respectively) node/item
    # @returns the item (not the node)
def pop_front(self) :
if self.head==None:
print ('Cant pop! List is already empty')
else:
self.head=self.head.getNextNode()
def pop_back(self) :
if self.head==None:
print ('Cant pop! List is already Empty')
else:
self.tail=self.tail.getPrevNode()
self.tail.setNextNode(None)
    ## Turns list into a string representation.
    # Strings prints identical to how
    # it would if it were a Python list
    # @returns the string representation
def __str__(self) :
strr="["
tmp=self.head
while tmp!=self.tail:
strr=strr+str(self.head.getItem())+", "
tmp=tmp.getNextNode()
strr=strr+str(tmp.getItem())+"]"
return strr
  
    ## Provides an iterator over an instance of the linked list
    # iterator is a separate class (either external or inner)
    # that iterates from first to last.
    # __next__ returns a node
    # @returns an iterator
def __iter__(self) :
listt=[]
tmp=self.head
while tmp!=None:
listt.append(tmp.getItem())
tmp=tmp.getNextNode()
my_iter = iter(listt)
return my_iter
    ## Generator function to iterate over the linked list from last to first.
    # Generates nodes.
def __reversed__(self) :
tmp=self.tail
print ('[')
while tmp!=self.head:
print (str(tmp.getItem())+", ")
tmp=tmp.getPrevNode()
print (str(tmp.getItem())+"]")
      
    ## converts linked list to a bool
    # @returns False if empty, True otherwise
def __bool__(self) :
if self.head==None:
return False
else:
return True
      
    ## Computes length of linked list
    # @returns the length of the linked list
def __len__(self) :
return len
    ## implements Python sequence-style equality and less-then
    # (on the items held and not the nodes), respectively
    # Ensures other is another linked list, if not assertion fail
    # @returns True if equal/less-than, False otherwise
def __eq__(self, other) :
try:
if isinstance(other,self.__class__):
len1=self.__len__()
len2=other.__len__()
assert len1==len2
tmp1=self.head
tmp2=other.head
while(tmp1!=None):
assert tmp1.getItem() ==tmp2.getItem()
tmp1=tmp1.getNextNode()
tmp2=tmp2.getNextNode()
return true
except AssertionError:
return False
  
def __lt__(self, other) :
try:
if isinstance(other,self.__class__):
len1=self.__len__()
len2=other.__len__()
assert len1<len2
tmp1=self.head
tmp2=other.head
while(tmp1!=None):
assert tmp1.getItem() <tmp2.getItem()
tmp1=tmp1.getNextNode()
tmp2=tmp2.getNextNode()
return true
except AssertionError:
return False
  
    ## implements in operator
    # @returns True if item is in linked-list, False otherwise
def __contains__(self, item) :
tmp=self.head
while tmp!=None:
if item==tmp.getItem():
return True
tmp=tmp.getNextNode()
return False
  
    ## insert_after and remove are extra credit (5 points)
    # All or nothing, linked-list must function perfectly to be elligible
    # No partial credit
      
    ## constant time insertion of the data item (any element) after node
    # @pre (precondition) node is in the linked list (self)
def insert_after(self, node, item) :
if(self.__contains__(node.getItem())==False):
print (str(node.getItem()),' doesnt exist')
return
node.getNextNode().setPrevNode(newNode)
newNode=node(item,node,node.getNextNode())
node.setNextNode(newNode)
if self.tail==node:
self.tail=newNode
      
    ## constant time removal of node from the linked list (self)
    # @pre (precondition) node is in the linked list (self)
def remove(self, node) :
if(self.__contains__(node.getItem())==False):
print (str(node.getItem()),' doesnt exist')
return
if self.head==node and self.tail==node:
self.head=None
self.tail=None
return
elif self.head==node:
self.head==self.head.getNextNode()
self.head.setPrevNode(None)
elif self.tail==node:
self.tail=self.tail.getPrevNode()
self.tail.setNextNode(None)
else:
tmp=self.head
while tmp.getItem()!=node.getItem():
tmp=tmp.getNextNode()
tmp.getPrevNode().setNextNode(tmp.getNextNode())
tmp.getNextNode().setPrevNode(tmp.getPrevNode())
  
l=[1,2,3,5,6]
listt1=linked_list(l)
print (listt1.__len__())
listt1.__str__()
listt1.__reversed__()

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.