Eigene LinkedList und Nodes

[mamelinchen]

Ziel ist es, eine LinkedList selber zu schreiben.
Am Anfang existieren nur der Node head und der Node tail.
Head zeigt nur auf den nächsten Node, ohne Objekt, Node auf Objekt und nextNode.
Tail soll am Ende wieder auf den head zeigen.

Wie ich es dann recht verstehe sind die Instanzvariablen von LinkedList dann

public  class LinkedList extends List{
protected Node head;          
protected Node tail;

...Node(Node next,Objekt objekt){ //Node-Klasse in LinkedList mit Iv,Konst
...
}

}

Was ist mit einem Index?
Ist er auch eine Instanzvariable von LinkedList?
Oder soll ich den weglassen?
Woher soll ich dann wissen wo dann mein neues Objekt in der Liste hinmuss ohne Index?

Bin bissl verwirrt und unsicher...:bahnhof:

will ja nicht gleich Fehler am Anfang machen und dann damit weiterarbeiten.:autsch:

 

[diggaa1984]

also add .. hängt die elemente einfach stumpf vor den tail und biegt alle nötigen anderen referenzen um. Wenn du nun nen insert durchführen willst, dann musst du dich vom 1. element bis zum jeweiligen betroffenen durchhangeln und da dann alle referenzen umbiegen. Ob du da bei 0 oder 1 anfängst mit zählen spielt an sich keine rolle, aber 0 wäre intuitiver für mich

 

[0x7F800000]

Am Anfang existieren nur der Node head und der Node tail.

Am Anfang würde ich head und tail auf ein und denselben dummy-knoten zeigen lassen.

Tail soll am Ende wieder auf den head zeigen.

wozu das? Für eine unnötige extra Abfrage bei hasNext()?

Was ist mit einem Index?

Was für ein Index? Verkettete Listen erlauben kein random access. Ein Element mit einem bestimmten Index aufzusuchen ist bei verketteten Listen eine unverhältnismäßig teuere Angelegenheit [ O(n) statt O(1) wie bei Arrays bzw ArrayList bzw Vector ]

Woher soll ich dann wissen wo dann mein neues Objekt in der Liste hinmuss ohne Index?

einfach ans ende dranhängen, dazu ist tail ja da...

will ja nicht gleich Fehler am Anfang machen und dann damit weiterarbeiten.:autsch:

Dieses unangenehme Gefühl sollte man sich nicht angewöhnen. Sieh es ganz locker, sag dir: "das ist ein schmierblatt, und ich habe fest vor, den code größtenteils wegzuschmeißen" und schreib dann einfach los, ohne großartig gedanken zu machen. Wenn's nicht klappt, dann schmeißt du es eben weg, und fängst mit den eben gesammelten erfahrungen neu an. Besser als ewig rumzusitzen, und sich die theoretisch optimale Lösung herzuleiten... Bei kleinen Sachen macht's ja nichts aus.

 

[diggaa1984]

zwischenfrage: ist das eine Einfach-verkettete Liste oder doppelt?

Würde bei einfach-verketteten der Tail.next auf das letzte Element zeigen? Wäre ja quasi n rückwärtsschritt. Bei doppelt gäbs ja dafür den .previous-Part

 

[0x7F800000]

Würde bei einfach-verketteten der Tail.next auf das letzte Element zeigen?

dann wäre tail sowas wie das vorletzte element oder wie? Ne, das ist irgendwie schräg ???:L
bei doppelt verketteten Listen würde ich aus symmetriegründen wohl zwei dummy Nodes an den anfang und ans ende dranhängen. Eigentlich ist es vollkommen egal, hauptsache man kommt nicht durcheinander...

 

[diggaa1984]

jo bei doppelt is klar, aber bei einfach, müsste man ja dann sogar beim add immer komplett über die liste rennen, macht ja auch kein sinn .. das könnte man mit tail.next ein wenig umgehen auch wenns nicht ganz in die vorstellung passt.

aus eben diesem grund stellte sich mir grad die frage

 

[0x7F800000]

jo bei doppelt is klar, aber bei einfach, müsste man ja dann sogar beim add immer komplett über die liste rennen, macht ja auch kein sinn .. das könnte man mit tail.next ein wenig umgehen auch wenns nicht ganz in die vorstellung passt.

Wieso? In tail speichere man einfach das letzte vorhandene Element. Bei append macht man einfach nur:

append(T value){
   tail.next=(tail=new Node(value));
}

 

[diggaa1984]

Zitat von diggaa1984
Würde bei einfach-verketteten der Tail.next auf das letzte Element zeigen?

dann wäre tail sowas wie das vorletzte element oder wie? Ne, das ist irgendwie schräg

aber bei einfach, müsste man ja dann sogar beim add immer komplett über die liste rennen

Wieso? In tail speichere man einfach das letzte vorhandene Element

ein innerer konflikt!? liest sich so widersprüchlich :bahnhof::lol:

append(T value){
   tail.next=(tail=new Node(value));
}

//wenn dann so, sonst kommst vom head nich hin :D
append(T value){
   Node n = new Node(value);
   tail.next.next = n;
   tail.next= n;
}

2-zeichen-text-damit-ich-das-posten-kann-da-der-das-da-oben-im-quote-nicht-erkennen-kann

 

[0x7F800000]

äääh, was? :autsch:
"tail speichere man einfach das letzte vorhandene Element"
noch besser man nennt es "last". Was davon hört sich widersprüchlich an? ???:L

 

[diggaa1984]

zu dem was du vorher bezüglich meiner identischen idee gesagt hattest .. halb so wild

 

[0x7F800000]

Verstehe ich immer noch nicht, sorry zuviel crack im hirn... :autsch:?

Zwischen dem letzten und dem vorletzten element besteht imho schon ein nicht vernachlässigbarer inhaltlicher unterschied. Wozu zugriffe wie
tail.next.next
gut sein sollen, fällt mir spontan auch nicht ein. :bahnhof:

 

[diggaa1984]

ach jetzt versteh ich dich .. bei mir is tail schon immer n Dummy-Node gewesen, der keine info enthält. Bei dir ist tail eben, das letzte gültige Element der Liste. Jeder wie ers gewohnt ist

 

[mamelinchen]

Also von doppelt verketteter Liste ist wohl nicht die Rede...

Klasse LinkedList,die das Interface List(von mir ohne java.util) als einfach verkettete und nicht zirkuläre Liste implementiert.


Originalsatz:
Der Hilfsknoten tail soll die Invariante tail.next==tail zum Abschluss (und damit auch bei Beginn) aller Methoden erfüllen.

Wie bekomme ich dann zB

public Person get(int i)?

 

[maki]

Kannst doch deine Liste durchlaufen bis zum Index i.

 

[faetzminator]

als pseudo code:

get(int i) {
    if (i < 0) {
        throw new IndexOutOfBoundsException();
    }
    Node node = this.getStartNode();
    while (i-- > 0) {
        if (node.isTail()) {
            throw new IndexOutOfBoundsException();
        }
        node = node.getNext();
    }
    return node;
}

 

[mamelinchen]

Ick kanns die Objekte nicht ans Ende hängen...ich habe Methoden vorbekommen wie:

void insert(int i,Object object)
remove(int i)

Ich soll sie genau an diese Stellen setzen..
oder an der stelle löschen :/

wie soll ich das machen?

Hilfsknoten head am Anfang und tail am Ende.
Zeigt dann head auf tail?und tail auf sich selbst.Am Anfang?Ist die LinkedList am Anfang leer?
Wie soll ich das initialisieren?
Ich brauche dann 2 Konstruktoren?

public Node (Person person){
                this.next=null;
                this.person=person;
            }

und der andere dummy für head und tail?
head und tail haben doch keine referenz auf ein objekt mehr....
sie zeigen doch nur auf die knoten selbst.

public Node (){
                this.next=null;
            }

Wo sage ich denn auf was der Node zeigt?

hab viel gelesen und bin immernoch verwirrt???:L

 

[SlaterB]

denken und selbst entscheiden, das sind die Regeln, nichts ist in Stein gemeißelt,
erlaubt ist was funktioniert,

head und tail könnten anfangs null sein,
beim ersten Element ist next null, head und tail zeigen auf dieses neue Element,

kommt dann ein neues hinzu, dann entweder auf Position 0 oder 1,
je nachdem muss entweder head oder tail neu gesetzt werden
(Code wie if (position == 0) ist doch nicht schwer?)

außerdem muss entweder next des neuen Nodes auf den einzigen alten zeigen oder umgekehrt

das muss nicht alles in einer Zeile passieren, verwende neben Konstruktoren auch getNext() und setNext()
nach und nach einzelne Schritte bis am Ende alle Referenzen stimmen

 

[mamelinchen]

Ick bin mir net sicher , ick habs jetzt so gemacht, dafür das ick es überhaupt net raffe...

ich hoffe ihr wisst , was ick damit erreichen will^^
Und ick bin mir sicher das ick irgend n Mist gebaut habe, bloss ick wees net wo!

    public void insert(int i, AbstractPerson person) {
        if (i<0){
             throw new IndexOutOfBoundsException();
        }
        else if (i==0){
            head = new Node(person, head.next);
            }
        else{
            Node f;
            int stelle= 0;
            for(f=head.next;f==tail;f=f.next)
                stelle++;
            if(stelle>i){
                Node g=new Node(person,f.next);
                g.next=f;
            }
            
            tail = new Node(person, tail);
        }
    }

 

[mamelinchen]

  tail = new Node(person, tail);

dis is quatsch, sorry!

denken und selbst entscheiden, das sind die Regeln, nichts ist in Stein gemeißelt,
erlaubt ist was funktioniert,

das sag ma meenem dozenten....

 

[faetzminator]

[offtopic]Kannst du auch Schriftdeutsch schreiben? Sogar ich kann das [/offtopic]

 

[mamelinchen]

???:L

Ich wollte nur fragen ob meine Methode insert funktioniert!

Ich hangel mich wie ein Affe von Knoten zu Knoten, ein Zähler zählt mit, und wenn dieser kleiner i ist, dann setze ich ein^^