Eine eigene Liste erstellen - verwendung von Nodes?

[blawa]

Hallo alle, also ich muss für die Uni ein Programm schreiben, was folgendes kann:

Ein Listenklasse ist zu schreiben (mit Typparameter), welche Elemente einfügen kann, jedoch aufsteigend sortiert.

Ok die normale Liste zu schreiben ist nicht schwer, aber ich verstehe den Einsatz der Nodes nicht ganz.
Sind Nodes Zeiger die auf ein bestimmtes Element zeigen?

Weil unser Grundgerüst ist ca so:

public abstract class Set<A> implements Collection<A> {
	Comparator<A> xc;
	protected class Node {
		A elem;
		Node next = null;
		Node (A elem) { this.elem = elem; }
	}
	protected Node first= null, second = null;
        .... Hier wird der iterator definiert ....
public void insert (A x) {
		if (first == null) {
			second = first = new Node(x);
		}
                else {
			second = second.next = new Node(x);
				
		}

So, das ist Teil eines aus dem Skriptum stehenden Listen.Konstrukts.
Aber wie genau funktionieren diese Nodes?
Weil was macht second = second.next = new Node(x); genau?

Ich habe mir das so ausgemalt, aber weis nicht ob ich mich da irre:

x1 o x2 o x3

Die 'o' würden dann die Nodes darstellen, xn Elemente.
Stimmt das so oder sieht das ganze anders aus?

Hoffe jemand kann mir antowerten

mfg

 

[takidoso]

Sind Nodes Zeiger die auf ein bestimmtes Element zeigen?

das kann man gewissermaßen mit ja beantworten
Ein Node in Deinem Fall scheint den Inhalt des Elementes zu haben (genaugenommen zeigt da drauf) und zeigt gleichzeitig auf den nächsten Node in Deiner Liste.

So, das ist Teil eines aus dem Skriptum stehenden Listen.Konstrukts.
Aber wie genau funktionieren diese Nodes?
Weil was macht second = second.next = new Node(x); genau?

public abstract class Set<A> implements Collection<A> 
{
    Comparator<A> xc;
    protected Node first       = null; 
    protected Node second = null;

    protected class Node 
    {
        A elem;
        Node next = null;
        Node (A elem) 
         {
               this.elem = elem; 
         }
    }

    public void insert (A x) 
    {
       if (first == null) 
       {
          second = first = new Node(x);
           // übersichtlicher wäre:
           // first  = new Node(x);
           // second = first;             
       }      
       else 
       {          
           second = second.next = new Node(x);
           // übersichtlicher wäre:
           // second.next = new Node(x);
           // second      = second.next;
     }

Wie Du siehst habe ich das Grundgerüst mal ein wenig durch Einrücken etc. zumindest aus meiner Sicht übersichtlicher gemacht. (Habe so den Verdacht der, der diese Vorgabe machte hatte Euch entweder ärgern wollen oder hat wirklich so einen unglückichen Stil.
Die Bezeichnung second denke ich sollte man lieber in last umbenennen, denn nach einem insert() wird in second immer das letzte Element stehen. Beim aller ersten Mal (deswegen die Fallunterscheidung mit first==null) ist das erste Element mit dem letzten Element identisch.

Ich hoffe Dir etwas ausgeholfen haben zu können

Takidoso

 

[blawa]

Ja hast du, aber ich bin auch selber draufgekommen (stand auf der Leitung scheinbar)

Verwirrt hat mich eben das second=second.next= new Node(x);

Weil ich zuerst dachte, dass das second auf das neue Element zeigt, und dass dann das next von dem neuen Element wieder auf sich selbst zeigt, was ja nicht stimmt ^^


Aber jetzt weis ich nicht, wie ich einen Typ-unabhängigen Comperator einbauen kann.

Hat da jemand einen Rat?

 

[takidoso]

ja auch dafür gibt es Rat
schau doch mal in den Sourccode (JDK) der anderen Collections, die einen Comparator aufnehmen können. Ich wette du wirst alles notwendige dort finden.