LinkedListExercise.java
LinkedListExercise.java — 7.5 KB
Dateiinhalt
package ss19.ue3; import java.util.Random; /** A class that implements a linked list. */ public class LinkedListExercise { /** * An exception that is thrown if a position is not valid e.g., negative numbers or a number * greater than the size of the list. */ protected static class InvalidPositionException extends Exception { private static final long serialVersionUID = 6706174452236696114L; public InvalidPositionException() {} } /** A nested class to represent a Linked List. */ protected static class LinkedList { // Head node private Node head; // Size of the list private int n; /** A nested class to represent a node of the linked list. */ private static class Node { /** Creates a new node with value 'newValue', and 'next' set to null. */ public Node(int newValue) { this.value = newValue; this.next = null; } // Value stored in the current node. public int value; // Pointer to the next node. public Node next; } /** Creates a new empty linked list, sets the size to zero and the head to null. */ public LinkedList() { this.n = 0; this.head = null; } /** Returns the size of the linked list. */ public int size() { return this.n; } /** * Returns the node at a given position. * * @param pos: the position of the node in the list * @return the node stored at the given position */ protected Node nodeAt(int pos) { // FIXME Your code here return null; } /** * Returns the value of the node at a given position. * * @param pos: the position of the node in the list * @return the value stored in the node at the given position * @throws InvalidPositionException if such node does not exist. */ public int elementAt(int pos) throws InvalidPositionException { // FIXME Your code here return -1; } /** * Deletes the node at a given position. * * @param pos: the position of the node to be removed * @throws InvalidPositionException if such node does not exist. */ public void delete(int pos) throws InvalidPositionException { // FIXME Your code here } /** * Inserts a new node in the list at a given position. * * @param pos: the position of the node to be inserted * @param val: the value stored in the new node * @throws InvalidPositionException if the position is greater than n. */ public void insert(int val, int pos) throws InvalidPositionException { // FIXME Your code here. } /** Reverses the content of the list (e.g., 0->1->2 becomes 2->1->0). */ public void reverse() { // FIXME Your code here. } /** * Given a integer value 'val', rearranges the nodes in the list such that: every node with * value >= 'val' comes before the nodes with value < 'val'. * * @param val: the value used to split the list. */ public void split(int val) { // FIXME Your code here. } } private static LinkedList createLinkedList(int size, int maxVal) { Random rd = new Random(); rd.setSeed(42); LinkedList ll = new LinkedList(); for (int i = 0; i < size; i++) { values[i] = rd.nextInt(maxVal); try { ll.insert(values[i], ll.size()); } catch (InvalidPositionException e) { System.err.println("Error: insert threw an exception!"); } } return ll; } private static int[] values; /** Test cases. */ public static void main(String[] args) { int size = 100; int maxVal = 500; boolean success = true; values = new int[size]; LinkedList ll1 = createLinkedList(size, maxVal); // Checks that insert() works for (int i = 0; i < 100; i++) { try { if (values[i] != ll1.elementAt(i)) { System.err.println( "insert failed. value must be " + values[i] + " but is " + ll1.elementAt(i)); success = false; break; } } catch (InvalidPositionException e) { System.err.println("Error: valueAt(" + i + ") threw an exception!"); success = false; break; } } if (success) { System.out.println("insert() was successfull"); } else { System.out.println("insert() was not successfull"); } // Checks reverse() ll1.reverse(); success = true; for (int i = 0; i < 100; i++) { try { if (values[size - i - 1] != ll1.elementAt(i)) { System.err.println("reverse failed. value must be " + values[size - i - 1]); success = false; break; } } catch (InvalidPositionException e) { System.err.println("Error: valueAt(" + i + ") threw an exception!"); success = false; break; } } if (success) { System.out.println("reverse() was successfull"); } else { System.out.println("reverse() was not successfull"); } // Checks delete() LinkedList ll2 = createLinkedList(size, maxVal); // Create a new LinkedList success = true; int[] delAt = {0, (size - 1) / 2, size - 3}; for (int del : delAt) { try { ll2.delete(del); } catch (InvalidPositionException e) { System.err.println("Delete threw an exception!"); success = false; break; } // Deleting element also from array for (int i = del; i < size - 1; ++i) { values[i] = values[i + 1]; } } if (ll2.size() != size - delAt.length) { System.err.println("delete failed. number of values must be " + (size - delAt.length)); success = false; } if (success) { int lpos = 0; int vpos = 0; while (lpos < ll2.size()) { try { if (values[vpos] != ll2.elementAt(lpos)) { System.err.println( "elementAt failed. value must be " + values[vpos] + " but is " + ll2.elementAt(lpos)); success = false; break; } } catch (InvalidPositionException e) { System.err.println("Error: valueAt(" + lpos + ") threw an exception!"); success = false; break; } ++vpos; ++lpos; } } if (success) { System.out.println("delete() was successfull"); } else { System.out.println("delete() was not successfull"); } // Check split() LinkedList ll3 = createLinkedList(size, maxVal); // Create a new LinkedList success = true; int split = 250; ll3.split(split); boolean first = true; for (int i = 0; i < ll3.size(); i++) { if (first) { try { if (ll3.elementAt(i) < split) { first = false; } } catch (InvalidPositionException e) { System.err.println("Error: valueAt(" + i + ") threw an exception!"); success = false; break; } } else { try { if (ll3.elementAt(i) >= split) { System.err.println("split failed. value must be smaller than " + split); success = false; break; } } catch (InvalidPositionException e) { System.err.println("Error: valueAt(" + i + ") threw an exception!"); success = false; break; } } } if (success) { System.out.println("split() was successfull"); } else { System.out.println("split() was not successfull"); } } }