Doubly Linked Circular Lists in Python 3: Implementation and Unit Tests

The assignment involves testing the functionality of a doubly linked list implementation in Python using the unittest framework. The tests cover the constructors, equality comparison, length calculation, indexing and assigning values, inserting new nodes at specific positions, deleting nodes, and deleting all nodes from the list.

Implement doubly linked circular lists Python 3
Implement doubly linked circular lists with stored length and with
access to a dummy node. Support all the operations of
myListArray ADT as describe below. All operations should be
reasonably efficient (as much as this structure allows.) In
particular, deleteLast and insertItemAtTheEnd should be O(1).
There should be a class Node, whose objects have fields _prev,
_data, _next.
There should be a class List, whose objects have fields
_length, _dummy.
Unit tests Notice : the class needs to called List. Other methods
need to be called as required by the unit tests:
• x.len() -- find size (the number of items)
• x[index] -- (get) return the item at the given index
• x[index] = item -- (set) replace the the item at the
given index by the given item.
• x.insertItemAtTheFront(item) -- insert a given item
at the beginning -- at index 0, shifting existing items by one
to the right.
• x.insertItemAtTheEnd(item) -- add a given item at
the end.
• x.insertItemAtIndex(k, item) -- insert the given
item at the given index k, shifting the items at k, k+1, ... by
one to the right.
• x.deleteFirst() -- delete the first item -- the item at
index 0, shifting other items by one to the left
• x.deleteLast() -- delete the last item.
• x.deleteItemAtIndex(index) -- delete the item at
index k, shifting the items at k+1, k+2, ... by one to the left.
• x.deleteAll() -- delete all the items.
Notice that x.insertItemAfterIndex(index, item) should work also
when index=len(x).
The List objects need to support iterations (so you need to define
iterators)

The program :
#! /usr/bin/env python3
class Node(object):
__slots__="_data", "_prev","_next" # Technicality, improves
memory usage
def __init__(self, prev, data, next):
self._prev = data
self._data = prev
self._next = next
def __eq__(self, otherNode):
return self._data == otherNode._data
class List(object):
def __init__(self, length=0, items=[]):
# create the dummy node for the list
self._dummy = Node(None, None, None)
dataNode = self._dummy
nextNode = self._dummy
prevNode = self._dummy
self._length = 0
for item in items:
aNode = Node(item,item,item)

dataNode._next = aNode
nextNode._prev = aNode
prevNode._data = aNode
dataNode = aNode
nextNode = aNode
prevNode = aNode
self._length += 1
def __len__(self):
return self._length
def __getitem__(self, index):
if index < 0 or index >= self._length:
raise Exception("invalid index")
# move to the given index in the list
node = self._dummy
for i in range(index + 1):
node = node._next
return node._data
def __setitem__(index, item):
if index < 0 or index >= self._length:
raise Exception("invalid index")
# move to the given index in the list
node = self._dummy
for i in range(index + 1):
node = node._next
node._data = item

def insertAtBeginning(self, item):
# add a new item to the beginning of the list
self.insertItemAtIndex(0, item)
def insertAtEnd(self, item):
# add a new item to the end of the list
self.insertItemAtIndex(self._length, item)
def insertItemAtIndex(self, k, item):
# add the item at index k.
if k < 0 or k > self._length:
raise Exception("invalid index")
# find prev node to insert the new node
prev = self._dummy
for i in range(k):
prev = prev._next
next = prev._next
# create a new node and insert it at the position
curr = Node(item, prev, next)
prev._next = curr
next._prev = curr
self._length += 1
def deleteFirst(self):
self.deleteNodeAtIndex(0)
def deleteLast(self):
self.deleteNodeAtIndex(self._length - 1)
def deleteNodeAtIndex(self, index):

# delete at the given index
if index < 0 or index >= self._length:
raise Exception("invalid index")
# move to the node to be removed
prev = self._dummy
for i in range(index):
prev = prev._next
curr = prev._next
next = curr._next
# now remove the current node
prev._next = next
next._prev = prev
self._length -= 1
def deleteAll(self):
# delete all items in the list
# equals to create an empty list
dummy = Node(None, None, None)
dummy._prev = dummy
dummy._next = dummy
self._head = dummy
self._length = 0
def __iter__(self):
return _LinkedListIterator(self)
class _LinkedListIterator(object):
def __init__(self, aLinkedList):

self._linkedList = aLinkedList
self._currentIndex = -1
def __iter__(self):
return self
def __next__(self):
if self._currentIndex == self._linkedList.__len__() - 1:
raise StopIteration
else:
self._currentIndex += 1
return self._linkedList[self._currentIndex]
def main():
array = List.create()
print("The size of an array at the start is : ", array.__len__())
for i in range(array.__len__()):
print(array.__getitem__(i))
print()
for i in range(3):
array.insertAtBeginning(i)
print()
for i in range(3):
array.insertAtEnd(i)
print()
array.insertItemAtIndex(1, 10)
array.insertItemAtIndex(4, 11)

print("The operations of myListArray ADT begin " )
print("The size is : ", array.__len__())
for i in range(array.__len__()):
print(array.__getitem__(i))
print("delete: 0 ")
array.deleteNodeAtIndex(0)
print("deleteFirst: 2 ")
array.deleteFirst()
print("deleteLast: 2 ")
array.deleteLast()
print("deleteLast: 1 ")
array.deleteLast()
print("deleteFirst: 1 ")
array.deleteFirst()
print()
print("The size is : ", array.__len__())
for i in range(array.__len__()):
print(array.__getitem__(i))
print()
print("deleteAll: ")
array.deleteAll()
print()
print("The size of the array at the end is : ", array.__len__())
for i in range(array.__len__()):
print(array.__getitem__(i))

print()
if __name__ == '__main__':
main()
—————————————————
The blow is the unit test for the doubly
#!/usr/bin/env python3
import unittest
from lists import *
#-----------------------------------------------------------------------------
class LinkedListTest(unittest.TestCase):
def testNodeConstructor(self):
n = Node(1, 2, 3) # just for testing, we use 1 and 3 instead
of references.
self.assertEqual(n._prev, 1)
self.assertEqual(n._data, 2)
self.assertEqual(n._next, 3)
def testNodeEq(self):
n = Node(1, 2, 3)
m = Node(11,2, 33)
self.assertEqual(n, m)

def testListConstructor0(self):
x = List()
self.assertEqual(x._length, 0)
dummy = x._dummy
self.assertEqual(dummy._data, None)
self.assertIs(dummy._next, dummy)
self.assertIs(dummy._prev, dummy)
def testListConstructor1(self):
y = List([1])
self.assertEqual(y._length, 1)
dummy = y._dummy
first = dummy._next
self.assertEqual(dummy._data, None)
self.assertIs(dummy._next, first)
self.assertIs(dummy._prev, first)
self.assertEqual(first._data, 1)
self.assertIs(first._next, dummy)
self.assertIs(first._prev, dummy)
def testListConstructor2(self):
y = List([1,2])
self.assertEqual(y._length, 2)
dummy = y._dummy
first = dummy._next

second = first._next
self.assertEqual(dummy._data, None)
self.assertIs(dummy._next, first)
self.assertIs(dummy._prev, second)
self.assertEqual(first._data, 1)
self.assertIs(first._next, second)
self.assertIs(first._prev, dummy)
self.assertEqual(second._data, 2)
self.assertIs(second._next, dummy)
self.assertIs(second._prev, first)
def testLen(self):
x = List()
self.assertEqual(len(x), 0)
y = List([0,1,2])
self.assertEqual(len(y), 3)
def testGetItem0(self):
x = List()
self.assertRaises(IndexError, x.__getitem__, 0)
def testGetItem3(self):
x = List([0,1,2])
self.assertRaises(IndexError, x.__getitem__, 3)
self.assertEqual(x[0], 0)

self.assertEqual(x[1], 1)
self.assertEqual(x[2], 2)
def testSetItem0(self):
x = List()
self.assertRaises(IndexError, x.__setitem__, 0, 0)
def testSetItem3(self):
x = List([0,1,2])
self.assertRaises(IndexError, x.__setitem__, 3, 0)
x[0]=10
x[1]=11
x[2]=12
self.assertEqual(x[0], 10)
self.assertEqual(x[1], 11)
self.assertEqual(x[2], 12)
def testInsertItemAtIndexA(self):
x = List([0,1])
self.assertRaises(IndexError, x.insertItemAtIndex, 3, 33)
def testInsertItemAtIndexB(self):
x = List([0,1])
x.insertItemAtIndex(1,"a")
self.assertEqual(len(x), 3)

dummy = x._dummy
first = dummy._next
second = first._next
third = second._next
self.assertEqual(first._data, 0)
self.assertEqual(second._data, "a")
self.assertEqual(third._data, 1)
self.assertIs(third._prev, second)
self.assertIs(second._prev, first)
def testInsertItemAtIndexC(self):
x = List([0,1])
x.insertItemAtIndex(2,"a")
self.assertEqual(len(x), 3)
dummy = x._dummy
first = dummy._next
second = first._next
third = second._next
self.assertEqual(first._data, 0)
self.assertEqual(second._data, 1)
self.assertEqual(third._data, "a")
self.assertIs(third._prev, second)
self.assertIs(dummy._prev, third)
self.assertIs(third._next, dummy)

def testDeleteNodeAtIndexA(self):
x = List()
self.assertRaises(IndexError, x.deleteNodeAtIndex, 0)
y = List([0,1])
self.assertRaises(IndexError, y.deleteNodeAtIndex, 2)
def testDeleteNodeAtIndexB(self):
x = List([0,1])
x.deleteNodeAtIndex(0)
self.assertEqual(len(x), 1)
dummy = x._dummy
first = x._dummy._next
self.assertEqual(first._data, 1)
self.assertIs(first._next, dummy)
self.assertIs(first._prev, dummy)
self.assertIs(dummy._prev, first)
def testDeleteAll(self):
x = List([1,2])
x.deleteAll()
self.assertEqual(len(x), 0)
dummy = x._dummy
self.assertIs(dummy._prev, dummy)
self.assertIs(dummy._next, dummy)
#-----------------------------------------------------------------------------

def main():
unittest.main()
main()
#======================================
=======================================