Doubly Linked Circular Lists

This practical assignment focuses on implementing a doubly linked circular list data structure in Python 3. The implementation must include a `Node` class with `_prev`, `_data`, and `_next` fields, and a `List` class with `_length` and `_dummy` fields. The `List` class must support various operations, including insertion (at the beginning, end, and a specific index), deletion (from the beginning, end, and a specific index), getting and setting items at a specific index, finding the list's length, and iteration. All operations should be reasonably efficient, with `deleteLast` and `insertItemAtTheEnd` having O(1) time complexity. The assignment includes a comprehensive set of unit tests to verify the correctness of the implementation. The provided code includes both the implementation and the unit tests, demonstrating a complete solution to the problem.

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)