Implement Doubly Linked Circular Lists Python

Added on - 16 Sep 2019

  • 14

    pages

  • 2127

    Words

  • 97

    Views

  • 0

    Downloads

Showing pages 1 to 4 of 14 pages
Implement doubly linked circular lists Python 3Implement doubly linked circular lists with stored length and withaccess to a dummy node. Support all the operations ofmyListArray ADT as describe below. All operations should bereasonably efficient (as much as this structure allows.)Inparticular, 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 methodsneed 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 indexx[index] = item -- (set) replace the the item at thegiven index by the given item.x.insertItemAtTheFront(item) -- insert a given itemat the beginning -- at index 0, shifting existing items by oneto the right.x.insertItemAtTheEnd(item) -- add a given item atthe end.x.insertItemAtIndex(k, item) -- insert the givenitem at the given index k, shifting the items at k, k+1, ... byone to the right.x.deleteFirst() -- delete the first item -- the item atindex 0, shifting other items by one to the leftx.deleteLast() -- delete the last item.x.deleteItemAtIndex(index) -- delete the item atindex 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 alsowhen index=len(x).The List objects need to support iterations (so you need to defineiterators)
The program :#! /usr/bin/env python3class Node(object):__slots__="_data", "_prev","_next" # Technicality, improvesmemory usagedef __init__(self, prev, data, next):self._prev = dataself._data = prevself._next = nextdef __eq__(self, otherNode):return self._data == otherNode._dataclass List(object):def __init__(self, length=0, items=[]):# create the dummy node for the listself._dummy = Node(None, None, None)dataNode = self._dummynextNode = self._dummyprevNode = self._dummyself._length = 0for item in items:aNode = Node(item,item,item)
dataNode._next = aNodenextNode._prev = aNodeprevNode._data = aNodedataNode = aNodenextNode = aNodeprevNode = aNodeself._length += 1def __len__(self):return self._lengthdef __getitem__(self, index):if index < 0 or index >= self._length:raise Exception("invalid index")# move to the given index in the listnode = self._dummyfor i in range(index + 1):node = node._nextreturn node._datadef __setitem__(index, item):if index < 0 or index >= self._length:raise Exception("invalid index")# move to the given index in the listnode = self._dummyfor i in range(index + 1):node = node._nextnode._data = item
def insertAtBeginning(self, item):# add a new item to the beginning of the listself.insertItemAtIndex(0, item)def insertAtEnd(self, item):# add a new item to the end of the listself.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 nodeprev = self._dummyfor i in range(k):prev = prev._nextnext = prev._next# create a new node and insert it at the positioncurr = Node(item, prev, next)prev._next = currnext._prev = currself._length += 1def deleteFirst(self):self.deleteNodeAtIndex(0)def deleteLast(self):self.deleteNodeAtIndex(self._length - 1)def deleteNodeAtIndex(self, index):
desklib-logo
You’re reading a preview
card-image

To View Complete Document

Become a Desklib Library Member.
Subscribe to our plans

Download This Document