CCC121 Doubly Linked List

doubly_linked_list.py

# CCC121 Laboratory Exercise No. 1
# Due: January 8, 2023 (Sunday) at 11:55PM

# The definition of the class for doubly-linked link objects. This class
# definition should not be modified in any way.
class DLink:
    # definition of the instance initializer method
    def __init__(self, it, prevval, nextval):
        # define the fields by setting their initial values
        self.elementField = it
        self.prevField = prevval
        self.nextField = nextval

    # definition of the method that returns the value of nextField
    def next(self):
        return self.nextField

    # definition of the method that sets the value of nextField
    def setNext(self, nextval):
        self.nextField = nextval

        # return the value of nextField
        return self.nextField

    # definition of the method that returns the value of prevField
    def prev(self):
        return self.prevField

    # definition of the method that sets the value of prevField
    def setPrev(self, prevval):
        self.prevField = prevval

        # return the value of prevField
        return self.prevField

    # definition of the method that returns the value of elementField
    def element(self):
        return self.elementField

    # definition of the method that sets the value of elementField
    def setElement(self, it):
        self.elementField = it

        # return the value of elementField
        return self.elementField

# The definition of the class for doubly-linked list objects. Complete
# this implementation variant of the doubly-linked list. Use the same
# convention as described in the slides. The DLink declaration to be used
# here should not be modified in any way. All of the operations of the
# DLink class must be done in the methods of this class. Use assertions to
# ensure the correct operation of this ADT.


class DList:
    # definition of the instance initializer method
    def __init__(self):
        # define the fields by setting their initial values

        # create DLink object for the head link
        self.head = DLink(None, None, None)

        # create DLink object for the tail link
        self.tail = DLink(None, None, None)

        # fix the nextField of the head link
        self.head.setNext(self.tail)

        # fix the prevField of the tail link
        self.tail.setPrev(self.head)

        self.curr = self.head
        self.cnt = 0

    # definition of the method that returns the number of elements in the
    # list
    def length(self):
        return self.cnt

    # definition of the method that empties the list
    def clear(self):
        self.head.setNext(self.tail)
        self.tail.setPrev(self.head)
        self.curr = self.head
        self.cnt = 0
        pass

    # definition of the method that inserts a new link in the current
    # position
    def insert(self, it):
        newLink = DLink(it, self.curr, self.curr.next())
        self.curr.next().setPrev(newLink)
        self.curr.setNext(newLink)
        self.cnt += 1

    # definition of the method that inserts a new link after the end
    # link
    def append(self, it):
        newLink = DLink(it, self.tail.prev(), self.tail)
        self.tail.prev().setNext(newLink)
        self.tail.setPrev(newLink)
        self.cnt += 1

    # definition of the method that removes the link in the current
    # position
    def remove(self):
        temp = self.curr.next()
        it = temp.element()
        self.curr.setNext(temp.next())
        temp.next().setPrev(self.curr)
        self.cnt -= 1
        return it

    # definition of the method that sets the current position to the
    # beginning of the list
    def moveToStart(self):
        self.curr = self.head

    # definition of the method that sets the current position to the end
    # of the list
    def moveToEnd(self):
        self.curr = self.tail.prev()

    # definition of the method that decrements the current position
    def prev(self):
        if self.curr != self.head:
            self.curr = self.curr.prev()

    # definition of the method that increments the current position
    def next(self):
        if self.curr.next() != self.tail:
            self.curr = self.curr.next()

    # definition of the method that returns the current position
    def currPos(self):
        temp = self.head
        pos = 0
        while temp != self.curr:
            pos += 1
            temp = temp.next()
        return pos

    # definition of the method that sets the current position
    def moveToPos(self, pos):
        self.curr = self.head
        for _ in range(pos):
            self.curr = self.curr.next()

    # definition of the method that returns the value of elementField of
    # the current link
    def getValue(self):
        return self.curr.next().element()

# A helper function that displays a linked list according to the defined
# convention in the lecture slides. This function should not be modified
# in any way.


def printList(theList):
    # display the openning angle bracket
    print("<", end="")

    # save the value of the current position
    currPos = theList.currPos()

    if currPos == 0:
        # display the "|" marker if the current position is at the
        # beginning
        print("|", end="")

    if theList.length() > 0:
        # display the elements of the list in proper format

        # start iterating from the beginning of the chain of links
        theList.moveToStart()

        for i in range(0, theList.length()):
            # display the element at the current position
            print(str(theList.getValue()), end="")

            if i+1 != currPos:
                if i+1 != theList.length():
                    # display a comma
                    print(",", end="")
            else:
                # display a "|"
                print("|", end="")

            # advance to the next position
            theList.next()

    # restore the value of the current position
    theList.moveToPos(currPos)

    # display the closing angle bracket
    print(">")


# The following program statements are for testing your implementation
# of the DList class. You are free to modify these statements.
print("creating a list...")
theList = DList()

print("state of the list is: ", end="")
printList(theList)

print("the size of the list is:", theList.length())

print("inserting 1...")
theList.insert(1)

print("inserting 2...")
theList.insert(2)

print("inserting 3...")
theList.insert(3)

print("appending 4...")
theList.append(4)

print("appending 5...")
theList.append(5)

print("appending 6...")
theList.append(6)

print("state of the list is: ", end="")
printList(theList)

print("the size of the list is:", theList.length())

print("setting the current link position to 3...")
theList.moveToPos(3)

print("state of the list is: ", end="")
printList(theList)

print("removing", theList.remove(), "...")

print("state of the list is: ", end="")
printList(theList)

print("removing", theList.remove(), "...")

print("state of the list is: ", end="")
printList(theList)

print("setting the current link position to the beginning...")
theList.moveToStart()

print("state of the list is: ", end="")
printList(theList)

print("the element field of the current link is:", theList.getValue())

print("executing the next() method...")
theList.next()

print("state of the list is: ", end="")
printList(theList)

print("executing the prev() method...")
theList.prev()

print("state of the list is: ", end="")
printList(theList)

print("setting the current link position to the end...")
theList.moveToEnd()

print("state of the list is: ", end="")
printList(theList)

print("the current link position is:", theList.currPos())

print("clearing the list...")
theList.clear()

print("state of the list is: ", end="")
printList(theList)