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

ID: 3563952 • Letter: U

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.

Picture of nodes in the linked list:

.........

Start with the class Deque program below and fill in code to the ADT methods where you see (pass #???? replace this line with your lines of code ). Use the class Deque program as a template to place the code for the deque code. The python keyword pass, does nothing except serve as a placeholder for code.

The following are the ADT methods that will be implemented in the the program for deque with a double linked list.

-isEmpty()

-addFront(item)

-addRear(item)

-removeFront(item)

-removeRear(item)

-size()

For Extra Credit:

Implement a pop method that takes an integer argument i and returns the ith nodes data counting from 0 from the beginning of the list if i is positive and returns the ith node counting backward from the end of the list if i is negative.

It should also remove the node from the list.

So for the list pictured:

pop(0) returns 16 -- and the the list would have [ 10, 5, 2 ] left on it
pop(2) returns 5 -- 5 was the third element from the front of the list, and the list after pop would be [ 10, 2, 16 ]
pop(5) gets an error -- there is no 5 element from the front, there is just 0 through 3
pop(-1) returns most rear element in list: 10
pop(-3) returns the third from rear: 2

# The end of the program below contains test code called def main(). Please do not change the names already defined in the test code def main().

#Start of code here:

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

    def size(self):
        pass # replace this pass line with your code
        # HINT: count nodes in deque by traversing them

# END OF ASSIGNMENT. DO NOT MODIFY ANY OF THE CODE AFTER THIS POINT
    # code after this point, is for the testing, it includes __str__ and dump()

    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 = {} # dictinary 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 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()

    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()

# now test it
main(

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. Picture of nodes in the linked list: Start with the class Deque program below and fill in code to the ADT methods where you see (pass #???? replace this line with your lines of code ). Use the class Deque program as a template to place the code for the deque code. The python keyword pass, does nothing except serve as a placeholder for code. The following are the ADT methods that will be implemented in the the program for deque with a double 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...
}
}

Navigate

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

Using Python develop a program in modular format (def Main, call Main, etc.) for

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

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

Question

Explanation / Answer

Related Questions

Navigate