einfach verkette Liste

[itse]

Hallo,

ich möchte eine Warteschlange als einfach verkette Liste erzeugen. Soweit funktioniert auch das Erzeugen, mit den einzelnen Personen in der Warteschlange, und das jede Person weiß,wer ihr Nachfolger (next) ist.

Nun möchte ich eine Person innerhalb der Warteschlange löschen, also die Person mit ihrem Nachfolger überschreiben, dazu habe ich folgendes programmiert:

	public boolean remove(String name) {
		//Liste leer
		if (this.first == null) {
			return false;
		} 
		//Das erste Element der Liste löschen
		else if (this.first.getName() == name) {
			this.first = this.first.getNext();
			return true;
		} else 
		//Ein Element innerhalb der Liste löschen
		{
			Person search = this.first;
			//Anhand des Namens das entsprechende Element in der Liste suchen
			while (search.getName() != name) {
				search = search.getNext();
			}
			
			//Dann wird der Nachfolger, des gesuchten ermittelt
			Person naechster = search.getNext();
			
			//Wenn der Nachfolger nicht existiert
			//Dann ist das gesuchte Elemente das Letzte in der Liste
			//und soll gelöscht werden
			if(naechster == null){
				search = null;
				return true;
				
			//Wenn der Nachfolgder existiert
			//Dann soll das gesuchte Element aus der Liste gelöscht werden
			//also mit dem Nachfolger überschrieben werden
			}else if(naechster != null){
				search = naechster;
				return true;
			}else
				return false;
		}
	}

Es wird immer von der ersten Person in der Warteschlange ausgegangen.

Das Löschen der ersten Person funktioniert auch einwandfrei, diese wird mit ihrem Nachfolger überschrieben.

Jedoch kann ich keine Person innerhalb der Warteschlange und am Ende löschen.

Es funktioniert, dass die Person innerhalb der Warteschlange samt ihrem Nachfolger gesucht wird. Auch die Person am Ende wird richtig erkannt und das die nächste Person nicht existiert.

Aber die gesuchte (zu ersetzende Person) wird nicht ihrem Nachfolger bzw. mit Null überschrieben.

Was mache ich da falsch? Das Ersetzen der Person müsste doch genauso wie bei der Ersten funktionieren?

Besten Dank
Michi

 

[Michael...]

[JAVA=25] if(naechster == null){
search = null;
return true;

//Wenn der Nachfolgder existiert
//Dann soll das gesuchte Element aus der Liste gelöscht werden
//also mit dem Nachfolger überschrieben werden
}else if(naechster != null){
search = naechster;
return true;
}else
return false;
}
}
[/code]

Ich weiss ja nicht, wie Deine Klasse so aufgebaut ist, aber Du änderst hier ja nur irgendwelche lokalen Variablen, das hat ja nich unbedingt Auswirkungen auf die eigentlichen Objekte

[edit]
Im ersten Fall Zeile 26 müsstest Du eigentlich den Vorgänger von search haben und darauf sowas wie .setNext(null) aufrufen.

 

[Schumi]

Du ersetzt ja nur Deine lokale search Variable, Du solltest den Vorgänger von search nehmen und dessen Pointer neu besetzen.

 

[itse]

Ich habe zwei Klassen:

Person und Warteschlange.

Der Inhalt von Person:

public class Person {
	private String name;
	private Person next;

	public Person(String name) {
		this.name = name;
		this.next = null;
	}

	public String getName() {
		return this.name;
	}

	public Person getNext() {
		return next;
	}

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

Die Funktion setNext verwende ich bei der Warteschlange im Konstruktor, wenn ich eine neue Person erzeuge, soll die ihren Namen und den Nachfolger erhalten.

Ich weiß ja nur, wer der Nachfolger ist. Wie ermittle ich denn den Vorgänger um dann setNext verwenden zu können?

Geht das ohne eine zusätzliche Methode in der Klasse Person?

Danke.

 

[Schumi]

Den kannst Du Dir doch beim suchen nach der richtigen Person einfach vormerken. Ihn sich in den Listenelementen zu merken würde Deine Liste ja zu einer doppelt verlinkten machen.

 

[itse]

Vielen Dank für den Tipp.

So funktioniert es nun:

    public boolean remove(String name) {
        if (this.first == null) {
            return false;
        } 
        else if (this.first.getName() == name) {
            this.first = this.first.getNext();
            return true;
        } else {
        	
        	Person Vorgaenger = null;
            Person search = this.first;
            while (search.getName() != name) {
            	Vorgaenger = search;
                search = search.getNext();
            }
            if(Vorgaenger == null){
            	return false;
            }else{
                Vorgaenger.setNext(search.getNext());
                return true;
            }
        }
    }

 

[Landei]

Etwas OT: Die unveränderliche Variante einer verketteten Liste lässt sich viel einfacher implementieren. Warum muss es immer veränderlich sein?

import java.util.NoSuchElementException;

public abstract class ImmutableList<T> {
  public abstract T head();
  public abstract ImmutableList<T> tail();
  public abstract boolean isEmpty();
  public abstract int size();
  public abstract ImmutableList<T> remove(T t);
  public abstract boolean contains(T t);
  public abstract ImmutableList<T> append(ImmutableList<T> list);
  
  private static class Nil<U> extends ImmutableList<U> {
    public U head() { throw new NoSuchElementException(); }
    public ImmutableList tail() { throw new NoSuchElementException(); }
    public boolean isEmpty() { return true; }
    public int size() {  return 0; }
    public ImmutableList<U> remove(U u) { return this; }
    public boolean contains(U u) { return false; }
    public ImmutableList<U> append(ImmutableList<U> list){ return list; }
  }

  private static class Cons<U> extends ImmutableList<U> {
    final U head;
    final ImmutableList<U> tail;
    private Cons(U head, ImmutableList<U> tail) {
      this.head = head; this.tail = tail;
    }
    public U head() { return head; }
    public ImmutableList tail() { return tail; }
    public boolean isEmpty() { return false; }
    public int size() {  return 1 + tail.size(); }
    public ImmutableList<U> remove(U u) {
      return head.equals(u) ? tail : cons(head, tail.remove(u)); 
    }
    public boolean contains(U u) { return head.equals(u) || tail.contains(u); }
    public ImmutableList<U> append(ImmutableList<U> list){ 
      return cons(head, tail.append(list)); 
    }
  }
  
  public static <E> ImmutableList<E> nil() { return new Nil<E>(); }
  public static <E> ImmutableList<E> cons(E head, ImmutableList<E> tail) { 
    return new Cons<E>(head, tail);
  }
}

 

[itse]

Hallo,

nun habe ich noch ein Problem. Eine weitere Funktion, die an einer bestimmten Stelle eine Person einfügt, sich sozusagen vordrängelt. Als Erstes wird die Person mit der Methode push(person) ans Ende der Schlange gestellt. Danach wollte ich es noch positionieren, jedoch funktioniert das nicht.

Die neue Person wird eingefügt ganz am Ende, aber ansonsten passiert nichts. Ich hatte mir vorgestellt per Hilfsvariable die Anzahl der Durchläufe zu zählen und wenn dieser mit dem angegeben Wert, wo soll die Person hin, es dann eingefügt wird. Das geht aber nicht, wo hackt es denn da bzw. ist meine Vorstellung so überhaupt umsetzbar/machbar ?

	public void insert(Person person, int stelle) {
		push(person);
		Person search = this.first;
    	Person Vorgaenger = null;
		int durchlauf = 1;
        while (durchlauf != stelle) {
        	Vorgaenger = search;
        	search = search.getNext();

        	if(durchlauf == stelle)
                Vorgaenger.setNext(person.getNext());
        	
        	durchlauf++;
        }
	}

 

[Michael...]

Muss wohl eher so aussehen (Achtung ungeprüfter Code):

public void insert(Person person, int stelle) {
        if (stelle==0) {
        	person.setNext(this.first)
        	this.first = person;	
        }
        else if (stelle > 0){
        	Person parent = this.first;
	        for (int i=1; i<stelle; i++) {
	        	parent = parent.getNext();
	        }
	        person.setNext(parent.getNext());
	        parent.setNext(person);
        }
        else System.out.println("Ungültige Position: " + stelle);
}

Ausserdem, müssen noch die Fälle behandelt werden, wenn "stelle" <0 und >als die Listenlänge ist.

 

[Schumi]

Vielleicht solltest Du Dir vor Implementation von weiteren Operationen immer mal ein Bildchen malen, so visualisiert ist, wie die einzelnen Listenelemente verlinkt sind. Dann kannst Du Dir dort genau klarmachen, welcher Zeiger anschließend worauf zeigen soll.