generische, sortierte Liste

[sakizzo]

Hallo...

in unserer Übung sollen wir in der Uni folgende Aufgabe realisieren:
___________________________________________________________________________
Schreiben Sie eine Java-Klasse SortedList, die eine generische, sortierte Liste realisiert
Die Liste soll folgende Methoden bereitstellen:

/**
* Methode zum Hinzufügen eines Wertes in eine gemaess Comparable sortierte
* Liste. Dabei ist es möglich, dass Werte mehrfach vorhanden sind.
* @param elem der hinzuzufügende Wert
*/
public void add(T elem);

/**
* Methode zum Entfernen von Werten aus einer Liste.
* Falls der übergebene Wert mehrfach vorhanden ist,
* werden alle Vorkommen dieses Wertes aus der Liste entfernt
* @param elem der zu entfernende Wert
*/
public void remove(T elem);

Intern soll die Java-Klasse durch eine doppelt verkettete Liste realisiert werden.
____________________________________________________________________

Könnt ihr mir Denkanstöße geben, wie ich das am Besten anstelle?

 

[Kai008]

Schreib ne Klasse die von LinkedList erbt. Ich kenne grad die Methoden von der nicht auswendig, weil ich sie nahezu nie verwende, glaube aber sie vererbt beide die du brauchst.

 

[fjfvo]

Hallo

diese Aufgabe ist vielleicht so gedacht dass man selber eine Datenstruktur kreiert.
Also eine private interne Klasse Node erstellen, diese Klasse hat Attribute previous und next vom Typ Node.
Liste bleibt sortiert wenn man in der add Methode an der richtige Stelle hinzufügt.
Löschen von mehrfach vorhandene Elemente ist einfach weil die Liste sortiert ist und T Comparable ist.

 

[Aya12345]

Hi.
Ich muss die selbe Aufgabe lösen. Habe jetzt bisher diesen Code zusammengeschrieben.

public class SortedList<T extends Comparable<T>>{

private Kette daten;

	public SortedList(){
		daten = null;
	}
	
	class Kette{
	    public T data; 
	    public Kette next;
	    public Kette(T elem) {		 //Konstruktor
	      data = elem;
	    }
	    public void display() {
	        System.out.print(data + " ");
           }

	  }
  
  public void add(T elem){
	    Kette neuK = new Kette(elem); 
	    Kette vorgaenger = null; 
	    Kette temp = daten;

	    while (temp != null && (elem.compareTo(temp.data)>0)){
	      vorgaenger = temp;
	      temp = temp.next;
	    }
	    if (vorgaenger == null)
	      daten = neuK; 
	    else
	      vorgaenger.next = neuK; 
	    neuK.next = temp; 
	  }

  
  	public void remove(T elem){
		
	}
  	
  	 public void displayList() {
  	    System.out.print("List: ");
  	    Kette temp = daten; 
  	    while (temp != null){
  	      temp.display(); 
  	      temp = temp.next;
  	    }
  	    System.out.println("");
  	  }

  	
  	  	

	public static void main(String[] args) {
		
		SortedList<T> theSortedList = new SortedList<T>();
		theSortedList.add(20);
		theSortedList.displayList();
	    
	}

}

Folgenden Fehler bekomm ich beim Compilieren.

Multiple markers at this line
- Cannot make a static reference to the non-
static type T
- Cannot make a static reference to the non-
static type T

Ein Freund hat mir teilweise bei der Aufgabe geholfen, aber jetzt sind wir mit unserem Latain am Ende. Ich weiß auch im Endeffekt nicht, ob es ueberhaupt richtig ein Element hinzufügt, da ich ja nicht compilieren kann (die Remove Methode ist noch nicht drin - haette da auch jemand Tipps dazu?)

Danke im Vorraus.

 

[Aya12345]

Nochmal ich.. mein Fehler ist mir jetzt klar geworden! *Kopf -> Tisch*

Jedenfalls würde ich mich freuen, wenn ich einen Tipp für public void remove(); kriegen könnte

 

[Vereth]

Hier erstmal ein paar grundsätzliche Tipps:

• Ein immer wieder gern genutzter Kunstgriff ist es, einen immer vorhandenen Kopf-Node zu haben, das den Datenwert null hat, und zu Beginn sich selbst als Vorgänger und Nachfolger hat; dadurch wird die Liste ringförmig verkettet, was ein paar Fallunterscheidungen erspart bzw. vereinfacht.
• null-Werte werden nicht eingefügt.

Das Löschen ist dann ganz einfach:

wenn elem == null, dann fertig // Parametertest!
Nachfolger des Kopf-Nodes wird aktueller Node
solange Datenwert != null && Datenwert <  elem
- Nachfolger wird aktueller Node
solange Datenwert != null && Datenwert == elem
- Vorgänger  wird Vorgänger  des Nachfolgers
- Nachfolger wird Nachfolger des Vorgängers
- Nachfolger wird aktueller Node
fertig

Die Vergleiche musst du natürlich mit compareTo-Aufrufen machen