<JAVA coding problem> 6. (17 points total) Imagine using a doubly linked list to

Question

<JAVA coding problem> 6. (17 points total) Imagine using a doubly linked list to implement the queue ADT for values of type int. Skeleton code is provided below. Implement the enqueue and dequeue methods. Instead of using the methods of the List ADT, manipulate the nodes directly. You have access to the head and tails nodes directly. This doubly linked list uses sentinel nodes and you can assume that head and tail have already been initialized properly.

class LinkedListQueue {

private static class Node {

Node prev;

Node next;

int data;

}

Node head;

Node tail;

public enqueue(int x) { // write this};

public int dequeue() { // write this};

}

Explanation / Answer

class LinkedListQueue {

private static class Node {

public Node() {

}

Node prev;

Node next;

int data;

}

Node head;

Node tail;

public void enqueue(int x) {

Node newNode = new Node();

newNode.data = x;

newNode.next = null;

if (head == null)

head = newNode;

else {

Node trav = null;

for (trav = head; trav.next != null; trav = trav.next) {

}

trav.next = newNode;

newNode.prev = trav;

}

}

public int dequeue() {

int t=head.data;

if(head.next==null)

head=null;

else{

head.next.prev=null;

head=head.next;

}

return t;

}

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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