Doppelverkettete Listen

[ohsmos]

Hallo,

ich habe leider totale Schwierigkeiten doppelverkettete Listen anzuwenden.
Videos, Lesematerial und sonstiges haben auch nicht viel gebracht.
Hier mal eine Aufgabenstellung: (Es waren mehrere Aufgaben enthalten, wie gesagt es geht mir jedoch nur um Listen)

Der dazugehörige Code:
[JAVA]
public class Aufgabe1 {
public static void main(String[] args) {
int[] p1 = { 11, 13, 13, 24, 77, 89, 90, 91, 92 };
int[] p2 = { 12, 14, 15, 19, 26, 29, 33, 52, 56, 76 };
int[] p3 = { 12, 14, 15, 19, 23, 29, 46, 53, 76 };

System.out.print("\nd) ");
Liste list = s.ArrayToList(p2, p3);
Element listElement = list.Kopf;
while (listElement != null) {
System.out.print(listElement.Zahl + " ");
listElement = listElement.Nf;

}
}[/code]

[JAVA]public Liste ArrayToList(int[] a, int[] b) {
// hier die Lösung eintragen...
return new Liste();
}
}
class Liste {
Element Kopf, Fuss; // Listen-Anfang und Ende.
Liste() { Kopf = Fuss = null; }
}
class Element // Ein Element der Liste.
{ int Zahl; // In das Element eingetragene Zahl.
Element Nf; // Nachfolge-Element in der Liste.
Element(int Zahl) { this.Zahl = Zahl; Nf = null; }}
[/code]

Ich weiß beispielsweise nicht wie ich nun Elemente in die Liste hinzufügen kann.
Oder wie man danach die Liste komplett sortiert usw usw usw....

 

[Tarrew]

Also erstmal brauchst du ja irgendwelche Methoden um neue Elemente einzufügen oder zu löschen. Entweder du fügst die Elemente direkt sortiert ein, oder du fügst sie der Reihe nach ein und sortierst sie am Ende.

Auf dem Bild ist übrigens eine einfach-verkettete Liste und deine Klasse "Element" deutet auch eher auf eine einfach-verkette Liste hin.
EInfügen und Löschen könnte man zB so anfangen:

	void insert(int value){
		if(Kopf == null){
			Kopf = new Element(value);
			Fuss=Kopf;
		}else{
			
			//...
		}
	}
	
	void delete(int value){
		Element tmp = Kopf;
		while(tmp!=null){
			if(tmp.Zahl==value){
				//...
				return;
			}
			tmp=tmp.Nf;
		}
	}

Variablennamen sollte man eig. klein schreiben. Habs jetzt mal aus deinen Klassen übernommen aber im Normalfall lieber "kopf" und "fuss" statt "Kopf" und "Fuss".
Du hast ja immer eine Referenz auf das Ende der Liste mit "Fuss". Wenn du also ein neues Element einfügen willst, musst du den Nachfolger von Fuss auf das neue Element setzen. Danach musst du natürlich auch den "Fuss" umsetzen.

Wenn das einfügen läuft musst du nur das Array durchlaufen und die Elemente einfügen.
Und dann die Liste sortieren. Alternativ direkt beim einfügen sortieren. Das liegt dann bei dir

 

[ohsmos]

Ich habe es leider immer noch nicht ganz verstanden....
Außerdem hast du ja komplett falsch deklaiert.

Wäre es möglich, dass mir jemand die Lösung dazu gibt?
Oder mir wenigstens den Anfang?

 

[Joose]

ich habe leider totale Schwierigkeiten doppelverkettete Listen anzuwenden.
Hier mal eine Aufgabenstellung: (Es waren mehrere Aufgaben enthalten, wie gesagt es geht mir jedoch nur um Listen)

Sorry wenn ich nachfrage, aber wo in der Aufgabe ist von "doppelt verkettenden Listen" die Rede?

 

[ohsmos]

Sorry wenn ich nachfrage, aber wo in der Aufgabe ist von "doppelt verkettenden Listen" die Rede?

Hallo,

wie bereits Tarrew erkannt hat, sind es keine doppelt sondern einfach verkettete Listen.
Tut mir leid für die falsche Beschreibung.
Glücklicherweise konnte ich das ganze bereits lösen.

Lösung 1): Zu beachten ist, dass ich mich hier noch an eine andere Methode begnüge "merge"(Sortierung)

	public int[] merge(int[] p, int[] q) {

		int count = 0;

		int[] result = new int[p.length + q.length];
		int puffer = 0;

		for (int i = 0; i < p.length; i++) {
			result[i] = p[i];
		}
		for (int j = p.length; j < result.length; j++) {
			result[j] = q[count];
			count++;
		}

		// sehr einfache möglichkeit zu sortieren
		// Arrays.sort(result);

		// BubbleSort: [url]https://www.youtube.com/watch?v=T5CZoQ_Sppo[/url]
		boolean doNotChange;

		do {
			doNotChange = false;

			for (int i = 0; i < result.length; i++) {
				boolean lastElement = (i + 1 < result.length);

				if (lastElement) {
					boolean changeElement = (result[i] > result[i + 1]);
					if (changeElement) {
						puffer = result[i];
						result[i] = result[i + 1];
						result[i + 1] = puffer;

						doNotChange = true;
					}
					// System.out.println("D: " + doNotChange + " i: " + i);
				}
			}
			// Wiederholung: while solange while True ist wiederholt sich das
		} while (doNotChange);

		return result;
	}


public Liste ArrayToList(int[] a, int[] b) {
		// hier die Lösung eintragen...
		
		Liste liste = new Liste();
		int[] c = merge(a, b);
		
	
		for(int i = 0; i < c.length; i++){
			if(c[i] > 10 && c[i] < 99){
				if(liste.Kopf == null){
					liste.Kopf = liste.Fuss = new Element(c[i]);
				}
				else{
					if(liste.Fuss.Zahl != c[i]){
						liste.Fuss.Nf = new Element(c[i]);
						liste.Fuss = liste.Fuss.Nf;
					}
				}
			}
		}
		

		return liste;
	}

Lösung 2) vom User: camelCase90 dickes Danke !

public ArrayList<int> arrayToList(int[] a, int[] b) {
 
    ArrayList<int> listResult = new ArrayList<int>();
    int[] arrayFusion = new int[(a.length + b.length)];
    arrayFusion = Arrays.copyOf(a, (a.length + b.length));
    System.arraycopy(b, 0, arrayFusion, a.length, b.length);
 
    for(int i = 0; i <  (a.length + b.length); i++) {
                    if(!listResult.contains(arrayFusion[i]) && arrayFusion[i] > 10 && arrayFusion[i] < 99) 
         listResult.add(arrayFusion[i]);
    }
 
    return listResult;
}