Need help with my JAVA homework! Thank you! You’ll be given some standard linked
ID: 3846846 • Letter: N
Question
Need help with my JAVA homework! Thank you!
You’ll be given some standard linked list code (singly-linked, no dummy head node,) and be asked to trace
through the code to determine the output. Suggestion for this part: Draw pictures. public class LinkedList
{
{
private class Node private Node next;
private Comparable data; public Node(Comparable data)
{ }
{
this(data, null);
public Node(Comparable data, Node next)
this.data = data; this.next = next;
}
public Comparable getData(){ return this.data; } public Node getNext(){return this.next;}
}//end nested Node class private Node head;
private int numItems; public boolean isEmpty()
{ }
{ }
return this.head == null; public void deleteAll()
this.head = null; this.numItems = 0;
} }
1. Describe completely what the mystery method above does.
2. Write four of the following methods for the LinkedList class: add, delete, sort, toString, addOrdered.
4. Shown below is the iterative version of binary search. Write the recursive version! Note that the initial call to the recursive version would look like this:
int index = binarySearch(array, target, 0, array.length-1);
public static int binarySearch(Comparable [] array, Comparable target) {
int first=0, last=array.length-1, mid;
while (first <= last) {
mid = (first + last) / 2;
if (array[mid].compareTo(target) < 0)
first = mid + 1;
else if (array[mid].compareTo(target) > 0)
last = mid - 1;
else
return mid;
}//end while
return -1;//not found }//end binarySearch
Explanation / Answer
1)
This mystery method wiill print all successive nodes of given node. It will print current node and will go forward to print
next node data using statement 'curr = curr.getNext()'
-----------------------------------------------------------------------------------------------------------------
2)
// this will include add, oaddOrdered and sort methods...
public void add(Comparable data)
{
// make the new node to insert into list
Node newNode = new Node(data);
// check ilst is empty or not
if (head == null)
{
System.out.println("add "+data +" to front");
head = newNode;
return;
}
// check it can be placed in front
else if (data.compareTo(head.data) < 0)
{
System.out.println("added "+data +" before "+head.data);
newNode.next = head;
head = newNode;
}
//otherwise find appripriate position
else
{
Node after = head.next;
Node before = head;
while (after != null)
{
if (data.compareTo(after.data) < 0)
break;
before = after;
after = after.next;
}
// insert <-> before and after
newNode.next = before.next;
before.next = newNode;
System.out.println("add "+data +"after"+before.data);
}
}
----------------------------------------------------------------------------------------------------------------------------------------------
public boolean delete(int data) {
Node _tempNode = head;
Node _previousNode = null;
boolean deletedANode = false;
while (_tempNode != null) {
if (_tempNode.data == data) {
if (_tempNode == head) {
head = head.next;
} else {
_previousNode.next = _tempNode.next;
}
// fixed indenting
deletedANode = true;
} else {
// go to next node..
_previousNode = _tempNode;
}
_tempNode = _tempNode.next;
}
return deletedANode;
}
--------------------------------------------------------------------------------------------------------------------------------------------------
public String toString()
{
StringBuilder _str = new StringBuilder(100);
Node nn = head;
// loop each node
while (nn != null)
{
_str.append(nn.item.toString());
nn = nn.next;
}
// return final string
return _str.toString();
}
----------------------------------------------------------------------------------------------------------------------------------------------
4)
public static int recursiveBinarySearch(Comparable [] array, int start, int end, Comparable target) {
if (start < end) {
int mid = start + (end - start) / 2;
if (target < array[mid]) {
return recursiveBinarySearch(array, start, mid, target);
} else if (target > array[mid]) {
return recursiveBinarySearch(array, mid+1, end , target);
} else {
return mid;
}
}
return -(start + 1);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.