1 answer

LinkedList.java /** * @author someone * * Implements a double-linked list with four errors */ public...

Question:

Description For this assignment, you will be both debugging and testing a linked list. This will be similar to the queue test

LinkedList.java

/**
* @author someone
*
* Implements a double-linked list with four errors
*/

public class LinkedList<E>
{
// The first and last nodes in the list
private Node<E> head, tail;
// Number of items stored in the list
private int size;

// Create an empty linked list
public LinkedList()
{
// Create empty head and tail nodes to mark boundaries of list
head = new Node<E>(null);
tail = new Node<E>(null, null, head);
head.setNext(tail);
size = 0;
}

// Return whether there are any items in the list
public boolean isEmpty()
{
return size == 0;
}

// Return the number of items in the list
public int size()
{
return size;
}

// Empties the list
public void clear()
{
head.setNext(tail);
tail.setPrev(head);
size = 0;
}

// Adds a new item to the end of the list
public void add(E item)
{
// Create a new node between tail and the node before tail
Node<E> node = new Node<E>(item, tail, tail.getPrev());
tail.getPrev().setNext(node);
tail.setPrev(node);
// Update the size
size++;
}

// Return the item at the given index
public E get(int index)
{
// Return null if the index is out of bounds
if (index < 0 || index >= size)
{
return null;
}

Node<E> node = head.getNext();

// Traverse the list until we reach the given index
for (int i = 0; i < index; i++)
{
node = node.getNext();
}

// Return the item at the given index
return node.getItem();
}

// Removes an item from the list and returns whether an item was removed
public boolean remove(E item)
{
Node<E> node = head.getNext();

// Traverse the list until we reach the end or find item
for (int i = 0; i < size; i++)
{
// Remove the item when we find it
if (node.getItem().equals(item))
{
// Remove any references to the removed node
node.setNext(null);
node.setPrev(null);

// Update the size
size--;

return true;
}

// Move to the next node
node = node.getNext();
}

return false;
}

// Returns the index of item, or -1 if it's not in the list
public int indexOf(E item)
{
Node<E> node = head.getNext();

// Traverse the list looking for our item
for (int i = 0; i < size; i++)
{
if (node.getItem().equals(item)) return i;
}

return -1;
}

// Add a node to the list at the given index
public boolean insert(int index, E item)
{
// Return false if the index is out of bounds, but allow insertions at the end
// of the list (index == size)
if (index < 0 || index > size)
{
return false;
}

Node<E> newNode = new Node<E>(item);

// Find the node before index i
Node<E> node = head;
for (int i = 0; i < size; i++)
{
node = node.getNext();
}

// Insert after the node we just found
newNode.setNext(node.getNext());
newNode.setPrev(node);
node.getNext().setPrev(newNode);
node.setNext(newNode);

// Update the size
size++;

return true;
}

// Reverse the order of the list
public void reverse()
{
// If there are fewer than 2 items, we don't need to do anything
if (size >= 2)
{
// Two node pointers, will move through the list and swap items
Node<E> front = head.getNext(), back = tail.getPrev();

// Go halfway through the list from each end, swapping items in each pair of nodes
for (int i = 0; i < size / 2; i++)
{
// Swap items in front/back nodes
// ERROR: temp = back.getItem(), will swap incorrectly and overwrite list
E temp = back.getItem();
front.setItem(back.getItem());
back.setItem(temp);
  
// Move front/back pointers
front = front.getNext();
back = back.getPrev();
}
}
}
}

Node.java

/**
* @author Zach
*
* Simple node class with a next and previous pointer
*/

public class Node<T>
{
   // The item stored in the node
   // This cannot be modified once set
   private T item;
   // The nodes linked before and after this node
   private Node<T> next, prev;

   // Create a node connected to no other nodes
   public Node(T item)
   {
       this(item, null, null);
   }

   // Create a node with the give next and prev nodes
   public Node(T item, Node<T> next, Node<T> prev)
   {
       this.item = item;
       this.next = next;
       this.prev = prev;
   }

public T getItem()
{
return item;
}

   public Node<T> getNext()
   {
       return next;
   }

   public Node<T> getPrev()
   {
       return prev;
   }

public void setItem(T item)
{
this.item = item;
}

   public void setNext(Node<T> next)
   {
       this.next = next;
   }

   public void setPrev(Node<T> prev)
   {
       this.prev = prev;
   }
}

TestLinkedList.java (Starter Code)

/**
* @author
*/

public class TestLinkedList
{
public static void main(String[] args)
{
System.out.println("Test IndexOf: " + (testIndexOf() ? "pass" : "fail"));
System.out.println("Test Insert: " + (testInsert() ? "pass" : "fail"));
System.out.println("Test Remove: " + (testRemove() ? "pass" : "fail"));
System.out.println("Test Reverse: " + (testReverse() ? "pass" : "fail"));
}

public static boolean testIndexOf()
{
return false;
}

public static boolean testInsert()
{
return false;
}

public static boolean testRemove()
{
return false;
}

public static boolean testReverse()
{
return false;
}
}

Description For this assignment, you will be both debugging and testing a linked list. This will be similar to the queue testing assignment, but with the additional step of identifying and fixing the bugs. The starter code includes three classes: TestLinked List, LinkedList, and Node. Node is a generic data type that stores a single value and can be connected to two other Nodes, it is more or less identical to the Link example in section 10.03. The Linked List is similar to the example from chapter 10, but this implementation is a doubly linked list. It still uses the header/trailer node model described in 10.01, but has a different set of methods. Below is a brief summary of these methods: isEmpty (): returns whether the list is empty size(): returns the number of items in the list clear()removes all items from the list add(): adds a new item to the end of the list get): returns the item at the given index remove(): removes an item from the list indexof (): returns the index of an item, or -I if it's not in the list insert): adds an item to the list at the given index reverse(): reverses the order of the entire list LinkedList.java contains four errors, one in each of the following methods: removel], indexOfl), insert(), and reversel). Each bug is relatively small, and only involves one or two lines of code. Once you have fixed a bug, you can write the test to detect that bug. The TestLinked List class contains a test method for each bug, as well as a main method that runs all four tests. This part will be similar to the previous testing lab. Keep in mind the following when writing your tests Each test should return true if the method passes (the bug has been fixed] and false if the method contains the bug. A test should not crash the program. If your test detects the bug by triggering an exception, the exception should be caught by the test. You can assume that the isEmptyll, size(], clear(), addl), and get) methods dont contain bugs. Use them when writing your tests and avoid the other methods (except for the one you're testing) Grading Mimir will grade your program by running two tests for each of the bugs in the starter code. These tests will check that you have 1. Fixed the bug (5 points) 2 Written a test that detects the bug (5 points) Mimir checks your tests by running it with the starter code (which should fail and return false), your code (which should pass and return true] and another version of the list with the bugs removed (which should also pass). Mimir will show the results of testing each program.

Answers

class LinkedList<E>
{

private Node<E> head, tail;

private int size;

public LinkedList() {
head = new Node<E>(null);
tail = new Node<E>(null, null, head);
head.setNext(tail);
size = 0;
}

public boolean isEmpty()
{
return size == 0;
}

public int size()
{
return size;
}

public void clear()
{
head.setNext(tail);
tail.setPrev(head);
size = 0;
}

public void add(E item)
{
Node<E> node = new Node<E>(item, tail, tail.getPrev());
tail.getPrev().setNext(node);
tail.setPrev(node);
size++;
}

public E get(int index)
{
if (index < 0 || index >= size)
{
return null;
}

Node<E> node = head.getNext();

for (int i = 0; i < index; i++)
{
node = node.getNext();
}
return node.getItem();
}

public boolean remove(E item)
{
Node<E> node = head.getNext();

for (int i = 0; i < size; i++)
{
if (node.getItem().equals(item))
{
//Added line
node.getPrev().setNext(node.getNext());
//Added line
node.getNext().setPrev(node.getPrev());
node.setNext(null);
node.setPrev(null);

size--;

return true;
}

node = node.getNext();
}

return false;
}

public int indexOf(E item)
{
Node<E> node = head.getNext();

for (int i = 0; i < size; i++)
{
if (node.getItem().equals(item)) return i;
//Added line
node = node.getNext();
}

return -1;
}

public boolean insert(int index, E item)
{
if (index < 0 || index > size)
{
return false;
}

Node<E> newNode = new Node<E>(item);
Node<E> node = head;
//Changed line
for (int i = 0; i < index; i++)
{
node = node.getNext();
}

newNode.setNext(node.getNext());
newNode.setPrev(node);
node.getNext().setPrev(newNode);
node.setNext(newNode);

size++;

return true;
}

public void reverse()
{
if (size >= 2)
{
Node<E> front = head.getNext(), back = tail.getPrev();

for (int i = 0; i < size / 2; i++)
{
//Changed line
E temp = front.getItem();
front.setItem(back.getItem());
back.setItem(temp);

front = front.getNext();
back = back.getPrev();
}
}
}
}

class Node<T>
{
private T item;
private Node<T> next, prev;

public Node(T item)
{
this(item, null, null);
}

public Node(T item, Node<T> next, Node<T> prev)
{
this.item = item;
this.next = next;
this.prev = prev;
}

public T getItem()
{
return item;
}

public Node<T> getNext()
{
return next;
}

public Node<T> getPrev()
{
return prev;
}

public void setItem(T item)
{
this.item = item;
}

public void setNext(Node<T> next)
{
this.next = next;
}

public void setPrev(Node<T> prev)
{
this.prev = prev;
}
}


public class TestLinkedList
{
public static void main(String[] args)
{
LinkedList<Integer> list = new LinkedList();
list.add(2);
System.out.println("Test IndexOf: " + (testIndexOf(list, 2) ? "pass" : "fail"));
System.out.println("Test Insert: " + (testInsert(list) ? "pass" : "fail"));
System.out.println("Test Remove: " + (testRemove(list) ? "pass" : "fail"));
System.out.println("Test Reverse: " + (testReverse(list) ? "pass" : "fail"));
}

public static boolean testIndexOf(LinkedList<Integer> list, int n)
{
return list.indexOf(n) == 0;
}

public static boolean testInsert(LinkedList<Integer> list)
{
return list.insert(1, 2);
}

public static boolean testRemove(LinkedList<Integer> list)
{
return list.remove(2);
}

public static boolean testReverse(LinkedList<Integer> list)
{
list.add(1);
list.reverse();
return list.indexOf(1) == 0;
}
}

$java -Xmx128M -Xms16M Test LinkedList Test Index0f: pass Test Insert: pass Test Remove: pass

Test Reverse: pass$java -Xmx128M -Xms16M Test LinkedList Test Index0f: pass Test Insert: pass Test Remove: pass Test Reverse: pass

.

Similar Solved Questions

1 answer
Hazelnut Corp. manufactures lawn ornaments. It currently has two product lines, the basic and the luxury....
Hazelnut Corp. manufactures lawn ornaments. It currently has two product lines, the basic and the luxury. Hazelnut has a total of $137,061 in overhead. The company has identified the following information about its overhead activity cost pools and the two product lines: Cost Quantity/Amount Quantity...
1 answer
On April 1, Gimit Publishing Company received 533,480 from Santa Fe, Inc. for 36-month subscriptions to...
On April 1, Gimit Publishing Company received 533,480 from Santa Fe, Inc. for 36-month subscriptions to several different magazines. The company credited Uneaned Fees for the amount received and the Subscriptions started immediately. Assuming adjustments are only made at year-end, what is the adjust...
1 answer
Kindly, give me 3 companies that were involved in 2008 financial crisis. Faced a financial crisis...
Kindly, give me 3 companies that were involved in 2008 financial crisis. Faced a financial crisis in 2008...
7 answers
- Computers - English - Foreign Languages - Health - Home Economics - Math - Music - Physical Education - Science - Social Studies GRADE LEVELS - Preschool - Kindergarten - Elementary School - 1st Grade - 2nd Grade - 3rd Grade - 4th
- Computers - English - Foreign Languages - Health - Home Economics - Math - Music - Physical Education - Science - Social Studies GRADE LEVELS - Preschool - Kindergarten - Elementary School - 1st Grade - 2nd Grade - 3rd Grade - 4th Grade - 5th Grade - 6th Grade - 7th Grade - 8th Grade - High Scho...
1 answer
Please show all of your work and please make sure your handwriting is clear and easy...
Please show all of your work and please make sure your handwriting is clear and easy to read. Thank you! elasticity of substitution 10. Compared to isoquant Qı, production for isoquant Q2 has the and the elasticity of labor demand. a. lower; lower b. higher; higher c. higher; lower d. lower; hi...
1 answer
IN C++; A. Develop a class for a list, "" Develop the appropriate methods to insert...
IN C++; A. Develop a class for a list, "" Develop the appropriate methods to insert and remove data." Describe the behavior of a list and what class you would use to extend to develop a list class". B. Explain the difference between an array based and a linked based implementation. W...
1 answer
Suppose the world real interest rate is r* = 3%, the gdp growth rates in the...
Suppose the world real interest rate is r* = 3%, the gdp growth rates in the US and the foreign country are 6%, US monetary growth is μUS = 10%, and foreign monetary growth is μFC = 50%. Find inflation rates in both countries, πUS and πFC, nominal interest rates in both countries, iUS an...
1 answer
1. List 2 reasons why Clinical Practice Guidelines (CPGs) are important, in your own words, briefly,...
1. List 2 reasons why Clinical Practice Guidelines (CPGs) are important, in your own words, briefly, describe how each can help with improving the quality of care. 2. Explain the importance of con dentiality, integrity and availability as it pertains to health information privacy and security...
1 answer
Explain how an atom could emit no x-ray when an outer shell electron falls into a...
explain how an atom could emit no x-ray when an outer shell electron falls into a hole in the k shell...
1 answer
1) a) (8 points) Find L{-2e3tt + e3t). b) (8 points) Find L{e3t42}. c) (4 points)...
1) a) (8 points) Find L{-2e3tt + e3t). b) (8 points) Find L{e3t42}. c) (4 points) Can you use part a) and part b) to find l{e}"(t – 1)2}? Explain....
1 answer
Reece is comparing retirement plans with prospective employers. ABC, Inc, offlering a salary of $25,800, will...
Reece is comparing retirement plans with prospective employers. ABC, Inc, offlering a salary of $25,800, will match 75 percent of his contributions up to 10 percent of his salary, his $24,500 salary If Reece assumes that he will contribute the maximum amount allowed and keep these first-year much wo...
1 answer
24. Circle one word inside each set of parentheses in the following statement: (Solutions, colloids, suspensions)...
24. Circle one word inside each set of parentheses in the following statement: (Solutions, colloids, suspensions) contain the smallest particle size and (solutions, colloids, suspensions) contain the largest particle size. Which statement about colligative properties is incorrect? A. Solutes will lo...
1 answer
Four research participants take a test of manual dexterity (high scores mean better dexterity) and anxiety test (high scores mean more anxiety)
Four research participants take a test of manual dexterity (high scores mean better dexterity) and anxiety test (high scores mean more anxiety). The scores are as follows Person Dexterity Anxiety 1 1 10 2 1 8 3 2 4 4 4 -2...
1 answer
To calculate the Ksp value in the presence of ion activity, it is necessary to measure...
To calculate the Ksp value in the presence of ion activity, it is necessary to measure the ion product at the point of saturation for multiple . The ion product nears the Ksp value at Choose... Choose... concentrations is finally used to determine the Ksp Value. due to lower ionic strer temperatures...
1 answer
Simple Regression in Class Example StudentID Exam Score 10 Hours Studied 100 25 225 7 2...
Simple Regression in Class Example StudentID Exam Score 10 Hours Studied 100 25 225 7 2 0 0 20 ol 75 30 25 85 80 90 65 75 95 100 9 001 002 003 004 005 006 007 008 009 010 N=10 5 15 -10 ol 20 -10 S 10 2 6 8 3 S - 3 1 3 0 0 400 9 60 -2 4 100 25 -S 2 -3 9 65 70 55 70 Mean=75 20 ISI ol 13 -20 400 C 0 $ ...
1 answer
Path of B B Path of A (e) Identify the following motions as translation, rotation or...
Path of B B Path of A (e) Identify the following motions as translation, rotation or general. 32 B, ов, DZ D C₂ (a) (6) Az B2 DB В. AR D + (c) (d)...
1 answer
The commitment of scarce resources to capture returns created politically is called Orent seeking cost minimizing...
The commitment of scarce resources to capture returns created politically is called Orent seeking cost minimizing logrolling profit maximizing...