Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

There are 5 Java files below that can be copy and pasted for testing. The files are: 1) a3tester.java (main) 2) IntegerList.java 3) IntegerLinkedList.java 4)

There are 5 Java files below that can be copy and pasted for testing. The files are:

1) a3tester.java (main)

2) IntegerList.java

3) IntegerLinkedList.java

4) IntegerNode.java

5) IntegerArrayList.java

Code must only be written in IntegerLinkedList.java. 9 Methods need to be implemented so that all the tests in the tester file passes.

Your task is to implement the interface described in the file IntegerList.java using a doubly linked list in the file IntegerLinkedList.java.

The tester is written to be able to test the linked list implementation that you are required to implement in IntegerLinkedList.java

Your implementation must be a doubly-linked list that maintains both a head and a tail reference. You've also been provided with a node class (IntegerNode.java) that includes a prev and next references.

//a3tester.java//

public class a3tester { public static int testCount = 0; public static int totalTests = 36; public static boolean testArraySolution = false; public static int stressTestSize = 20000; public static void displayResults (boolean passed) { /* There is some magic going on here getting the line number * Borrowed from: * http://blog.taragana.com/index.php/archive/core-java-how-to-get-java-source-code-line-number-file-name-in-code/ * * Once we've discussed Exceptions in more detail this won't be required. */ if (passed) { System.out.println ("Passed test: " + testCount); } else { System.out.println ("Failed test: " + testCount + " at line " + Thread.currentThread().getStackTrace()[2].getLineNumber()); System.exit(1); } testCount++; } public static void testOne () { boolean passed; IntegerList l = createNewList(); System.out.println("Basic testing of size, addFront, addBack, get"); displayResults (l.size() == 0); l.addFront(10); displayResults (l.size() == 1); l.addBack(9); displayResults (l.size() == 2); l.addFront(7); displayResults (l.size() == 3); displayResults (l.get(0) == 7); displayResults (l.get(1) == 10); displayResults (l.get(2)== 9); } public static void addArray (int[] a, IntegerList l, boolean addBack) { for (int i=0;i= -10; i--) { l1.remove(i); } displayResults(l1.size() == 0); l1.addFront(9); l1.addFront(8); l1.addBack(12); displayResults((l1.get(0) == 8) && (l1.get(1) == 9) && (l1.get(2) == 12) && (l1.size() == 3)); l1.remove(9); displayResults((l1.get(0) == 8) && (l1.get(1) == 12) && l1.size() == 2); l1.addBack(13); l1.addFront(14); l1.remove(14); l1.remove(13); displayResults((l1.get(0) == 8) && (l1.get(1) == 12) && (l1.size() == 2)); l1.remove(8); l1.remove(12); displayResults(l1.size() == 0); } public static void testFour() { int[] a1 = {1,2,3}; IntegerList l1 = createNewList(); System.out.println ("Testing remove"); addArray(a1,l1,true); l1.remove(1); displayResults( (l1.size() == 2) && (l1.get(0) == 2) && (l1.get(1) == 3)); l1.addFront(1); l1.addBack(3); l1.addFront(3); l1.remove(3); displayResults( (l1.size() == 2) && (l1.get(0) == 1) && (l1.get(1) == 2)); IntegerList l2 = createNewList(); for (int i = 0;i<10;i++) { l2.addBack(10); } displayResults(l2.size() == 10); l2.remove(10); displayResults(l2.size() == 0); } public static void testFive() { IntegerList l1 = createNewList(); System.out.println("Stress test"); for (int i=0;i

//IntegerList.java interface//

 
/* * IntegerList.java * * A definition of the List ADT that can store items of type int * */ public interface IntegerList { /* * PURPOSE: * Add the element x to the front of the list. * * PRECONDITIONS: * None. * * Examples: * * If l is {1,2,3} and l.addFront(9) returns, then l is {9,1,2,3}. * If l is {} and l.addFront(3) returns, then l is {3}. */ public void addFront (int x); /* * PURPOSE: * Add the element x to the back of the list. * * PRECONDITIONS: * None. * * Examples: * * If l is {1,2,3} and l.addBack(9) returns, then l is {1,2,3,9}. * If l is {} and l.addBack(9) returns, then l is {9}. */ public void addBack (int x); /* * PURPOSE: * Add the element x at position pos in the list. * * Note: * In a list with 3 elements, the valid positions for addAt are * 0, 1, 2, 3. * * PRECONDITIONS: * pos >= 0 and pos <= l.size() * * Examples: * * If l is {} and l.addAt(9,0) returns, then l is {9}. * If l is {1} and l.addAt(9,0) returns, then l is {9,1}. * If l is {1,2} and l.addAt(9,1) returns, then l is {1,9,2} * If l is {1,2} and l.addAt(9,2) returns, then l is {1,2,9} */ public void addAt (int x, int pos); /* * PURPOSE: * Return the number of elements in the list * * PRECONDITIONS: * None. * * Examples: * If l is {7,13,22} l.size() returns 3 * If l is {} l.size() returns 0 */ public int size(); /* * PURPOSE: * Return the element at position pos in the list. * * PRECONDITIONS: * pos >= 0 and pos < l.size() * * Examples: * If l is {67,12,13} then l.get(0) returns 67 * If l is {67,12,13} then l.get(2) returns 13 * If l is {92} then the result of l.get(2) is undefined. * */ public int get (int pos); /* * PURPOSE: * Remove all elements from the list. After calling this * method on a list l, l.size() will return 0 * * PRECONDITIONS: * None. * * Examples: * If l is {67,12,13} then after l.clear(), l is {} * If l is {} then after l.clear(), l is {} * */ public void clear(); /* * PURPOSE: * Remove all instances of value from the list. * * PRECONDITIONS: * None. * * Examples: * If l is {67,12,13,12} then after l.remove(12), l is {67,13} * If l is {1,2,3} then after l.remove(2), l is {1,3} * If l is {1,2,3} then after l.remove(99), l is {1,2,3} */ public void remove (int value); /* * PURPOSE: * Remove the element at position pos in the list. * * Note: * In a list with 3 elements, the valid positions for removeAt are * 0, 1, 2. * * PRECONDITIONS: * pos >= 0 and pos < l.size() * * Examples: * * If l is {1} and l.removeAt(0) returns, then l is {}. * If l is {1,2,3} and l.removeAt(1) returns, then l is {1,3} * If l is {1,2,3} and l.removeAt(2) returns, then l is {1,2} */ public void removeAt (int pos); /* * PURPOSE: * Return a string representation of the list * * PRECONDITIONS: * None. * * Examples: * If l is {1,2,3,4} then l.toString() returns "{1,2,3,4}" * If l is {} then l.toString() returns "{}" * */ public String toString(); }

//IntegerLinkedList.java//

/* * Name: * Student Number: */ public class IntegerLinkedList implements IntegerList { public IntegerLinkedList() { } /* * PURPOSE: * Add the element x to the front of the list. * * PRECONDITIONS: * None. * * Examples: * * If l is {1,2,3} and l.addFront(9) returns, then l is {9,1,2,3}. * If l is {} and l.addFront(3) returns, then l is {3}. */ public void addFront (int x) { } /* * PURPOSE: * Add the element x to the back of the list. * * PRECONDITIONS: * None. * * Examples: * * If l is {1,2,3} and l.addBack(9) returns, then l is {1,2,3,9}. * If l is {} and l.addBack(9) returns, then l is {9}. */ public void addBack (int x) { } /* * PURPOSE: * Add the element x at position pos in the list. * * Note: * In a list with 3 elements, the valid positions for addAt are * 0, 1, 2, 3. * * PRECONDITIONS: * pos >= 0 and pos <= l.size() * * Examples: * * If l is {} and l.addAt(9,0) returns, then l is {9}. * If l is {1} and l.addAt(9,0) returns, then l is {9,1}. * If l is {1,2} and l.addAt(9,1) returns, then l is {1,9,2} * If l is {1,2} and l.addAt(9,2) returns, then l is {1,2,9} */ public void addAt (int x, int pos) { } /* * PURPOSE: * Return the number of elements in the list * * PRECONDITIONS: * None. * * Examples: * If l is {7,13,22} l.size() returns 3 * If l is {} l.size() returns 0 */ public int size() { return -1; } /* * PURPOSE: * Return the element at position pos in the list. * * PRECONDITIONS: * pos >= 0 and pos < l.size() * * Examples: * If l is {67,12,13} then l.get(0) returns 67 * If l is {67,12,13} then l.get(2) returns 13 * If l is {92} then the result of l.get(2) is undefined. * */ public int get (int pos) { return -1; } /* * PURPOSE: * Remove all elements from the list. After calling this * method on a list l, l.size() will return 0 * * PRECONDITIONS: * None. * * Examples: * If l is {67,12,13} then after l.clear(), l is {} * If l is {} then after l.clear(), l is {} * */ public void clear() { } /* * PURPOSE: * Remove all instances of value from the list. * * PRECONDITIONS: * None. * * Examples: * If l is {67,12,13,12} then after l.remove(12), l is {67,13} * If l is {1,2,3} then after l.remove(2), l is {1,3} * If l is {1,2,3} then after l.remove(99), l is {1,2,3} */ public void remove (int value) { } /* * PURPOSE: * Remove the element at position pos in the list. * * Note: * In a list with 3 elements, the valid positions for removeAt are * 0, 1, 2. * * PRECONDITIONS: * pos >= 0 and pos < l.size() * * Examples: * * If l is {1} and l.removeAt(0) returns, then l is {}. * If l is {1,2,3} and l.removeAt(1) returns, then l is {1,3} * If l is {1,2,3} and l.removeAt(2) returns, then l is {1,2} */ public void removeAt (int pos) { } /* * PURPOSE: * Return a string representation of the list * * PRECONDITIONS: * None. * * Examples: * If l is {1,2,3,4} then l.toString() returns "{1,2,3,4}" * If l is {} then l.toString() returns "{}" * */ public String toString() { return "Not implemented."; } } 

//IntegerNode.java//

/* * IntegerNode.java * * An implementation of a node class for a doubly-linked list of integers. * * This implementation does not make the instance variables private because * we prefer to write things like: * * n.next = null; * n.prev.next = p; * * Rather than: * * n.setNext(null); * n.getPrev().setNext(p); * * In this assignment, and on exams, you are free to use whichever * method you find most comfortable. * */ public class IntegerNode { IntegerNode next; IntegerNode prev; int value; public IntegerNode() { next = null; value = 0; } public IntegerNode (int val) { value = val; next = null; } public IntegerNode (int val, IntegerNode nxt) { value = val; next = nxt; } public IntegerNode getNext() { return next; } public IntegerNode getPrev() { return prev; } public int getValue() { return value; } public void setNext (IntegerNode nxt) { next = nxt; } public void setPrev (IntegerNode prv) { prev = prv; } public void setValue (int val) { value = val; } } 
/* * IntegerArrayList.java */ public class IntegerArrayList implements IntegerList { private static final int INITIAL_SIZE=1; private int[] storage; private int count; public IntegerArrayList () { storage = new int[INITIAL_SIZE]; count = 0; } private void growAndCopy() { int[] newstorage = new int[storage.length*2]; for (int i=0;i 0; i--) { storage[i] = storage[i-1]; } storage[0] = x; count++; } public void addBack (int x) { if (count == storage.length) { growAndCopy(); } storage[count++] = x; } public void addAt (int x, int pos) { if (count == storage.length) { growAndCopy(); } for (int i = count; i > pos; i--) { storage[i] = storage[i-1]; } storage[pos] = x; count++; } public int size() { return count; } public int get (int pos) { // Note that there is no verification that pos is // in range due to the preconditions. return storage[pos]; } public void clear() { count = 0; } public void remove (int value) { for (int i = 0 ; i < count ; i++) { if (storage[i] == value) { removeAt(i); i--; } } } public void removeAt (int index) { for (int i = index; i < (count - 1); i++) { storage[i] = storage[i + 1]; } count--; } public String toString() { String s = "{"; for (int i=0;i                    

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Students also viewed these Databases questions