Verkettete Liste.

[Verkettet]

Hallo Leute,

ich habe hier eine verkettete Liste und verstehe an einem bestimmten Punkt etwas nicht.
Habe die entsprechende Stelle markiert.

class List
{
        private Node head = null;
        
        private class Node
        {
                private Data data;
                private Node next;

                public Node(Data data, Node node)
                {
                        this.data= data;
                        next = node;
                }
        }

        public void insert(Data data)
        {
                Node node = head;
               
                 if (node == null || node.data.nr > data.nr)
                {
                        head = new Node (data, node);
                }
                else
                {
                        while (node.next != null)
                {

                if (node.next.data.nr > data.nr)
                {
                        break;
                }
                node = node.next;
        }
        node.next = new Node (data, node.next);  // HIER, das verstehe ich nicht
}

Wir sagen node.next = new Node und sagen dann, das das nächste Element
das Element selbst ist? Oder komme ich da irgendwo durcheinander?

Wenn ich Node.next erzeuge kann ich doch nicht sagen das Node.next der nächste
Knoten ist oder?

 

[Marcinek]

Es sei den man hat einen Kreis;D

Ist das überhaupt kompilierbar?

 

[Verkettet]

Hier fehlt lediglich eine schließende Klammer hab ich bemerkt,
ansonsten kompiliert es. Ja!

 

[JavaProfi]

Wo hast du denn dieses Beispiel her?
Sorry, wenn ich das so sage, aber als Beispiel für eine einfach verkette Liste ungeeignet.Oder fehlt da Code?
Wenn du mal ein einfaches Beispiel für eine einfach verkettete oder doppelt verkettete Liste benötigst, schreibe ich dir ein KSKB, an dem du besser Lernen kannst.



Gruß
JP

 

[Verkettet]

Hier mal mein Kompletter Code in bisschen übersichtlicherer Form

Liste:

package test;

public class Liste {
	private Node head = null;

	private class Node {
		private Data data;
		private Node next;

		public Node(Data data, Node node) {
			this.data = data;
			next = node;
		}
	}

	public void insert(Data data) {
		Node node = head;

		if (node == null || node.data.nr > data.nr) {
			head = new Node(data, node);
		} else {
			while (node.next != null) {

				if (node.next.data.nr > data.nr) {
					break;
				}
				node = node.next;
			}
			node.next = new Node(data, node.next); // HIER, das verstehe ich
													// nicht
		}
	}

	public void delete(int nr) {
		Node node = head;

		if (node != null) {
			if (node.data.nr == nr) {
				head = node.next;
			} else {
				while (node.next != null) {
					if (node.next.data.nr == nr) {
						node.next = node.next.next;
						break;
					}
					node = node.next;
				}
			}
		}
	}

	public Data member(int nr) {
		Node node = head;

		while (node != null) {
			if (node.data.nr == nr) {
				return node.data;
			}
			node = node.next;
		}
		return null;
	}

	public void print() {
		Node node = head;

		while (node != null) {
			System.out.println(node.data);
			node = node.next;
		}
		System.out.println();
	}
}

Data:

package test;

public class Data {
	public int nr = 0;
	
	public Data(int nr) {
		this.nr = nr;
	}
	
	public String toString() {
		return "" + nr;
	}
}

Main:

package test;

public class Main {
	public static void main(String[] args) {
		Data eins = new Data(1);
		Data zwei = new Data(2);
		Data drei = new Data(3);
		Data vier = new Data(4);
		
		Liste liste = new Liste();
		liste.insert(zwei);
		liste.print();
		liste.insert(drei);
		liste.print();
		liste.insert(eins);
		liste.print();
		liste.insert(vier);
		liste.print();
	}
}

Das funktioniert alles wunderbar so wie es soll, nur wie gesagt ich verstehe nicht warum
dem node.next node.next als nächstes Element übergeben werden muss und nicht node.next.next....

 

[Verkettet]

Ich glaube ich habe es verstanden, wäre aber nett wenn das jemand bestätigen könnte.

In node.next steht z.B. null drin.
Jetzt erzeuge ich einen neuen Knoten:

new Node(data, node.next)

und weiße das meinem next zu:

node.next = new Node(data, node.next)

Dann wird ganz einfach aus meinem null ein New Node und im neuen Knoten
wird das next auf null gesetzt.



Beispiel für node.next = 4;

node.next = new Node(data, node.next)

Es wird eine eine Node eingefügt die kleiner 4 ist dann wird node.next
die neue Zahl zugewisen (new Node(data,..)) und node.next auf 4 gesetzt.

Richtig so?

 

[AquaBall]

Ist schon richtig, (deshalb funktionierts auch :lol.

node = head;
...
node.next = new Node(data, node.next)

Du beginnst oben, wanderst evtl. weiter.
Letzlich stehst du an einer Stelle, an der du einen neuen Knoten einfügen willst.
Du gibst diesem node ein neues Objekt, und diese (neue) Objekt zeigt auf den (noch) alten Nachfolger, damit die Reihe wieder angeknüpft wird.

Du könntest auch ausführlicher schreiben:

insertStelle = head;
...
Node neuerKnoten = new Node(data, insertStelle.next); // Der neue Knoten soll den Rest der Reihen anhängen.
insertStelle.next = neuerKnoten

(Ich würde auch nicht alles nur 'node' nennen, sondern sprechendere Namen geben.)

 

[Dekker]

Der Grund für die Zeile ist einfach folgender:

Wenn du dir den Code ansiehst, wird mittels node = node.next solange ein knoten gesucht, bis node.next.data.nr > data.nr oder eben node.next != null gilt. Warum man das nicht beides in der whilebedingung prüft verstehe ich nicht, da man eigentlich nur die von mir zuerst genannte Bedingung negieren müsste.

Im Grunde genommen wird dann ein neuer Knoten als Nachfolger der somit bestimmten Node eingesetzt. Natürlich musst du dann aber den Nachfolger deines neuen Knotens auf den alten Knoten next des Knotens setzen, in dem er eingesetzt wird. Ansonsten verlierst du nämlich alle Knoten nach deinem neuen Knoten. Ein Beispiel:

Liste sieht so aus:

1->5->6->9->null

insert(4)

1->4->5->6->9->null

Wenn du den node.next von 1 (was in diesem Falle 5 wäre) nicht übernimmst, würde deine Liste wie folgt aussehen

1->4->null

Somit wäre deine Liste ab 4 gelöscht.