2011-01-01 15 views
1

Ich habe einige Probleme, die lineare verknüpfte Listendatenstruktur zu verstehen. Dies ist, wie ich ein Listenelement definieren:Die lineare verknüpfte Liste verstehen

class Node{ 
    Object data; 
    Node link; 

    public Node(Object pData, Node pLink){ 
     this.data = pData; 
     this.link = pLink; 
    } 
} 

es einfach zu halten wir sagen, dass eine Liste Knoten verbunden ist, so dass wir (Rekursion Prinzip) keine Klassenliste definieren müssen.

Mein Problem ist, dass ich wirklich verwirrt bin zu verstehen, wie Knoten verbunden sind, genauer gesagt die Reihenfolge der Knoten, wenn wir sie verbinden.

Node n1 = new Node(new Integer(2), null); 
Node n2 = new Node(new Integer(1), n1); 

Was ist ein Link? Ist es das vorherige oder das nächste Element? Irgendwelche anderen Vorschläge, um mir zu helfen, diese Datenstruktur zu verstehen?

Antwort

5

Vielleicht hilft Ihnen diese Zeichnung zu verstehen.

alt text

(Beachten Sie, dass die Pfeile Referenzen NICHT Zeiger für Java sind)

Die „Liste“ wird ein Verweis auf den ersten Knoten.

+0

+1 - Schöne Grafik. – duffymo

1

In einer einfach verknüpften Liste ist es "next".

Es sieht wie Java aus, obwohl Sie es nicht als solches markiert haben. Wenn das wahr ist, sollten Sie die Verwendung von Generika:

public class Node<T> 
{ 
    T value; 
    Node<T> next; 
} 
4

link ein Verweis auf den nächsten Knoten in der Liste ist.

Sie würden also am ersten Knoten in der Liste beginnen, n1, auf den Sie direkt verweisen würden. Um den zweiten Knoten in der Liste zu erhalten, verweisen Sie auf n1.link.

über die Liste zu durchlaufen, würden Sie etwas Ausgangspunkt haben müssen, wie n1, dann link wiederholt Referenz:

Node n = n1; 
while (n != null) { 
    println(n.data); 
    n = n.link; 
} 
0

Ich habe zwei Vorschläge.

Zuerst über das "ist das das vorherige oder das nächste Element": es hängt von Ihrer Datenstruktur ab. Normalerweise ist es das nächste Element.

Zweitens würde ich empfehlen, einen Zeiger oder eine Referenz zu verwenden. (Und Ihre C++ Syntax ist falsch: this ein Zeiger ist, und der new Operator gibt auch einen Zeiger nicht sicher, ob Sie C++ verwenden, obwohl, da Sie kein lanugage angegeben haben..)

So zum Beispiel:

class Node { 
    Object data; 
public: 
    Node *next; 

    Node (Object pData, Node *pLink) { 
     this->data = pData; 
     this->next = pLink; 
    } 
} 

Dies wäre eine gültige Struktur. Dann könnten Sie tun:

Node *n3 = new Node(new Integer(2), null); 
Node *n2 = new Node(new Integer(1), n1); 
Node *n1 = new Node(new Integer(3), n2); 

oder einfach

Node *n1 = new Node(new Integer(3), new Node(new Integer(1), new Node(new Integer(2), NULL))); 

Dann könnten Sie durch die Liste durchlaufen wie folgt:

for (Node *current = n1; current != NULL; current = current->next) 
{ 
    // do something with the current element 
} 

Ich hoffe, das hilft!


Wenn Sie eine moderne Sprache verwenden, gibt es bereits vorgefertigte Listenstrukturen in C++ 's stl verknüpft, in .NET es in System.Collections.Generic ist und ich bin sicher, es gibt auch ein Java-Pendant.

+0

es ist java ...... –

+0

Ja, es gibt eine Java List-Schnittstelle und eine LinkedList-Implementierung dafür. Ich denke, die Frage ist immer noch relevant, weil dies ein Student ist, der die Implementierungsdetails verstehen will. – duffymo