Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

LinkedListExercise.java

text/x-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");
    }
  }
}