Hi I would like to implement a doubly chained list with 4 operations namely:
I was able to implement them, but I have a mistake when I do unit tests on the different methods. my shift method that is supposed to delete the item at the end of the list returns an error to me when running unit tests Here is my source code. here the class of Doubly linked list
class Node(object):
def __init__(self, value, succeeding=None, previous=None):
# reference to next node into the doubly linked list
self.next = succeeding
# reference to previous node into the doubly linked list
self.prev = previous
# adding an value element to the node
self.data = value
class LinkedList(object):
def __init__(self):
self.head = None
self.tail = None
def push(self, new_data):
""" insert value at back in the list
Args:
new_data (object): the value to insert at the back in the list
Returns:
None
"""
# creating a new node with the desired value
new_node = Node(new_data)
# newly created node's next pointer will refer to the old head
new_node.next = self.head
# Checks whether list is empty or not
if self.head != None:
# old head's previous pointer will refer to newly created node
self.head.prev = new_node
# new node becomes the new head
self.head = new_node
new_node.prev = None
else: # If the list is empty, make new node both head and tail
self.head = new_node
self.tail = new_node
new_node.prev = None # There's only one element so both pointers refer to null
def unshift(self, new_data):
""" Insert value at front in the list
Args:
new_data (object): the value to insert at the front in the list
Returns:
None
"""
new_node = Node(new_data)
new_node.prev = self.tail
# checks whether the list is empty, if so make both head and tail as new node
if self.tail == None:
self.head = new_node
self.tail = new_node
# the first element's previous pointer has to refer to null
new_node.next = None
# If list is not empty, change pointers accordingly
else:
self.tail.next = new_node
new_node.next = None
self.tail = new_node # Make new node the new tail
def pop(self):
""" Remove value at back in the list
Args:
None
Returns:
data (object): The value removed at the back in the list
"""
if self.head == None:
print("List is empty")
else:
temp = self.head
# temp.next.prev = None # remove previous pointer referring to old head
self.head = temp.next # make second element the new head
temp.next = None # remove next pointer referring to new head
return temp.data
def shift(self):
""" Remove value at front in the list
Args:
None
Returns:
data (object): The value removed at the front in the list
"""
if self.tail == None:
print("List is empty")
else:
temp = self.tail
# temp.prev.next = None # removes next pointer referring to old tail
self.tail = temp.prev # make second to last element the new tail
temp.prev = None # remove previous pointer referring to new tail
return temp.data
def taille(self, dll):
""" Get the length of the doubly linked list
Args:
dll (Object): the doubly linked list
Returns:
length (list): The length of the DLL
"""
n = 0
lst = dll
while lst is not None:
n = n + 1
lst = lst.next
return n
def __len__(self):
return self.taille(self.head)
# This function prints contents of linked list
# starting from the given node
def printList(self, node):
print("\nTraversal in forward direction")
while node:
print(" {}".format(node.data), end="")
last = node
node = node.next
# Start with empty list
if __name__ == "__main__":
llist = LinkedList()
# Insert 6. So the list becomes 6->None
llist.unshift(6)
# Insert 7 at the beginning.
# So linked list becomes 7->6->None
llist.push(7)
# Insert 1 at the beginning.
# So linked list becomes 1->7->6->None
llist.push(1)
# Insert 4 at the end.
# So linked list becomes 1->7->6->4->None
llist.unshift(4)
print("Created DLL is: ")
llist.printList(llist.head)
print('\n', len(llist))
print('shift value return ',llist.shift())
print('pop value return ',llist.pop())
print("\n List after pop/shift element: ")
llist.printList(llist.head)
# print('\n', len(llist))
here is the test case
import unittest
from linked_list import LinkedList
class LinkedListTest(unittest.TestCase):
def test_push_pop(self):
lst = LinkedList()
lst.push(10)
lst.push(20)
self.assertEqual(lst.pop(), 20)
self.assertEqual(lst.pop(), 10)
def test_push_shift(self):
lst = LinkedList()
lst.push(10)
lst.push(20)
self.assertEqual(lst.shift(), 10)
self.assertEqual(lst.shift(), 20)
def test_unshift_shift(self):
lst = LinkedList()
lst.unshift(10)
lst.unshift(20)
self.assertEqual(lst.shift(), 20)
self.assertEqual(lst.shift(), 10)
def test_unshift_pop(self):
lst = LinkedList()
lst.unshift(10)
lst.unshift(20)
self.assertEqual(lst.pop(), 10)
self.assertEqual(lst.pop(), 20)
def test_all(self):
lst = LinkedList()
lst.push(10)
lst.push(20)
self.assertEqual(lst.pop(), 20)
lst.push(30)
self.assertEqual(lst.shift(), 10)
lst.unshift(40)
lst.push(50)
self.assertEqual(lst.shift(), 40)
self.assertEqual(lst.pop(), 50)
self.assertEqual(lst.shift(), 30)
def test_length(self):
lst = LinkedList()
lst.push(10)
lst.push(20)
self.assertEqual(len(lst), 2)
lst.shift()
self.assertEqual(len(lst), 1)
lst.pop()
self.assertEqual(len(lst), 0)
def test_iterator(self):
lst = LinkedList()
lst.push(10)
lst.push(20)
iterator = iter(lst)
self.assertEqual(next(iterator), 10)
self.assertEqual(next(iterator), 20)
def supprime(self):
self.supprimeCellule(self.head, 1)
def supprimeCellule(self, L, n):
""" Supprime la cellule après la nième cellule dans la liste L"""
if n > self.taille(L)-1:
raise IndexError("Indice invalide")
for i in range(n-1):
L = L.next
L.next = L.next.next
if __name__ == '__main__':
unittest.main()
I have this error:
.EF....
======================================================================
ERROR: test_iterator (__main__.LinkedListTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\guera\OneDrive\Documents\Python Scripts\preludd-recrutement-overlap\linked-list\linked_list_test.py", line 62, in test_iterator
iterator = iter(lst)
TypeError: 'LinkedList' object is not iterable
======================================================================
FAIL: test_length (__main__.LinkedListTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\guera\OneDrive\Documents\Python Scripts\preludd-recrutement-overlap\linked-list\linked_list_test.py", line 54, in test_length
self.assertEqual(len(lst), 1)
AssertionError: 2 != 1
----------------------------------------------------------------------
Ran 7 tests in 0.002s
FAILED (failures=1, errors=1)
Both your shift and pop method lack logic for:
head and tail attributesSo, for pop you have to add this in the else block
if self.head:
self.head.prev = None
else:
self.tail = None
...and similarly, this for shift:
if self.tail:
self.tail.next = None
else:
self.head = None
As a side note: I would have interpreted the functioning of your methods to be opposite: the comment for pop says *"Remove value at back in the list". To me, the back of the list is where tail points to, and the front of the list is where head points to. But your interpretation works for you, it is fine. It just will differ when performing an iteration over the list.