QuestionQuestion

Transcribed TextTranscribed Text

1) If x is a Node reference which points to a node in a linked list, what does this code fragment do to the list? Assume x and x.next are not null. Answer in one (English) sentence. if (x.next. next -- null) ( x.next null; } Suppose in some application, a linked list with the following list has been built. + + +-> 5 I 0-- 8 o-- 2 4 |null| I + + F-I-+ lo I + head Draw a picture of the list after the code below is executed. Node P head; while (p null) ( while ((p.next !- null) && (p.next.item >- p.item)) ( Node temp - p.next; p.next "p.next.next; } P p.next; } 2) Another way to implement a queue is to use a circular linked list. In a circular linked list, the last node's next reference points at the first node. Assume the list is a singly-linked list, and that we can maintain a reference to a node, in addition to the head reference which points to athe first node in the list. For which of the following representations can all basic queue operations be performed in constant time (O(1), i.e., without having to traverse the list)? Choose a. or b. below, and justify your answers. Write at least 2 sentences. a. Maintain a/another reference which points to the first node in the list. b. Maintain a/another reference which points to the last node in the list. 3) Make class Rational from 'comparable' by writing the compareTo() in this code. Use the fractional/floating-point value (with decimal digits) of what a Rational object represents to decide the order of two Rational's. Note that the source code provided for this midterm ("Rational.java" uses long instead of int as the data type for the numerator and the denominator. All necessary code by yourself. 4) For the class Bag (with extendible array, defined in "Bag.java"), add the following methods: a) public void trimToSize() -- If the data array has unused spaces (i.e., the bag is not full), allocate a new array just enough to hold the current items. If the bag is full, do nothing. b) public T removeMin() -- Removes the minimum item from the bag and returns the item. Size should be decremented as well. Note the items do implement Comparable in the code given. Also since the implementation of this Bag class stores items in an array from the beginning with no 'holes', the vacated slot is filled by the last element in the current array and the last slot should be nulled-out. If the bag is empty, the method returns null. c) public boolean isUnique() -- returns true if all items in this bag are unique, that is, there are no duplicates. Use equals() to test for equality between the items. 5) For the class LinkedList from add the following methods: a) public void insertAfter(int k, E e) inserts the item'e AFTER the node at index k (where k is O-based). For example, if the list contained [4, 8, 2, 7] and insertAfter(1, 9) is called, the method changes the list to [4, 8, 9, 2, 7]. The method also throws an IndexOutOfBoundsException if the index is out of range (k >= size()). b) public boolean findMove(E e) -- Receives a value to be searched ('e') in the list, and returns true if the value exists in the list, or false otherwise. IN ADDITION, if the value exists in the list, the list node which has the value is physically moved to the front of the list. For example, if the list contained [4, 7, 2, 8] and findMove(2) is called in this list, the method returns true and the list changes to [2, 4. 7, 8]. Note that you must accomplish this task ONLY by manipulating the Node references; NO new node should be created, nor should you delete a node and add a new node. c) public Iterator iterator(int index) -- returns an iterator starting at the specified position ('index') in the list. The specified index is O-based.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

package ;

import java.util.Iterator;

@SuppressWarnings("unchecked")
public class Bag<T extends Comparable<T>> implements Iterable<T> {
private int MAX_ITEMS = 10; // initial array size
private int size;
private T[] data;

public Bag( ) {
    data = (T []) new Object[MAX_ITEMS];
    size = 0;
}

public int size( ) {
    return size;
}

public void add(T newItem) {
    // check if it's full, then extend (array resizing)
    if (size == data.length) {
      T[ ] temp = (T [ ] ) new Object[data.length*2];
      for (int i = 0; i < size; ++i)
       temp[i] = data[i];
      // reassign data to point to temp
      data = temp;
    }
    // then do the assignment
    data[size++] = newItem; // assign newItem in the next-available slot
}

// a method in Iterable implemented
public Iterator<T> iterator() {
    return new BagIterator();
}

/***************************
* nested class BagIterator
***************************/
   class BagIterator implements Iterator<T> {
    // instance member
    private int index...
$70.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats