Implement the data structure DoublyLinkedList with the following characteristics
ID: 3710563 • Letter: I
Question
Implement the data structure DoublyLinkedList with the following characteristics:
- DoublyLinkedList() creates a new doubly linked list that is empty. It needs no parameters and returns nothing. Assume the items in the list are unique
-addFirst(item) adds a new Node with value=item at the beginning of the list. It needs the item and returns nothing.
-addLast(item) adds a new Node with value=item at the end of the list. It needs the item and returns nothing.
-addBefore(pnode_value, item) adds a new Node with value=item before the Node with value=pnode_value. It needs the value of the reference Node and the item to be added, returns nothing. You can assume the reference node is in the list.
-addAfter(pnode_value, item) adds a new Node with value=item after the Node with value=pnode_value. It needs the value of the reference Node and the item to be added, returns nothing. You can assume the reference node is in the list.
Here is the code:
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
def getValue(self):
return self.value
def getNext(self):
return self.next
def setValue(self,new_value):
self.value = new_value
def setNext(self,new_next):
self.next = new_next
def getPrevious(self):
return self.prev
def setPrevious(self,new_prev):
self.prev = new_prev
def __str__(self):
return ("{}".format(self.value))
__repr__ = __str__
class DoublyLinkedList:
# Do NOT modify the constructor
def __init__(self):
self.head = None
def addFirst(self, value):
node = Node(value)
node.next = self.head
if self.head is not None:
self.head.prev = node
self.head = node
def addLast(self, value):
# write your code here
def addBefore(self, pnode_value, value):
# write your code here
def addAfter(self, pnode_value, value):
# write your code here
def printDLL(self):
temp=self.head
print(" Traversal Head to Tail")
while temp:
print(temp.getValue(), end=' ')
last = temp
temp=temp.getNext()
print(" Traversal Tail to Head")
while(last is not None):
print(last.getValue(), end=' ')
last = last.prev
def getNode(self,value):
current=self.head
found=False
while current!=None and not found:
if current.getValue()==value:
found=True
return current
else:
current=current.getNext()
return
Explanation / Answer
I have implemented the methods
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
def getValue(self):
return self.value
def getNext(self):
return self.next
def setValue(self,new_value):
self.value = new_value
def setNext(self,new_next):
self.next = new_next
def getPrevious(self):
return self.prev
def setPrevious(self,new_prev):
self.prev = new_prev
def __str__(self):
return ("{}".format(self.value))
__repr__ = __str__
class DoublyLinkedList:
# Do NOT modify the constructor
def __init__(self):
self.head = None
def addFirst(self, value):
node = Node(value)
node.next = self.head
node.prev=None
if self.head is not None:
self.head.prev = node
self.head = node
def addLast(self, value):
# write your code here
node=Node(value)
if self.head is None:
node.prev=None
node.next=None
self.head=None
else:
temp=self.head
while temp.getNext()!=None:
temp=temp.next
temp.setNext(node)
node.setPrevious(temp)
node.next=None
def addBefore(self, pnode_value, value):
node=Node(value)
temp=self.head
while temp.getValue()!=pnode_value:
temp=temp.next
x=temp.getPrevious()
if x is not None:
x.setNext(node)
node.setPrevious(x)
node.setNext(temp)
temp.setPrevious(node)
else:
node.setNext(temp)
temp.setPrevious(node)
node.prev=None
self.head=node
def addAfter(self, pnode_value, value):
node=Node(value)
temp=self.head
while temp.getValue()!=pnode_value:
temp=temp.next
x=temp.getNext()
if x is not None:
temp.setNext(node)
node.setPrevious(temp)
node.setNext(x)
x.setPrevious(node)
else:
temp.setNext(node)
node.setPrevious(temp)
node.next=None
def printDLL(self):
temp=self.head
print(" Traversal Head to Tail")
while temp:
print(temp.getValue(), end=' ')
last = temp
temp=temp.getNext()
print(" Traversal Tail to Head")
while(last is not None):
print(last.getValue(), end=' ')
last = last.prev
def getNode(self,value):
current=self.head
found=False
while current!=None and not found:
if current.getValue()==value:
found=True
return current
else:
current=current.getNext()
return