Test that the node constructor creates a new node with the correct data values.
Added on 2019-09-16
14 Pages2127 Words274 Views
|
|
|
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 python3class 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._dataclass 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):
End of preview
Want to access all the pages? Upload your documents or become a member.