Using Python create an implementation of Deque with a double linked list: Each n

Question

Using Python create an implementation of Deque with a double linked list:

Each node has two links. One to the next node, and another one linked to the previous node.

Start with the program below and only fill in code to the ADT methods where you see (pass #???? replace this line with your lines of code ). It is a template to place the linked list version of deque code. The python keyword pass, does nothing except serve as a placeholder for code. The first two methods you should write the code for are addFront(d) and size() otherwise it will fail right after it tries to add Front(11).

The program contains a test code at the end called def main() to test the program after code is added. def main() also contains the dump() method to help debug the program. Please do not change the names already defined since it is set up to be tested in def main().

Implement the following ADT for Deque methods using a double linked list to hold the data for the deque.

     isEmpty()

     addFront(item)

     addRear(item)

     removeFront(item)

     removeRear(item)

     size()

Picture of nodes in the linked list:

#                      --------   --------   --------

# self.rear   -------> | data |   | data |   | data | <----------- self.front

#                      | prev |-->| prev |-->| prev |--> None

#             None <-- | next |<--| next |<--| next |

#                      --------   --------    --------

#                        node2     node1       node0

#

# ----------------------------------------------------------------------------------

#Start of code here:

class Node:

    def __init__(self,data):

        self.data = data

      self.next = None

        self.prev = None

#These are the defs' for deque

class Deque:

    def __init__(self): # construct a empty deque to start

        self.front = None

        self.rear = None

    def isEmpty(self):

        pass # ???? replace this line with your lines of code

        # HINT: you can use the fact that an empty deque will have self.front equal to None

    def addFront(self,data):

        pass # ???? replace this line with your lines of code

    def addRear(self,data):

        pass # ???? replace this line with your lines of code

    def removeFront(self):

        pass # ???? replace this line with your lines of code

    def removeRear(self):

        pass # ???? replace this line with your lines of code

    def pop(self,index):

        pass # ???? replace this line with your lines of code

        # HINT: remember to return the data that was popped, not the node

    def size(self):

        pass # ???? replace this line with your lines of code

        # HINT: count nodes in deque by traversing them

   #Code after this point, is for the testing python code above, it includes __str__ and dump() Please do not modify code after this point

    #-----------------------------------------------------------------------------------

    # these first items are added to the definition of Deque class

    def __str__(self): # print deque

        node = self.front

        s = ""

        while node is not None:

            s += str(node.data) + ", "

            node = node.next

        return "[ " + s[0:-2] + " ]"

    _nodes = {} # dictionary to map node id to n1, n2, n2 to make reading dump easier

    _index = 1   # used to keep track of first n that is not used in node names

    def dump(self): # new version to name the nodes found n1, n2, etc.

                              # instead of dumping raw id numbers

        def addr(x):

            if x is None:

                return "None"

            else:

                if id(x) in self._nodes:

                    return self._nodes[id(x)]

                else:

                    self._nodes[id(x)] = "n%d" % self._index

                    self._index += 1

                    return self._nodes[id(x)]

        print("self.front: ", addr(self.front))

        node = self.front

        while node is not None:

            print(" Node: ",addr(node))

            print("        next ",addr(node.next))

            print("        prev ",addr(node.prev))

            print("        data ",node.data)

            node = node.next

        print(" self.rear: ", addr(self.rear) )

    def integrity_check(self):

        if self.front == None:

            assert self.rear is None, "rear is not None for empty deque"

        else:

            forward = []

            node = self.front

            while node is not None:

                forward.append(node)

                node = node.next

            node = self.rear

            node = self.rear

            while node is not None:

                assert forward.pop() == node,

                    "prev for node does not match " +

                str(id(forward[len(forward) - 1])) + " <=> " + str(id(node)) +

                    "for node number " + str(len(forward))

                node = node.prev

# END of Deque Class definition

# main() does a call to Deque, and then prints the que, and then does an integrity check

def main():

    dq = Deque()

    print("new Deque(), and the size is ", dq.size()) # 0

    dq.integrity_check()

    dq.addFront(11)

    print("dq.addFront(11), dq: ", dq) # 0

    dq.integrity_check()

    assert dq.size() == 1, "size should now be 1"

    dq.addFront(22)

    print("dq.addFront(22), dq: ", dq) # 0

    dq.integrity_check()

    dq.addFront(55)

    print("dq.addFront(55), dq: ", dq) # 0

    dq.integrity_check()

    dq.removeFront()

    print("dq.removeFront(), dq: ", dq)

    dq.integrity_check()

    dq.addRear(9)

    print("dq.addRear(9), dq: ", dq)

    dq.integrity_check()

    dq.addRear(1)

    print("dq.addRear(1), dq: ", dq)

    dq.integrity_check()

    n = dq.pop(1)

    print("dq.pop(1), dq: ", dq)

    print(" returned: ",n)

    dq.integrity_check()

    n = dq.pop(-1)

    print("dq.pop(-1), dq: ", dq)

    print(" returned: ",n)

    dq.integrity_check()

    n = dq.pop(0)

    print("dq.pop(0), dq: ", dq)

    print(" returned: ",n)

    dq.integrity_check()

    n = dq.pop(-1)

    print("dq.pop(-1), dq: ", dq)

    print(" returned: ",n)

    dq.integrity_check()

main()

View comments (3)

Using Python create an implementation of Deque with a double linked list: Each node has two links. One to the next node, and another one linked to the previous node. Start with the program below and only fill in code to the ADT methods where you see (pass #???? replace this line with your lines of code ). It is a template to place the linked list version of deque code. The python keyword pass, does nothing except serve as a placeholder for code. The first two methods you should write the code for are addFront(d) and size() otherwise it will fail right after it tries to add Front(11). The program contains a test code at the end called def main() to test the program after code is added. def main() also contains the dump() method to help debug the program. Please do not change the names already defined since it is set up to be tested in def main(). Implement the following ADT for Deque methods using a double linked list to hold the data for the deque. isEmpty() addFront(item) addRear(item) removeFront(item) removeRear(item) size() Picture of nodes in the linked list:

Explanation / Answer

// implement Iterable at least, but List would be even better
public class DoublyLinkList<T> {

// private classes should be at the end of the file
private static class Node<T> {
private T data;
private Node next;
private Node prev;

public Node(T data) {
this.data = data;
}

// no need for this method
public void displayNode() {
System.out.print(data + " ");
}

@Override
public String toString() {
return data.toString();
}
}

// both should be private, nobody outside should see the node class
public Node first = null;
public Node last = null;

public void addFirst(T data) {
Node newNode = new Node(data);

if (isEmpty()) {
newNode.next = null; // no need for this line, it is null by default
newNode.prev = null; // no need for this line, it is null by default
first = newNode;
last = newNode;

} else {
first.prev = newNode;
newNode.next = first;
newNode.prev = null; // no need for this line, it is null by default
first = newNode;
}
}

// what about an addLast method?

public boolean isEmpty() {
return (first == null); // no need for parenthesis
}

// no need for this method (use toString)
public void displayList() {
Node current = first;
while (current != null) {
current.displayNode();
current = current.next;
}
System.out.println();
}

public Node first = null;
public Node last = null;

public void addFirst(T data) {
Node newNode = new Node(data);

if (isEmpty()) {
newNode.next = null; // no need for this line, it is null by default
newNode.prev = null; // no need for this line, it is null by default
first = newNode;
last = newNode;

} else {
first.prev = newNode;
newNode.next = first;
newNode.prev = null; // no need for this line, it is null by default
first = newNode;
}
}
def __str__(self): # print deque
node = self.front
s = ""
while node is not None:
s += str(node.data) + ", "
node = node.next
return "[ " + s[0:-2] + " ]"

  
def peekFront(self): # return front node data reference or None
if self.front == None: return None
return self.front.data

def peekRear(self): # return rear node data reference or None
if self.rear == None: return None
return self.rear.data

def dump(self): # new version to name the nodes found n1, n2, etc.
# instead of dumping raw id numbers

def addr(x):
if x is None:
return "None"
else:
if id(x) in self._nodes:
return self._nodes[id(x)]
else:
self._nodes[id(x)] = "n%d"%(self._index)
self._index += 1
return self._nodes[id(x)]

print (" ","-"*20," DUMP of Deque ","-"*20)
print (" self.front: " , addr(self.front))
node = self.front

while node is not None:
print (" Node: ",addr(node))
print (" data: ",node.data)
print (" next: ",addr(node.next))
print (" prev: ",addr(node.prev))
node = node.next
print( " self.rear: ", addr(self.rear) )
print( " ", "-"*50)

def integrity_check(self):
if self.front == None:
assert self.rear is None, "rear is not None for empty deque"
else:
forward = []
node = self.front
while node is not None:
forward.append(node)
node = node.next
node = self.rear

node = self.rear
while node is not None:
assert forward.pop() == node,
"prev for node does not match " +
str(id( forward[ len(forward)-1 ])) + " <=> "+ str(id(node)) +
"for node number " + str(len(forward))
node = node.prev

# END of Deque Class definition
def main():

dq = Deque()
print("new Deque(), and the size is ", dq.size()) # 0
print("dq after: ", dq)
if debug: dq.dump()
dq.integrity_check()

dq.addFront(11)
print("dq.addFront(11), dq after: ", dq) # 0
if debug: dq.dump() # dump out structure so you can see
assert dq.size() == 1, "size should now be 1"
assert dq.peekFront() == 11, "front node data should be 11"
assert dq.isEmpty() == False , "isEmpty should return False"
dq.integrity_check()

dq.addFront(22)
print("dq.addFront(22), dq after: ", dq) # 0
if debug: dq.dump() # dump out structure so you can see
assert dq.size() == 2, "size should now be 2"
assert dq.peekFront() == 22, "front node data should be 22"
assert dq.peekRear() == 11, "rear node data should be 11"
dq.integrity_check()

dq.addFront(55)
print("dq.addFront(55), dq after: ", dq) # 0
if debug: dq.dump() # dump out structure so you can see
assert dq.size() == 3, "size should now be 3"
assert dq.peekFront() == 55, "font node data should be 22"
dq.integrity_check()

data = dq.removeFront()
print("dq.removeFront(), dq after: ", dq)
if debug: dq.dump() # dump out structure so you can see
assert data == 55, "removeFront() should return 55"
assert dq.peekFront() == 22, "front node data should now be 22"
assert dq.size() == 2, "size should now be 2"
dq.integrity_check()

dq.addRear(9)
print("dq.addRear(9), dq after: ", dq)
if debug: dq.dump() # dump out structure so you can see
assert dq.size() == 3, "size should now be 3"
assert dq.peekRear() == 9, "front node data should now be 9"
dq.integrity_check()

dq.addRear(1)
print("dq.addRear(1), dq after: ", dq)
if debug: dq.dump() # dump out structure so you can see
assert dq.size() == 4, "size should now be 4"
dq.integrity_check()

dq.addRear(99)
print("dq.addRear(1), dq after: ", dq)
if debug: dq.dump() # dump out structure so you can see
assert dq.size() == 5, "size should now be 5"
dq.integrity_check()

class Node:

def __init__(self,data):
self.data = data
self.next = None
self.prev = None

class Deque:

def __init__(self): # construct a empty deque to start
self.front = None
self.rear = None

def isEmpty(self):
pass # replace this pass line with your code

def addFront(self,data):
pass # replace this pass line with your code

def addRear(self,data):
pass # replace this pass line with your code

def removeFront(self):
# removes front node and returns data reference
# return None if empty deque
pass # replace this pass line with your code

def removeRear(self):
# removes rear node and returns data reference
# return None if empty deque
pass # replace this pass line with your code

def pop(self,index):
# remove noded indexed: index indicated by index 0,1,2 count from front to rear
# index -1,-2,-3 counts from rear toward front
# return None if list is empty before pop
# NOTE: make sure to return the data that was popped, not the node
pass # replace this pass line with your code

data = dq.removeRear()
print("dq.removeRear(), dq after: ", dq)
if debug: dq.dump() # dump out structure so you can see
assert data == 99, "removeRear() should return 1"
assert dq.peekRear() == 1, "Rear node data should now be 22"
assert dq.size() == 4, "size should now be 4"
dq.integrity_check()

print("------- NOW EXTRA CREDIT TESTS: ")

n = dq.pop(1)
print("dq.pop(1), dq after: ", dq)
if debug: dq.dump() # dump out structure so you can see
print(" returned: ",n)
if debug: dq.dump() # dump out structure so you can see
assert n == 11, "pop(1) should have returned 9 "
assert dq.size() == 3, "size should now be 3"
dq.integrity_check()

n = dq.pop(-1)
print("dq.pop(-1), dq after: ", dq)
print(" returned: ",n)
if debug: dq.dump() # dump out structure so you can see
assert n == 1, "pop(-1) should have returned 1 "
assert dq.size() == 2, "size should now be 2"
dq.integrity_check()

n = dq.pop(0)
print("dq.pop(0), dq after: ", dq)
print(" returned: ",n)
if debug: dq.dump() # dump out structure so you can see
assert n == 22, "pop(0) should have returned 22 "
assert dq.size() == 1, "size should now be 1"
dq.integrity_check()

n = dq.pop(-1)
print("dq.pop(-1), dq after: ", dq)
print(" returned: ",n)
if debug: dq.dump() # dump out structure so you can see
assert n == 9, "pop(-1) should have returned 9 "
assert dq.size() == 0, "size should now be 0"
assert dq.isEmpty() == True , "isEmpty should return True"
dq.integrity_check()

main()

// it is helpful for remove to return the element removed
public void removeFirst() {
// if (isEmpty()) {
// throw new NoSuchElementException();
// }
// ...
if (!isEmpty()) {
Node temp = first;

if (first.next == null) {
first = null;
last = null;
} else {
first = first.next;
first.prev = null;
}
// should not really be printing in these methods
System.out.println(temp.toString() + " is popped from the list"); // ...was removed from...
}
}

// it is helpful for remove to return the element removed
public void removeLast() {
// if (isEmpty()) {
// throw new NoSuchElementException();
// }
// ...
Node temp = last;

if (!isEmpty()) {

if (first.next == null) {
first = null;
last = null;
} else {
last = last.prev;
last.next = null;
}
}
// should not really be printing in these methods
System.out.println(temp.toString() + " is popped from the list"); // ...was removed from...
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.