Codemonkeys: InsertFirst in LinkedList

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
DerMathematiker
Neuling
Neuling
Beiträge: 8
Registriert: 27. Apr 2017 14:52

Codemonkeys: InsertFirst in LinkedList

Beitrag von DerMathematiker »

Hallo,
ich habe ein Problem mit den Tests für insert(ListElement<T> el) in eine LinkedList. Bei meiner Implementierung schlagen leider 3 der 11 Tests fehl. Da die Fehlersuche in Codemonkeys extrem(!) schwierig ist, habe ich ein neues Java-Projekt auf meinem PC erstellt und die LinkedList mal selbst implementiert und auch eigene Tests geschrieben, die alle durchlaufen. Auch einige Beispielausgaben auf der Konsole haben immer dem erwarteten Ergebnis entsprochen. Daher frage ich mich, ob ich einige Testfälle noch vergessen habe, die in Codemonkeys gerade nicht durchlaufen, oder ob die Tests fehlerhaft sind.

Hier ist meine Implementierung der LinkedList:

Code: Alles auswählen

public class LinkedList<T> {

    private ListElement<T> head;
    private ListElement<T> last;
    private int size;

    public LinkedList(ListElement<T> head, ListElement<T> last, int size){
        this.head = head;
        this.last = last;
        this.size = size;

    }

    public ListElement<T> getFirst(){
        return head;
    }

    public void setFirst(ListElement<T> head){
        this.head = head;
    }

    public ListElement<T> getLast() { return last; }

    public void setLast(ListElement<T> last){
        this.last = last;
    }

    public int size(){
        return size;
    }

    public void setSize(int size){
        this.size = size;
    }

    public boolean contains(ListElement<T> el){
        ListElement<T> p = getFirst();
        while(p != null){
            if (p.equals(el)) return true;
            p = p.next();
        }
        return false;
    }

    public boolean insertFirst(ListElement<T> el){
            if (el == null || contains(el)) return false;
            boolean emptyFirst = size() == 0;
            ListElement<T> p = el;
            ListElement<T> tmp = p.next();
            p.setNext(getFirst());
            setFirst(p);
            setSize(size() + 1);
            while(p != null && tmp != null){
                if (contains(tmp)) return true;
                ListElement<T> temp = tmp.next();
                tmp.setNext(p.next());
                p.setNext(tmp);
                setSize(size() + 1);
                tmp = temp;
                p = p.next();
            }
            if (emptyFirst) setLast(p);
            return true;
    }

    public void print(){
        ListElement<T> p = getFirst();
        while (p != null){
            System.out.print(p.getID() + "|");
            p = p.next();
        }
        System.out.println();
    }
}

Die ListElements sehen folgendermaßen aus:

Code: Alles auswählen

public class ListElement<T> {
    private String ID;
    private T key;
    private ListElement<T> next;

    public ListElement(T key){
        this.key = key;
        ID = "EL-0";
    }

    public ListElement(T key, String ID, ListElement<T> next){
        this.key = key;
        this.ID = ID;
        this.next = next;
    }

    public boolean hasNext(){
        return next != null;
    }

    public ListElement<T> next(){
        return next;
    }

    public void setNext(ListElement<T> next){
        this.next = next;
    }

    public String getID(){
        return ID;
    }
}

Zum Abschluss sind hier meine Tests:

Code: Alles auswählen

public class TestInsertLinkedList {
    LinkedList<Integer> emptyList, filledList;
    ListElement<Integer> el1, el2, el3, el4, el5, el6, el7;

    @Before
    public void init(){
        emptyList = new LinkedList<Integer>(null, null, 0);
        el1 = new ListElement<Integer>(1, "el-1", null);
        el2 = new ListElement<Integer>(2, "el-2", null);
        el3 = new ListElement<Integer>(3, "el-3", null);
        el4 = new ListElement<Integer>(4, "el-4", null);
        el5 = new ListElement<Integer>(5, "el-5", null);
        el6 = new ListElement<Integer>(6, "el-6", null);
        el7 = new ListElement<Integer>(7, "el-7", null);
        el3.setNext(el4);
        el4.setNext(el5);
        el5.setNext(el6);
        el6.setNext(el7);
        filledList = new LinkedList<Integer>(el3, el7, 5);
    }

    @Test
    public void testInsertionInEmptyList(){
        assertTrue(emptyList.insertFirst(el1));
        assertEquals(el1, emptyList.getFirst());
        assertEquals(el1, emptyList.getLast());
        assertEquals(1, emptyList.size());
    }

    @Test
    public void testRepeatedInsertionInEmptyList(){
        assertTrue(emptyList.insertFirst(el1));
        for (int i = 0; i < 100; i++){
            assertFalse(emptyList.insertFirst(el1));
            assertEquals(el1, emptyList.getFirst());
            assertEquals(el1, emptyList.getLast());
            assertEquals(1, emptyList.size());
        }
    }

    @Test
    public void testInsertionOfSuccessiveElementsInEmptyList(){
        el1.setNext(el2);
        assertTrue(emptyList.insertFirst(el1));
        assertFalse(emptyList.insertFirst(el2));
        assertEquals(el1, emptyList.getFirst());
        assertEquals(el2, emptyList.getLast());
        assertEquals(2, emptyList.size());
    }

    @Test
    public void testInsertSingleElement(){
        assertTrue(filledList.insertFirst(el2));
        assertEquals(6, filledList.size());
        assertEquals(el2, filledList.getFirst());
        assertEquals(el7, filledList.getLast());
    }

    @Test
    public void testNullInsertion(){
        assertFalse(emptyList.insertFirst(null));
        assertFalse(filledList.insertFirst(null));
    }

    @Test
    public void testRepeatedInsertion(){
        assertFalse(filledList.insertFirst(el3));
        assertFalse(filledList.insertFirst(el4));
        assertFalse(filledList.insertFirst(el5));
        assertFalse(filledList.insertFirst(el6));
        assertFalse(filledList.insertFirst(el7));
    }

    @Test
    public void testRecursivelyInsertionSingleElement(){
        el1.setNext(el1);
        assertTrue(emptyList.insertFirst(el1));
        assertEquals(1, emptyList.size());
    }
}

Ich hoffe, dass sich hier einige finden, die mir helfen können, ich bin ja scheinbar auch nicht der einzige mit diesen Problemen. Vielleicht können wir die ja zusammen lösen.

P.S.: Ähnliche Probleme treten auch bei den Methoden insert und insertLast auf.

Dadung
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 7. Mai 2017 13:08

Re: Codemonkeys: InsertFirst in LinkedList

Beitrag von Dadung »

es gab schon mehrere Threads zu den gleichen Aufgaben, ich hab grad nicht geschaut, ob deine Probleme die gleichen sind, wie da, aber es gab in erster Linie Probleme mit "unendlichen" ListElements, die eingefügt werden sollten.

Ich habe in einem Thread dazu eine funktionierende Lösung gepostet, schau da mal nach.

Antworten

Zurück zu „AuD: Programmieraufgaben“