ZuoTi.Pro
Question

On Java:

Problems Problem 1. (Deque) Hints: my Use a doubly-linked list Node to implement the API — each node in the list stores a genProblems void addFirst(Item item) my Add the given item to the front of the deque w Increment n by one void addLast (Item iteProblems Item removeLast() ms Remove and return the item at the back of the deque m Decrement n by one Iterator<Item> iterato

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Code For Above Problem:

Node Class Code:


public class Node<Item> {
        Item data;
        Node<Item> next;
        Node<Item> prev;

        public Node(Item data) {
                this.data = data;
                this.next = null;
                this.prev = null;
        }
}

LinkedDeque Class Code:

import java.util.Iterator;

public class LinkedDeque<Item> {
        // Instance variables
        Node<Item> first;// reference to the front of deque
        Node<Item> last;// reference to the back of the deque
        int n;// size of the deque

        /*
         * Constructor Initializes the instance variables to appropriate values
         */
        public LinkedDeque() {
                this.first = null;
                this.last = null;
                this.n = 0;
        }

        /*
         * Return whether Deque is empty or not
         */
        public boolean isEmpty() {
                return (n == 0);
        }

        /*
         * Returns Size of Deque
         */
        public int size() {
                return n;
        }

        /*
         * Add the given item to the front of the deque Increment n by one
         */
        public void addFirst(Item item) {
                Node<Item> newNode = new Node<Item>(item);
                if (isEmpty()) {
                        first = last = newNode;
                } else {
                        first.prev = newNode;
                        newNode.next = first;
                        first = newNode;
                }
                n++;
        }

        /*
         * Add the given item to the back of the deque Increment n by one
         */
        public void addLast(Item item) {
                Node<Item> newNode = new Node<Item>(item);
                if (isEmpty()) {
                        first = last = newNode;
                } else {
                        newNode.prev = last;
                        last.next = newNode;
                        last = newNode;
                }
                n++;
        }

        // Return the item at front of deque
        public Item peekFirst() {
                if (isEmpty()) {
                        throw new RuntimeException("Deque is empty");
                } else {
                        return first.data;
                }
        }

        // Remove and Return the item at front of deque
        public Item removeFirst() {
                if (isEmpty()) {
                        throw new RuntimeException("Deque is empty");
                }

                Node<Item> temp = first;
                if (first.next == null) {
                        last = null;
                } else {
                        first.next.prev = null;
                }
                first = first.next;
                n--;
                return temp.data;
        }

        // Return the item at the back of the deque
        public Item peekLast() {
                if (isEmpty()) {
                        throw new RuntimeException("Deque is empty");
                } else {
                        return last.data;
                }
        }

        // Remove and Return the item at the back of the deque
        public Item removeLast() {
                if (isEmpty()) {
                        throw new RuntimeException("Deque is empty");
                } else {
                        Node<Item> temp = last;
                        if (last.prev == null) {
                                first = null;
                        } else {
                                last.prev.next = null;
                        }
                        last = last.prev;
                        n--;
                        return temp.data;
                }
        }

        /*
         * Return an Object of type DequeIterator
         */
        public Iterator<Item> iterator() {
                return new DequeIterator();
        }

        class DequeIterator implements Iterator<Item> {

                // Instance variable
                // Reference to the current Node in the iterator
                Node<Item> current;

                /*
                 * initializes the instance variable appropiately
                 */
                public DequeIterator() {
                        this.current = first;
                }

                /*
                 * Return whether the iterator has more items to iterate or not
                 */
                public boolean hasNext() {
                        return (current != null);
                }

                /*
                 * Return the item in the current Node and advance current to the next node
                 */
                public Item next() {

                        Item data = current.data;
                        current = current.next;
                        return data;
                }
        }
}

Main Class Code:(Driver)/(Optional)

import java.util.Iterator;

public class Main {

        public static void main(String[] args) {

                // create new Object Of LinkedDeque
                LinkedDeque<String> q = new LinkedDeque<String>();
                // Check deque is empty or not
                System.out.println("Is Empty: " + q.isEmpty());
                // get the size of deque
                System.out.println("Size: " + q.size());
                // add values to front of deque
                q.addFirst("Three");
                q.addFirst("Two");
                q.addFirst("one");
                // add values to back of deque
                q.addLast("Four");
                q.addLast("Five");
                q.addLast("Six");

                // iterator to iterate all values in deque
                System.out.println("\nItems Of Deque are: ");
                Iterator<String> iter = q.iterator();
                while (iter.hasNext()) {
                        System.out.println(iter.next());
                }

                // get the fist item of deque
                System.out.println("\nFirst item is: " + q.peekFirst());
                // get the last value of deque
                System.out.println("Last item is: " + q.peekLast());
                // remove the first value of deque
                System.out.println("Removed item from first of deque is: " + q.removeFirst());
                // remove the last value of deque
                System.out.println("Removed item from last of deque is: " + q.removeLast());

                // iterator to iterate all values in deque
                System.out.println("\nItems Of Deque are: ");
                iter = q.iterator();
                while (iter.hasNext()) {
                        System.out.println(iter.next());
                }

                System.out.println("Size: " + q.size());
                System.out.println("Is Empty: " + q.isEmpty());
        }

}

Output Of Code:

Is Empty: true
Size: 0

Items Of Deque are: 
one
Two
Three
Four
Five
Six

First item is: one
Last item is: Six
Removed item from first of deque is: one
Removed item from last of deque is: Six

Items Of Deque are: 
Two
Three
Four
Five
Size: 4
Is Empty: false

Images Of Code:

Node Class Code:

public class Node<Item> { Item data; Node<Item> next; Node<Item> prev; public Node (Item data) { this.data = data; this.next

LinkedDeque Class Code:

4 6 11 */ 1 import java.util.Iterator; 2 3 public class LinkedDeque<Item> { // Instance variables 5 Node<Item> first;// refer

* Add the given item to the back of the deque Increment n by one */ public void addLast(Item item) { Node<Item> newNode = new

// Return the item at the back of the deque public Item peeklast() { if (isEmpty()) { throw new RuntimeException(Deque is em

120 1210 122 123 class DequeIterator implements Iterator<Item> { // Instance variable // Reference to the current Node in the

Main Class Code:(Driver)/(Optional)

6 7 8 1 import java.util. Iterator; 2 3 public class Main { 4 50 public static void main(String[] args) { // create new Objec

Output Of Code:

Is Empty: true Size: 0 Items Of Deque are: one TWO Three Four Five Six First item is: one Last item is: Six Removed item from

0 0
Add a comment
Know the answer?
Add Answer to:
On Java: Problems Problem 1. (Deque) Hints: my Use a doubly-linked list Node to implement the...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Given a singly-linked list interface and linked list node class, implement the singly-linked list which has...

    Given a singly-linked list interface and linked list node class, implement the singly-linked list which has the following methods in Java: 1. Implement 3 add() methods. One will add to the front (must be O(1)), one will add to the back (must be O(1)), and one will add anywhere in the list according to given index (must be O(1) for index 0 and O(n) for all other indices). They are: void addAtIndex(int index, T data), void addToFront(T data), void addToBack(T...

  • Using a doubly linked list as the underlying data structure, implement a list ADT that implements...

    Using a doubly linked list as the underlying data structure, implement a list ADT that implements the ListInterface.java found in the ProgProjTwo Eclipse project starting point for this assignment. In addition to the forward iterator defined by resetIterator( ) and getNextItem( ) in ListInterface.java, implement a backwards iterator by providing resetBackIterator( ) and getPreviousItem( ) methods. As noted in the syllabus addendum, you are encouraged to develop a find( ) helper method that can support various list ADT operations. A...

  • In Java The following Java implementation of a class Node is given: private class Node<Object> {...

    In Java The following Java implementation of a class Node is given: private class Node<Object> { Node() { this(null, null); } Node(Object d) { this(d, null); } Node(Object d, Node n) { data = d; next = n; } Object data; Node next; } Assume that a singly linked list is implemented with a header node, but no tail node, and that it maintains only a reference to the header node. Using the class Node described above, write a MySingleLinkedList...

  • Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements...

    Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...

  • Doubly Linked List Java Help Details: First, read the DoublyLinkedList.java code and try to under...

    Doubly Linked List Java Help Details: First, read the DoublyLinkedList.java code and try to understand what each field stores and what each method is doing. Modify and complete the class as described below •The field size was defined in the class but was never maintained. Set the current default value and modify it whenever it is needed in the existing methods and other methods you implement as it is needed. It should always include the number of Nodes inside the...

  • In Java please, These are instance methods which modify the linked list ,* accessed through the...

    In Java please, These are instance methods which modify the linked list ,* accessed through the instance variable: first * Note that this list keeps track of the number of elements in the instance varible N * It is important that N accurately reflect the length of the list. * You may not add any fields to the node or list classes. * You may not add any methods to the node class. static class Node ; } public Node...

  • Instructions Part 1 - Implementation of a Doubly Linked List Attached you will find the code for ...

    Instructions Part 1 - Implementation of a Doubly Linked List Attached you will find the code for an implementation of a Singly Linked List. There are 3 files: Driver.java -- testing the List functions in a main() method. LinkNode.java -- Class definition for a Node, which is the underlying entity that stores the items for the linked list. SinglyLinkedList.java -- Class definition for the Singly Linked List. All the heavy lifting happens here. Task 1 - Review & Testing: Create...

  • C++ assignment about doubly linked list

    You are required to write the following functions using this class: class Doubly_linked_list // Use a class Doubly_linked_list to represent an object {     public:     // constructor initialize the nextPtr     Doubly_linked_list()     {         prevPtr = 0; // point to null at the beginning         nextPtr = 0; // point to null at the beginning     }     // get a number     int GetNum()     {         return number;     }     // set a number     void SetNum(int num)     {         number = num;     }     // get the prev pointer     Doubly_linked_list ...

  • (The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and...

    (The SortedLinkedList class template) Complete the SortedLinkedList class template which is a doubly linked list and is implemented with a header node and a tail node. // SortedLinkedList.h // SortedLinkedList.h // A collection of data are stored in the list by ascending order #ifndef SORTEDLIST_H #define SORTEDLIST_H using namespace std; template <typename T> class SortedList { private: // The basic single linked list node type. // Nested inside of SortedList. struct NodeType { T data; NodeType* next; NodeType* prev; NodeType(const...

  • // Java Queue LinkedList Assignment // A queue is implemented using a singly linked list. //...

    // Java Queue LinkedList Assignment // A queue is implemented using a singly linked list. // the variable: back "points" at the first node in the linked list // new elements ( enqueued) are added at the back // the variable: front "points" at the last node in the linked list. // elements are removed (dequeued) from the front // // Several queue instance methods are provided for you; do not change these // Other instance methods are left for...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
Active Questions
ADVERTISEMENT