einfach verkettete Listen

[Vladyslav]

Hi,
wie oben beschrieben habe ich Probleme mit den einfach verketteten Liste, evtl. könnte man mir hier helfen.
Meine Aufgabe ist es aus einer Liste von 49 Zahlen, 6 Zahlen zu ziehen. Jede der 6 zufälligen Zahlen darf nur 1x gezogen werden, da sie aus der Liste ausgekettet werden.

Vom Prinzip her habe ich es verstanden nur die Umsetzung fällt mir schwer.
- Einfach verkette Listen beginnen beim Head und enden bei null.
- Am Anfang verweisst head auf null.
- Um Knoten einzufügen musst man imemr die Liste durchlaufen.
- Um etwas auszuketten, braucht man einen Zwischenspeicher in welchem man den Knoten der nach der zu "löschenden"-Knoten kommt speichert, danach setzt verbindet man das gespeicherte Element mit dem Knoten vor dem "gelöschtem" und dann ist die Liste wieder durchgängig.
- Was löschen muss man in dem Sinne nicht, wenn man etwas auskettet reicht es schon, da der Garbage Collector sich dann darum kümmert.

Soweit so gut.

Habe mal meinen "Fortschritt" soweit ich kamm gepostet.

Beim schreiben sind mir aber Fragen aufgekommen :

Dieser abstrakter Datentyp LottoElement, dem habe ich ein Attribut ""nextListElement"" gegeben. Ein Int nimmt eine Stelle im Speicher ein nur für Zahlen, double auch doch etc.. die primitiven Datentypen nehmen immer ein festen Platz im Speicher ein .
Wie ist es bei abstrakten ? Zwischen primitiven Datentypen kann man ja umwandeln von double zu int etc.. mit (int) . Von dem DatenTyp LottoElement zu int geht ja nicht.

Jetzt wird die Liste mit den 49 Zahlen aus dem Datentyp LottoElement bestehen. Wie finde ich eine spezielle Zahl beim durchlaufen der Liste. Bei Arrays kann ich ja eine for-Schleife schreiben und mit dem int( etc..) Wert suchen ?

Jetzt gibt es zu den Listen immer das anschauliche Beispiel mit den Rechtecken die die Knoten symbolisieren. Einen head start und und null. Die Blöcke dazwischen sind die Knoten. Rechtecke in der Mitte geteilt. Die linke Seite verweisst auf seinen eigenen Knoten, die rechte auf die nächsten ggf. null.
Was ich nicht verstehe, wenn head und null immer außen vor sind. Fängt dann meine Liste statt mit 1,2,3 ; mit null,1,2 an? Oder verweißt die 1 auf head ?

--

Mein Ansatz wäre

Ich fühle mir gerade wie in dem Moment als Algebra drankamm und plötzlich Zahlen durch Buchstaben ersetzt worden sind. >.<


hilfreiche Antworten wären wirklich sehr nett, mir qualmt die Rübe.

mfG

public class LottoElement {

    int zahl;
    LottoElement nextListElement;

    public LottoElement(int zahl) {
        nextListElement = null;
        this.zahl = zahl;
    }

//    public void setNextListElement(LottoElement nextListElement) {
//        this.nextListElement = nextListElement;
//    }

    public void setZahl(int zahl) {
        this.zahl = zahl;
    }

//    public LottoElement getNextListElement() {
//        return nextListElement;
//    }

    public int getZahl() {
        return zahl;
    }

}
public class LottoList {
    
    private LottoElement head;
    
    public LottoList() {
        head = null;
    }
    
    public boolean isEmpty() {
        return head == null;
    }
    
    public static void main (String []args) {
        
        LottoList liste = new LottoList();
        
        
        }
    }

 

[mihe7]

Dieser abstrakter Datentyp LottoElement, dem habe ich ein Attribut ""nextListElement"" gegeben. Ein Int nimmt eine Stelle im Speicher ein nur für Zahlen, double auch doch etc.. die primitiven Datentypen nehmen immer ein festen Platz im Speicher ein .
Wie ist es bei abstrakten ?

Bei komplexen Datentypen wird einmal Speicher für das Objekt auf dem Heap benötigt. Die Variable nextListElement enthält dagegen nur die Adresse (8 Byte).

 

[mihe7]

Oh, da war ja noch mehr

Wie finde ich eine spezielle Zahl beim durchlaufen der Liste. Bei Arrays kann ich ja eine for-Schleife schreiben und mit dem int( etc..) Wert suchen ?

Das geht genauso. Das erste Element ist head (Index 0), wenn Du das fünfte Element willst, musst Du vier Elemente weitergehen. Wenn Du eine bestimmte Zahl suchst, kannst Du getZahl() verwenden, um zu vergleichen.

Was ich nicht verstehe, wenn head und null immer außen vor sind. Fängt dann meine Liste statt mit 1,2,3 ; mit null,1,2 an? Oder verweißt die 1 auf head ?

Bei einer einfach verketteten Liste, ist head einfach der Zeiger auf das erste Element, das wäre dann das Element mit der 1.

 

[advanced_java]

Es ist zwar etwas unschön, aber so hätte ich das gemacht:

import java.util.Random;

public class Trommel {
	private Random random = new Random();
	private int n = 0;
	private TrommelElement first = null;

	public Trommel(int n) {
		this.n = n;

		TrommelElement e = null;
		for (int i = 1; i <= n; i++) {
			if (i == 1) {
				e = (first = new TrommelElement(i));
			} else {
				TrommelElement e2 = new TrommelElement(i);
				e.setNextListElement(e2);
				e = e2;
			}
		}
	}

	public boolean isEmpty() {
		return first == null;
	}

	public int getNextInt() {
		int i = random.nextInt(n);
		n--;

		if (i == 0) {
			TrommelElement e = first;
			first = e.getNextListElement();
			return e.getZahl();
		}

		TrommelElement e = first;
		for (int j = 1; j < i; j++) {
			e = e.getNextListElement();
		}
		TrommelElement e2 = e.getNextListElement();
		e.setNextListElement(e2.getNextListElement());
		return e2.getZahl();
	}

	public static void main(String[] args) {
		Trommel lotto = new Trommel(5);
		while (!lotto.isEmpty()) {
			System.out.println(lotto.getNextInt());
		}
	}
}

class TrommelElement {
	private int zahl;
	private TrommelElement nextListElement;

	public TrommelElement(int zahl) {
		this(zahl, null);
	}

	public TrommelElement(int zahl, TrommelElement nextListElement) {
		this.zahl = zahl;
		this.nextListElement = nextListElement;
	}

	public int getZahl() {
		return zahl;
	}

	public void setZahl(int zahl) {
		this.zahl = zahl;
	}

	public TrommelElement getNextListElement() {
		return nextListElement;
	}

	public void setNextListElement(TrommelElement nextListElement) {
		this.nextListElement = nextListElement;
	}
}

Cheers!

 

[Vladyslav]

Danke, hier noch eine Frage, sitzen schon etwas länger an dem Thema und hab jetzt wieder zwei neue Klassen gemacht. Knoten und List um es mir zu vereinfachen. Check nicht genau wie ich die Sachen umsetzen soll.

Hab jetzt den Konstruktor neu
und in der Klasse List habe ich mir eine Methode aus der Vorlesung abgeschaut.

Ich verstehe aber nicht wie next auf etwas zugreifen soll. [ Knoten temp = head; ] das versteh ich.
Bei der while Schleife steht aber [temp = temp.next] ;
mit temp.next nehme ich mir das Attribut temp vom Typ Knoten und benutze den Punktoperator damit temp auf die Adresse zeigt ?
Ich kann mir darunter nichts vorstellen .

Bzw. verstehe ich es richtig?
(Bsp: ich habe 4 Zahlen in meiner Liste. )
temp verweisst bei ja auf head, head verweißt auf null. Bildlich gesprochen habe ich damit zwei Zeiger erschaffen. Beide zeigen auf den Block head in dem null steht.
Sagen wir mal ich hab schon eine List. Dann nimmt [temp.next] immer die Adresse und dann den Wert der Zahl in der Liste an. Bin ich gerade zu eingefahren, oder irre ich mich aber die while schleife zählt doch so nicht hoch in der Liste ?

    public Knoten(int zahl, Knoten next) {
        this.zahl = zahl;
        this.next = next;
    }
    
    
     // Klasse List :
private Knoten head = null;

    public List() {
        head = new Knoten();
    }


public void add(Knoten n) { //fügt  n hinten an
        Knoten temp = head; //Zeiger für temp verweisst auf head 
        while (temp.getNext() != null)
        {
            temp = temp.next;
        }
        temp.next = n;
    }

 

[Vladyslav]

Danke an @advanced_java doch ein Code bringt mir nix :/ hier geht es ums Verständnis, da hadert es gerade.

 

[advanced_java]

Guck doch einfach, was ich gemacht habe. Ich hab zwar keine add Methode eingeführt, es sollte aber dennoch ersichtlich sein, wofür temp, temp.next usw. wichtig sind (zumal du auch noch kommentierten Code hast....).

 

[Vladyslav]

Ich weiß nicht ob es abwertend gemeint ist oder nicht, das kommentierte hab ich dazugefügt ums besser zu vestehen, weiß nicht was daran falsch ist.

 

[advanced_java]

doch ein Code bringt mir nix

temp ist nichts anderes als meine e Variable.

 

[mihe7]

Ich verstehe aber nicht wie next auf etwas zugreifen soll. [ Knoten temp = head; ] das versteh ich.
Bei der while Schleife steht aber [temp = temp.next] ;
mit temp.next nehme ich mir das Attribut temp vom Typ Knoten und benutze den Punktoperator damit temp auf die Adresse zeigt ?
Ich kann mir darunter nichts vorstellen .

Also, temp referenziert ein Objekt vom Typ Knoten. Dieses Objekt enthält ein Attribut next, das seinerseits ein Objekt vom Typ Knoten referenziert (oder null ist).

temp = temp.next nimmt nun die in temp.next gespeicherte Adresse und weist sie der Variablen temp zu. Du hangelst Dich also zum nächsten Objekt.

temp verweisst bei ja auf head, head verweißt auf null. Bildlich gesprochen habe ich damit zwei Zeiger erschaffen. Beide zeigen auf den Block head in dem null steht.

Nein, temp verweist nicht auf head, sondern per temp=head weist Du der Variablen temp den Wert von head zu. Es wird der Wert von head auf temp kopiert. Dabei handelt es sich halt um eine Adresse. Du hast also zwei Zeiger erschaffen, die beide auf null zeigen.

 

[advanced_java]

public void add(Knoten n) { //fügt n hinten an Knoten temp = head; //Zeiger für temp verweisst auf head while (temp.getNext() != null) { temp = temp.next; } temp.next = n; }

Das wird nicht funktionieren, wenn head/first null is.