ArrayTitelListe.java

import java.util.Arrays;

/**
 * Diese Klasse implementiert das Interface TitelListe mit "wachsenden" Arrays.
 * 
 * @author Till Aust
 * @author Axel Schmolitzky
 * @author Petra Becker-Pechau
 * @author Alexander Pokahr
 * @author Christian Spaeh
 * @author Fredrik Winkler
 * @version WiSe 2013/14
 */
class ArrayTitelListe implements TitelListe
{
    // In diesem Array sind die Referenzen auf die enthaltenen Titel abgelegt.
    // Die Laenge des Arrays entspricht der Kapazitaet der Liste und muss daher nicht separat gespeichert werden.
    private Titel[] _titelArray;

    // Die Kardinalitaet der Liste.
    private int _anzahlTitel;

    // Die Anfangskapazitaet einer jeden neuen Liste.
    private static final int ANFANGSKAPAZITAET = 10;

    /**
     * Initialisiert eine neue <code>ArrayTitelListe</code>.
     */
    public ArrayTitelListe()
    {
        _titelArray = new Titel[ANFANGSKAPAZITAET];
        _anzahlTitel = 0;
    }
    
    public ArrayTitelListe(int kapazitaet)
    {
        if (kapazitaet < 0)
        {
            throw new IllegalArgumentException("Die Kapazität muss größer-gleich 0 sein!");
        }
        
        _titelArray = new Titel[kapazitaet];
        _anzahlTitel = 0;
    }

    /**
     * Fuege einen Titel an der Position <code>position</code> in die Titelliste
     * ein. Alle folgenden Eintraege werden um eine Position verschoben.
     * Wenn <code>position</code> gleich der Laenge der Titelliste ist, dann
     * fuege den <code>titel</code> am Ende an.
     * 
     * @param titel Der einzufuegende Titel (darf nicht null sein).
     * @param position Die Position, an welcher der Titel eingefuegt werden soll.
     */
    public void fuegeEin(Titel titel, int position)
    {
        darfNichtNullSein(titel);
        mussGueltigeEinfuegepositionSein(position);
                
        if (_anzahlTitel >= _titelArray.length)
        {
            _titelArray = Arrays.copyOf(_titelArray, _anzahlTitel+1);
        }
        
        if (_titelArray[position] != null)
        {
            System.out.println("pos: " + position);
            for (int i = _anzahlTitel; i > position; i--)
            {
                System.out.println("i: " + i);

                _titelArray[i] = _titelArray[i - 1];
            }
        }
        
        _titelArray[position] = titel;
        _anzahlTitel++;
    }

    /**
     * Pruefe, ob ein Titel in der Liste enthalten ist.
     * 
     * @param titel Der Titel, welcher in der Liste gesucht werden soll.
     * @return <code>true</code> wenn der Titel in der Liste ist,
     *         ansonsten <code>false</code>.
     */
    public boolean enthaelt(Titel titel)
    {
        darfNichtNullSein(titel);

        for (Titel T : _titelArray)
        {
            if (T == null)
            {
                return false;
            }
            
            if (T != null && T.equals(titel))
            {
                return true;
            }
        }

        return false;
    }

    /**
     * Gib den Titel an der angegebenen Position zurueck.
     * 
     * @param position Die Position des Titels, der zurueckgeben werden soll.
     * @return Der Titel an der Position <code>position</code>.
     */
    public Titel gibTitel(int position)
    {
        mussGueltigePositionSein(position);
        return _titelArray[position];
    }

    /**
     * Entferne den Titel an der angegebenen Position. Alle folgenden Eintraege
     * werden um eine Position verschoben.
     * 
     * @param position Die Position des Titels, der entfernt werden soll.
     */
    public void entferne(int position)
    {
        mussGueltigePositionSein(position);
        
        _anzahlTitel--;
        
        if (position < _anzahlTitel)
        {
            for (int i = position; i < _anzahlTitel; i++)
            {
                _titelArray[i] = _titelArray[i + 1];
            }
        }
        
        _titelArray[_anzahlTitel] = null;
    }

    /**
     * Gib die Laenge der Liste zurueck.
     * 
     * @return Anzahl der Titel in der Liste.
     */
    public int gibLaenge()
    {
        return _anzahlTitel;
    }

    /**
     * Entferne alle Titel aus der Liste.
     */
    public void leere()
    {
        _titelArray = new Titel[ANFANGSKAPAZITAET];
        _anzahlTitel = 0;
    }

    /**
     * Schreibt den Array-Inhalt auf die Konsole (als Debugging-Hilfe gedacht).
     */
    public void schreibeAufKonsole()
    {
        System.out.println(java.util.Arrays.toString(_titelArray));
    }

    /**
     * Überprüft, ob position ein gültiger Index für diese Liste ist.
     * 
     * @param position Die Position des Titels, die überprüft werden soll.
     * @return Das Ergebnis der Überprüfung
     */
    public boolean istGueltigePosition(int position)
    {
        return (position >= 0) && (position < gibLaenge());
    }

    /**
     * Wirft eine IndexOutOfBoundsException, falls es sich um eine ungueltige Position handelt.
     * 
     * @param position Die Position des Titels, die überprüft werden soll.
     */
    private void mussGueltigePositionSein(int position)
    {
        if (!istGueltigePosition(position))
        {
            throw new IndexOutOfBoundsException(position + " ist keine gueltige Position");
        }
    }
    
    /**
     * Überprüft, ob an der Stelle position in die Liste eingefügt werden kann.
     * 
     * @param position Die Position des Titels, die überprüft werden soll.
     * @return Das Ergebnis der Überprüfung
     */
    public boolean istGueltigeEinfuegeposition(int position)
    {
        return (position >= 0) && (position <= gibLaenge());
    }

    /**
     * Wirft eine IndexOutOfBoundsException, falls es sich um eine ungueltige Einfuegeposition handelt.
     * 
     * @param position Die Position des Titels, die überprüft werden soll.
     */
    private void mussGueltigeEinfuegepositionSein(int position)
    {
        if (!istGueltigeEinfuegeposition(position))
        {
            throw new IndexOutOfBoundsException(position + " ist keine gueltige Einfuegeposition");
        }
    }
    
    /**
     * Wirft eine IllegalArgumentException, falls die uebergebene Titel-Referenz null ist.
     * 
     * @param titel Der Titel der überprüft wird.
     */
    private static void darfNichtNullSein(Titel titel)
    {
        if (titel == null)
        {
            throw new IllegalArgumentException("Die Titel-Referenz darf nicht null sein.");
        }
    }
}

aufg12_4.md

Das Ergebnis:

ArrayTitelListe 100000 mal am Anfang einfuegen: 10595ms LinkedTitelListe 100000 mal am Anfang einfuegen: 7ms ArrayTitelListe 100000 mal am Ende einfuegen: 10ms LinkedTitelListe 100000 mal am Ende einfuegen: 10ms ArrayTitelListe 100000 mal an Position 0 in einer 100000 Elemente langen Liste lesen: 9ms LinkedTitelListe 100000 mal an Position 0 in einer 100000 Elemente langen Liste lesen: 9ms ArrayTitelListe 100000 mal an Position 99999 in einer 100000 Elemente langen Liste lesen: 2ms LinkedTitelListe 100000 mal an Position 99999 in einer 100000 Elemente langen Liste lesen: 2ms ArrayTitelListe 100000 mal an Position 50000 in einer 100000 Elemente langen Liste lesen: 2ms LinkedTitelListe 100000 mal an Position 50000 in einer 100000 Elemente langen Liste lesen: 9822ms

Auswertung

ArrayListen sind schnell, wenn man Elemente an einem Index entfernt vom Anfang, bzw. Ende lesen/schreiben möchte.

Beim Einfügen entfernt vom Ende sind sie langsam, da alle Elemente index > Position geschoben werden müssen.

Wenn also nur am Ende eingefügt werden muss, sind ArrayListen vorzuziehen, ist dies nicht der Fall muss abgewogen werden, ob der indizierte Zugriff auf Elemente häufig vorkommt und schnell sein muss.

Ist dies nicht der Fall, sind LinkedListen auf jeden Fall besser.