addLast und addFirst bei Listen

[FunkyPhil94]

Hallo zusammen,

sitze an einer Frage/einem Problem fest.

Es soll eine Klasse "SchlangeMitEVL" erstellt werden, die im Prinzip eine Schlange mit einer einfach verketteten Liste ist.

Beim JUnit test, kommen allerdings Fehler auf, die ich nicht verstehe, bzw. warum diese entstehen..

SchlangeMitEVL hat folgende 3 Methoden, die mir etwas Sorgen bereiten:

    @Override
    public void insert(T value) throws IllegalStateException {
        evl.addLast(value);
    }

    @Override
    public T remove() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("Schlange ist leer");
        }
        T removed = evl.removeFirst();
        if (removed == null) {
            throw new NoSuchElementException("Element konnte nicht entfernt werden");
        }
        return removed;
    }

    @Override
    public T front() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("Schlange ist leer");
        }
        return evl.getFirst();
    }

bei Insert wird das addLast von EVL aufgerufen, damit der Wert "von hinten" in die Liste geschoben wird. Wie bei einer Warteschlange.

Hier der wichtige Code von EVL:

    public T removeFirst(){
        if(null != first) {
            T r = first.data;
            first = first.next;
            size--;
            return r;
            }
        return null;
    }
    
    public T getFirst()throws NoSuchElementException{
        if(first == null) {
            throw new NoSuchElementException("Get First: Liste ist leer");
            }
        return first.data;
    }
    
    public void addLast(T o){
        ListenEl e = new ListenEl(o);
        if (first == null) {
            first = e;
        } else {
            ListenEl current = first;
            while (current.next != null) {
                current = current.next;
            }
            current.next = e;
        }
        size ++;
    }

Im dazugehörigen JUnit test sind nun folgende Fehler:

  public void testInsertAndremove() {
    SchlangeMitEVL<Integer> schlange = new SchlangeMitEVL<>();
    schlange.insert(1);
    schlange.insert(2);
    assertEquals(1, (int) schlange.remove());
    assertEquals(2, (int) schlange.remove());
    assertTrue(schlange.isEmpty());
  }
 
    public void testFront() {
      SchlangeMitEVL<String> schlange = new SchlangeMitEVL<>();
      assertTrue(schlange.isEmpty());
      schlange.insert("A");
      schlange.insert("B");
      assertEquals("A", schlange.front());
      assertEquals("B", schlange.front());
  }

Bei testInsertAndRemove ist der Fehler im 1. assertEquals "NoSuchElementException:Element konnte nicht entfernt werden".
Aber warum? removeFirst von EVL sollte doch dann die 1 removen oder?

Bei testFront ist der Fehler ebenfalls im 1. assertEquals "NoSuchElementException: Get First: Liste ist leer".
Die Liste sollte doch in etwa so aussehen <A,B> bzw.


Bedeutet das, wenn man einer Liste ein Element von hinten anfügt, dass das "erste" Element den Wert "null" hat?

 

[KonradN]

Also so auf den ersten Blick sieht der Code soweit ok aus .. wie ist isEmpty implementiert? Bei so Fragen bitte immer den ganzen Code posten!

 

[FunkyPhil94]

Alles klar, einmal den kompletten Code:

import java.util.NoSuchElementException;

class EVL <T>{
    
        ListenEl first = null;
        int size = 0;    //Laenge
        
        class ListenEl{
            T data;        //Inhalt
            ListenEl next;
            
            ListenEl(T o) {
                data = o;
                next = null;
            }
        }
    
    public void addFirst(T o) {
        ListenEl e = new ListenEl(o);
            if(first == null) {
                first = e;
            } else {
                e.next = first;
                first = e;
            }
        size++;
    }
    
    public T removeFirst(){
        if(null != first) {
            T r = first.data;
            first = first.next;
            size--;
            return r;
            }
        return null;
    }

    
    ////////////////////////////////
    
    public T getFirst()throws NoSuchElementException{
        if(first == null) {
            throw new NoSuchElementException("Get First: Liste ist leer");
            }
        return first.data;
        }
    
    public T getLast()throws NoSuchElementException{
        if(first == null) {
            throw new NoSuchElementException("Get Last: Liste ist leer");
            }
        ListenEl e = first;
        while (e.next != null) {
            e = e.next;
        }
        return e.data;
    }
    
    public void addLast(T o){
        ListenEl e = new ListenEl(o);
        if (first == null) {
            first = e;
        } else {
            ListenEl current = first;
            while (current.next != null) {
                current = current.next;
            }
            current.next = e;
        }
        size ++;
    }
    
    public T removeLast()throws NoSuchElementException{
        if (first == null) {
            throw new NoSuchElementException("Remove Last: Liste ist leer");
        }
        if(first != null && first.next == null) {
            T r = first.data;
            first = null;
            size--;
            return r;
            }
        ListenEl current = first;
        while (current.next.next != null) {
            current = current.next;
        }
        T r = current.next.data;
        current.next = null;
        size --;
        return r;
    }
    
    public boolean contains(T o){
        while (first != null) {
            if (first.data.equals(o)) {
                return true;
            }
            first = first.next;
        }
        return false;
    }
    
    
    public int size(){
        int s = 0;
        if(first == null) { 
            return s;
        }
        while (first != null) {
            s++;
            first = first.next;
        }
        return s;
        
    }
    
    public String toString(){
        String s = "";
        if(first == null) {
            return "Leer";
        }
        while (first != null) {
            s += first.data + "-";
            first = first.next;
            }
        s = s.substring(0,s.length()-1);
        return "(" + s + ")";
    }
    
    
}

import java.util.NoSuchElementException;

public class SchlangeMitEVL<T> implements Schlange<T> {
    private EVL<T> evl;

    public SchlangeMitEVL() {
        evl = new EVL<>();
    }

    @Override
    public boolean isEmpty() {
        return evl.size() == 0;
    }


    @Override
    public int size() {
        return evl.size();
    }

    @Override
    public int capacity() {
        return Integer.MAX_VALUE;
    }

    @Override
    public void insert(T value) throws IllegalStateException {
        evl.addLast(value);
    }

    @Override
    public T remove() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("Schlange ist leer");
        }
        T removed = evl.removeFirst();
        if (removed == null) {
            throw new NoSuchElementException("Element konnte nicht entfernt werden");
        }
        return removed;
    }

    @Override
    public T front() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("Schlange ist leer");
        }
        return evl.getFirst();
    }
}

import static org.junit.Assert.*;
import org.junit.Test;
import java.util.NoSuchElementException;

public class SchlangeMitEVLTest2 {
 
    
    
    
  @Test
  public void testIsEmpty() {
    SchlangeMitEVL<String> schlange = new SchlangeMitEVL<>();
    assertTrue(schlange.isEmpty());
    schlange.insert("A");
    assertFalse(schlange.isEmpty());
  }
 
  @Test
  public void testInsertAndremove() {
    SchlangeMitEVL<Integer> schlange = new SchlangeMitEVL<>();
    schlange.insert(1);
    schlange.insert(2);
    assertEquals(1, (int) schlange.remove());
    assertEquals(2, (int) schlange.remove());
    assertTrue(schlange.isEmpty());
  }
 
 @Test
  public void testFront() {
      SchlangeMitEVL<String> schlange = new SchlangeMitEVL<>();
      assertTrue(schlange.isEmpty());
      schlange.insert("A");
      schlange.insert("B");
      assertEquals("A", schlange.front());
      assertEquals("B", schlange.front());
  }

 
  @Test(expected = NoSuchElementException.class)
  public void testremoveWithEmptyQueue() {
    SchlangeMitEVL<Double> schlange = new SchlangeMitEVL<>();
    schlange.remove();
  }
 
  @Test(expected = NoSuchElementException.class)
  public void testFrontWithEmptyQueue() {
    SchlangeMitEVL<Object> schlange = new SchlangeMitEVL<>();
    schlange.front();
  }
 
  @Test
  public void testSize() {
    SchlangeMitEVL<Integer> schlange = new SchlangeMitEVL<>();
    assertEquals(0, schlange.size());
    schlange.insert(1);
    schlange.insert(2);
    assertEquals(2, schlange.size());
    assertEquals(0, schlange.size());
  }
 
  @Test
  public void testCapacity() {
    SchlangeMitEVL<String> schlange = new SchlangeMitEVL<>();
    assertEquals(Integer.MAX_VALUE, schlange.capacity());
  }
 
}

 

[KonradN]

Ach je ... so manche Fehler sind wirklich nett

toString soll lediglich einen String aufbauen ... und nichts verändern:

    public String toString(){
        String s = "";
        if(first == null) {
            return "Leer";
        }
        while (first != null) {
            s += first.data + "-";
            first = first.next;
        }
        s = s.substring(0,s.length()-1);
        return "(" + s + ")";
    }

Wird in der Methode irgend etwas verändert?

Ebenso die Methode size: Verändert die etwas?

    public int size(){
        int s = 0;
        if(first == null) {
            return s;
        }
        while (first != null) {
            s++;
            first = first.next;
        }
        return s;
    }

Wenn Du es nicht sofort siehst: Schau Dir einmal an, wie Du in removeLast vorgehst!

contains hat den Fehler ansonsten auch noch ...

Und ganz am Rand: Du pflegst ja die Variable size - Wenn Du das machst (mit size++ und size--), dann brauchst Du natürlich in size() nichts mehr berechnen....

 

[KonradN]

Ach ja - die Unit Tests laufen noch nicht, wenn Du das angepasst hast:

• in testFront kommt ein Fehler - da musst Du einmal überlegen, was denn front() macht. Und zwei mal hintereinander front aufrufen: was gibt das zurück.
• in testSize: Da kommt ein Fehler: Du prüfst die size - und dann soll beim zweiten Aufruf eine andere size sein?

 

[FunkyPhil94]

Also deine Antwort und Hilfe machen Sinn. Eine "Kopie" der Liste zu erstellen klingt nicht dumm.
Ich hoffe darauf wolltest du hinaus

Zu dem "witzigen" 2. , anderen Wert bei testSize: Das war zum Testen gedacht, da mir dort immer 0 ausgegeben wurde.

Habe die Codes nun korrigiert und es funktioniert (ListenEl current = first).
Wie auch schon in removeLast gemacht.

Aber liegt es wirklich daran?
Denn wenn ich ähnliches mit Arrays bzw. Arrays mache, passieren solche Fehler (eigentlich) nicht.

Aber nochmals Danke bis hierher

 

[KonradN]

Von den Begriffen her: Du machst keine Kopie der Liste aber Du nutzt eine lokale Variable um auf das aktuelle Element zu verweisen beim Durchgehen.

Aber liegt es wirklich daran?

Ja, daran lag es. Beim Aufruf von isEmpty wurde size aufgerufen. Da kam dann noch z.B. 2 korrekt raus, aber first war danach null.
Beim Versuch, dann auf das erste Element zuzugreifen, gab es das natürlich nicht mehr.

Wenn das bei der Speicherung in Arrays nicht passierte, dann war schlicht kein solcher Fehler in dem Code.