Uni Lübeck SS 2019 AuD Übung3 - Verkettete Liste

MyIntListElement.java

/**
 * @author werner, braun (IFIS)
 */
public class MyIntListElement {

    private int key;
    protected MyIntListElement next;

    public MyIntListElement(int key, MyIntListElement next) {
        this.key = key;
        this.next = next;
    }

    public MyIntListElement getNext() {
        return this.next;
    }

    public void setNext(MyIntListElement next) {
        this.next = next;
    }

    /**
     * @param otherElement {@link MyIntListElement}
     * @return 0 if both Element equal, -1 if this < otherElement, else 1
     */
    public int compare(MyIntListElement otherElement) {
        return (key < otherElement.key) ? -1 : ((key == otherElement.key) ? 0 : 1);
    }

    public String toString() {
        return String.format("key: %d", key);
    }

}

MyIntOrderedList.java

/**
 * @author werner, braun (IFIS)
 */
public class MyIntOrderedList {

    private MyIntListElement head = null;

    public MyIntOrderedList() {
    }

    /**
     * Inserts a key value into the ordered list while keeping
     * the ordered list ascending.
     *
     * @param key any integer value to be inserted
     */
    public void insert(int key) {
        if (head == null) {
            head = new MyIntListElement(key, null);
            return;
        }

        // create new element for key with out any next value
        MyIntListElement element = new MyIntListElement(key, null);

        // find correct position for new element within structure
        InsertPosition insertPosition = findInsertPositionFor(element);

        if (insertPosition.smallerElement == null) {
            // there was no smaller element, new element is the new head
            element.setNext(head);
            head = element;
        } else {
            // a smaller and a larger element have been found.
            // insert new element in between those.
            element.setNext(insertPosition.largerElement);
            insertPosition.smallerElement.setNext(element);
        }

    }


    public void removeKeyAtIndex(int idx) {
        if (head == null || idx < 0) {
            return;
        }

        // get element that is 1 place before the element at idx
        MyIntListElement element = head;
        for (int i = 0; i < idx - 1; i++) {
            try {
                element = element.getNext();
            } catch (NullPointerException ignored) {
                break;
            }
        }

        try {
            // if the element 1 place behind the element to remove has further
            // elements, append them to the element 1 place before the element to remove
            MyIntListElement toAppend = element.getNext().getNext();
            element.setNext(toAppend);
        } catch (Exception noElementToAppend) {
            if (element != null)
                element.setNext(null);
        }

    }

    /**
     * Finds the "insert position" for an element.
     * The position contains a {@link InsertPosition#smallerElement} and a
     * {@link InsertPosition#largerElement}, in which the element could be put
     * in between.
     *
     * @param element {@link MyIntListElement}
     * @return {@link InsertPosition}
     */
    private InsertPosition findInsertPositionFor(MyIntListElement element) {
        InsertPosition insertPosition = new InsertPosition();

        insertPosition.largerElement = head; // assume that the largest element we have is the head
        insertPosition.smallerElement = null;
        while (insertPosition.largerElement != null
                && element.compare(insertPosition.largerElement) == 1) {
            // only search further if the element is larger than largerElement

            insertPosition.smallerElement = insertPosition.largerElement;
            insertPosition.largerElement = insertPosition.largerElement.getNext();
        }

        return insertPosition;
    }

    public void print() {
        MyIntListElement current = head;

        int i = 0;
        while (current != null) {
            System.out.println(i + ": " + current);
            current = current.getNext();
            i++;
        }
    }

    class InsertPosition {
        MyIntListElement smallerElement;
        MyIntListElement largerElement;
    }

}