Warum verwenden verknüpfte Listen Zeiger, anstatt Knoten innerhalb von Knoten zu speichern?

121

Ich habe zuvor ausgiebig mit verknüpften Listen in Java gearbeitet, bin aber sehr neu in C ++. Ich habe diese Knotenklasse verwendet, die mir in einem Projekt gegeben wurde

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

aber ich hatte eine Frage, die nicht sehr gut beantwortet wurde. Warum ist es notwendig zu verwenden

Node *m_next;

um auf den nächsten Knoten in der Liste zu zeigen, anstatt

Node m_next;

Ich verstehe, dass es besser ist, die Zeigerversion zu verwenden; Ich werde nicht über Fakten streiten, aber ich weiß nicht, warum es besser ist. Ich erhielt eine nicht so klare Antwort darauf, wie der Zeiger für die Speicherzuweisung besser ist, und ich fragte mich, ob mir hier jemand helfen könnte, das besser zu verstehen.

c++ pointers linked-list m0meni
quelle
14
@self Verzeihung? Warum sollte eine Sprache, in der alles ein Zeiger ist, keine verknüpften Listen haben?
Angew ist nicht mehr stolz auf SO
41
Es ist wichtig zu beachten, wie sich C und C ++ in Bezug auf Objektzeiger und Referenzen von Java unterscheiden. Node m_nextist kein Verweis auf einen Knoten, sondern ein Speicher für den gesamten Knoten Node.
Brian Cain
41
@self Java hat Zeiger, die Sie einfach nicht explizit verwenden.
m0meni
27
Schildkröten bis zum Anschlag sind keine Option. Der Wahnsinn muss irgendwo enden.
WhozCraig
26
Bitte vergessen Sie alles , was Sie über Java wissen. C ++ und Java behandeln den Speicher grundlegend unterschiedlich. In dieser Frage finden Sie Buchempfehlungen. Wählen Sie eine aus und lesen Sie sie. Sie werden uns allen einen großen Gefallen tun.
Rob K

Antworten:

218

Es ist nicht nur besser, es ist der einzig mögliche Weg.

Wenn Sie ein Node Objekt in sich selbst speichern würden, welches wäre sizeof(Node)das? Es wäre sizeof(int) + sizeof(Node), was gleich wäre , was gleich sizeof(int) + (sizeof(int) + sizeof(Node))wäre sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))usw. bis unendlich.

Ein solches Objekt kann nicht existieren. Es ist unmöglich .

Emlai
quelle
25
* Es sei denn, es wird träge ausgewertet. Unendliche Listen sind möglich, nur nicht mit strenger Auswertung.
Carcigenicate
55
Bei @Carcigenicate geht es nicht darum, eine Funktion für das Node-Objekt auszuwerten / auszuführen, sondern um das Speicherlayout jeder Node-Instanz, das zur Kompilierungszeit festgelegt werden muss, bevor eine Auswertung erfolgen kann.
Peteris
6
@ DavidK Es ist logisch unmöglich, dies zu tun. Sie brauchen hier einen Zeiger (also wirklich eine Indirektion) - sicher, dass die Sprache ihn vor Ihnen verbergen kann, aber am Ende führt kein Weg daran vorbei.
Voo
2
@ David Ich bin verwirrt. Zuerst stimmen Sie zu, dass es logisch unmöglich ist, aber dann möchten Sie darüber nachdenken? Entfernen Sie alles von C oder C ++ - es ist unmöglich in einer Sprache, die Sie sich jemals erträumen könnten, soweit ich sehen kann. Diese Struktur ist per Definition eine unendliche Rekursion, und ohne ein gewisses Maß an Indirektion können wir das nicht brechen.
Voo
13
@benjamin Ich habe tatsächlich darauf hingewiesen (weil ich wusste, dass sonst jemand dies ansprechen würde - nun, es hat nicht geholfen), dass Haskell die Thunks zum Zeitpunkt der Erstellung zugewiesen hat und dies daher funktioniert, weil diese Thunks uns die Indirektion geben, die wir brauchen. Dies ist nichts anderes als ein Zeiger mit zusätzlichen Daten in Verkleidung ...
Voo
178

In Java 

Node m_node

speichert einen Zeiger auf einen anderen Knoten. Sie haben keine Wahl. In C ++

Node *m_node

bedeutet das Gleiche. Der Unterschied besteht darin, dass Sie in C ++ das Objekt tatsächlich speichern können, im Gegensatz zu einem Zeiger darauf. Deshalb muss man sagen, dass man einen Zeiger will. In C ++:

Node m_node

bedeutet, den Knoten genau hier zu speichern (und das kann für eine Liste eindeutig nicht funktionieren - Sie erhalten eine rekursiv definierte Struktur).

pm100
quelle
2
@ SalmanA Das wusste ich schon. Ich wollte nur wissen, warum es ohne einen Zeiger nicht funktionieren würde, was die akzeptierte Antwort viel besser erklärte.
m0meni
3
@ AR7 Beide geben die gleiche Erklärung, knapp unter zwei verschiedenen Ansätzen. Wenn Sie es als "reguläre" Variable deklarieren, wird dies beim ersten Aufruf eines Konstruktors für eine neue Instanz instanziiert. Aber bevor die Instanziierung abgeschlossen ist - bevor der Konstruktor des ersten fertig ist - wird der Nodeeigene Konstruktor des Mitglieds aufgerufen, wodurch eine weitere neue Instanz instanziiert wird ... und Sie erhalten eine endlose Pseudorekursion. Es ist nicht wirklich so viel Größe Problem in ganz streng und wörtlichen Begriffe, wie es ein Performance - Problem ist.
Panzercrisis
Aber alles, was Sie wirklich wollen, ist nur eine Möglichkeit, auf den nächsten in der Liste zu verweisen, nicht auf einen Node, der tatsächlich im ersten enthalten ist Node. Sie erstellen also einen Zeiger, mit dem Java im Gegensatz zu Grundelementen im Wesentlichen mit Objekten umgeht. Wenn Sie eine Methode aufrufen oder eine Variable erstellen, speichert Java keine Kopie des Objekts oder sogar des Objekts selbst. Es speichert einen Verweis auf ein Objekt, bei dem es sich im Wesentlichen um einen Zeiger handelt, um den ein kleiner Kinderhandschuh gewickelt ist. Dies ist, was beide Antworten im Wesentlichen sagen.
Panzercrisis
Es ist kein Größen- oder Geschwindigkeitsproblem - es ist ein Unmöglichkeitsproblem. Das enthaltene Knotenobjekt würde ein Knotenobjekt enthalten, das ein
Knotenobjekt enthalten
3
@Panzercrisis Mir ist bewusst, dass beide die gleiche Erklärung geben. Dieser Ansatz war für mich jedoch nicht so hilfreich, da er sich auf das konzentrierte, was ich bereits verstanden hatte: wie Zeiger in C ++ funktionieren und wie Zeiger in Java behandelt werden. Die akzeptierte Antwort bezog sich speziell darauf, warum die Verwendung eines Zeigers nicht möglich wäre, da die Größe nicht berechnet werden kann. Auf der anderen Seite ließ dieser es vage als "eine rekursiv definierte Struktur". PS Ihre Erklärung, die Sie gerade geschrieben haben, erklärt es besser als beide: D.
m0meni
38

C ++ ist kein Java. Wenn du schreibst

Node m_next;

In Java ist das dasselbe wie beim Schreiben

Node* m_next;

in C ++. In Java ist der Zeiger implizit, in C ++ explizit. Wenn du schreibst

Node m_next;

In C ++ platzieren Sie eine Instanz von Nodegenau dort in dem Objekt, das Sie definieren. Es ist immer da und kann nicht weggelassen werden, es kann nicht zugeordnet werden newund es kann nicht entfernt werden. Dieser Effekt ist in Java nicht zu erreichen und unterscheidet sich grundlegend von dem, was Java mit derselben Syntax macht.

cmaster - Monica wieder einsetzen
quelle
1
Um etwas Ähnliches in Java zu erhalten, wäre es wahrscheinlich "erweitert", wenn SuperNode Node erweitert. SuperNodes enthält alle Attribute von Node und muss den gesamten zusätzlichen Speicherplatz reservieren. Also in Java können Sie nicht "Node erweitert Node"
Falco
@Falco Richtig, Vererbung ist eine Form der direkten Einbeziehung der Basisklassen. Da Java jedoch (im Gegensatz zu C ++) keine Mehrfachvererbung zulässt, können Sie nur eine Instanz einer einzelnen anderen bereits vorhandenen Klasse über die Vererbung abrufen. Aus diesem Grund würde ich Vererbung nicht als Ersatz für die Einbeziehung von Mitgliedern vor Ort betrachten.
cmaster - wieder herstellen Monica
27

Sie verwenden einen Zeiger, andernfalls Ihren Code:

class Node
{
   //etc
   Node m_next; //non-pointer
};

… Würde nicht kompiliert, da der Compiler die Größe von nicht berechnen kann Node. Dies liegt daran, dass es von sich selbst abhängt. Dies bedeutet, dass der Compiler nicht entscheiden kann, wie viel Speicher er verbrauchen würde.

Nawaz
quelle
5
Schlimmer noch, es gibt keine gültige Größe: Wenn k == sizeof(Node)hält und Ihr Typ Daten hat, müsste er diese sizeof(Node) = k + sizeof(Data) = sizeof(Node) + sizeof(Data)und dann auch halten sizeof(Node) > sizeof(Node).
Bitmaske
4
@bitmask In den reellen Zahlen existiert keine gültige Größe . Wenn Sie Transinfiniten zulassen, aleph_0funktioniert. (Nur übermäßig pedantisch sein :-))
k_g
2
@k_g Nun, der C / C ++ - Standard schreibt vor, dass der Rückgabewert sizeofein vorzeichenloser Integraltyp ist, also besteht die Hoffnung auf transfinite oder sogar reelle Größen. (noch pedantischer sein !: p)
Thomas
@ Thomas: Man könnte sogar darauf hinweisen, dass es sogar die natürlichen Zahlen gibt. (Über die pedantische Spitze gehen: p)
Bitmaske
1
Tatsächlich wird Nodees nicht einmal vor dem Ende dieses Snippets definiert, sodass Sie es nicht wirklich im Inneren verwenden können. Das implizite Vorwärtsdeklarieren von Zeigern auf eine noch nicht deklarierte Klasse ist ein kleiner Betrug, den die Sprache zulässt, um solche Strukturen zu ermöglichen, ohne dass Zeiger ständig explizit umgewandelt werden müssen.
osa
13

Letzteres ( Node m_next) müsste den Knoten enthalten . Es würde nicht darauf hinweisen. Und dann würde es keine Verknüpfung von Elementen geben.

Wallyk
quelle
3
Schlimmer noch, es wäre logisch unmöglich, dass ein Objekt etwas vom gleichen Typ enthält.
Mike Seymour
Würde es technisch gesehen immer noch keine Verknüpfung geben, da es sich um einen Knoten handelt, der einen Knoten enthält, der einen Knoten enthält, und so weiter?
m0meni
9
@ AR7: Nein, Containment bedeutet, dass es sich buchstäblich im Objekt befindet und nicht damit verbunden ist.
Mike Seymour
9

Der Ansatz, den Sie beschreiben , ist kompatibel nicht nur mit C ++, sondern auch mit seiner (meist) Teilmenge Sprache C . Das Erlernen der Entwicklung einer verknüpften Liste im C-Stil ist eine gute Möglichkeit, sich mit einfachen Programmiertechniken (z. B. manueller Speicherverwaltung) vertraut zu machen, ist jedoch im Allgemeinen keine bewährte Methode für die moderne C ++ - Entwicklung.

Im Folgenden habe ich vier Varianten zum Verwalten einer Liste von Elementen in C ++ implementiert.

  1. raw_pointer_demoVerwendet den gleichen Ansatz wie Sie - manuelle Speicherverwaltung bei Verwendung von Rohzeigern erforderlich. Die Verwendung von C ++ ist hier nur für syntaktischen Zucker , und der verwendete Ansatz ist ansonsten mit der C-Sprache kompatibel.
  2. In shared_pointer_demoder Liste erfolgt die Verwaltung weiterhin manuell, die Speicherverwaltung erfolgt jedoch automatisch (verwendet keine Rohzeiger). Dies ist sehr ähnlich zu dem, was Sie wahrscheinlich mit Java erlebt haben.
  3. std_list_demoverwendet den Standardbibliothekscontainer list. Dies zeigt, wie viel einfacher es wird, wenn Sie sich auf vorhandene Bibliotheken verlassen, anstatt Ihre eigenen zu rollen.
  4. std_vector_demoverwendet den Standardbibliothekscontainer vector. Dies verwaltet den Listenspeicher in einer einzigen zusammenhängenden Speicherzuordnung. Mit anderen Worten, es gibt keine Zeiger auf einzelne Elemente. In bestimmten extremen Fällen kann dies erheblich ineffizient werden. In typischen Fällen ist dies jedoch die empfohlene Best Practice für die Listenverwaltung in C ++ .

Bemerkenswert: Von all diesen raw_pointer_demoerfordert nur das tatsächlich, dass die Liste explizit zerstört wird, um ein "Verlieren" des Speichers zu vermeiden. Die anderen drei Methoden würden die Liste und ihren Inhalt automatisch zerstören, wenn der Container den Gültigkeitsbereich verlässt (am Ende der Funktion). Der Punkt ist: C ++ kann in dieser Hinsicht sehr "Java-ähnlich" sein - aber nur, wenn Sie Ihr Programm mit den verfügbaren High-Level-Tools entwickeln.

/*BINFMTCXX: -Wall -Werror -std=c++11
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <memory>
using std::cerr;
/** Brief   Create a list, show it, then destroy it */
void raw_pointer_demo()
{
    cerr << "\n" << "raw_pointer_demo()..." << "\n";

    struct Node
    {
        Node(int data, Node *next) : data(data), next(next) {}
        int data;
        Node *next;
    };

    Node * items = 0;
    items = new Node(1,items);
    items = new Node(7,items);
    items = new Node(3,items);
    items = new Node(9,items);

    for (Node *i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr << "\n";

    // Erase the entire list
    while (items) {
        Node *temp = items;
        items = items->next;
        delete temp;
    }
}
raw_pointer_demo()...
9, 3, 7, 1
/** Brief   Create a list, show it, then destroy it */
void shared_pointer_demo()
{
    cerr << "\n" << "shared_pointer_demo()..." << "\n";

    struct Node; // Forward declaration of 'Node' required for typedef
    typedef std::shared_ptr<Node> Node_reference;

    struct Node
    {
        Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {}
        int data;
        Node_reference next;
    };

    Node_reference items = 0;
    items.reset( new Node(1,items) );
    items.reset( new Node(7,items) );
    items.reset( new Node(3,items) );
    items.reset( new Node(9,items) );

    for (Node_reference i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr<<"\n";

    // Erase the entire list
    while (items)
        items = items->next;
}
shared_pointer_demo()...
9, 3, 7, 1
/** Brief   Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
    cerr << msg;
    bool first = true;
    for ( int i : container )
        cerr << (first?" ":", ") << i, first = false;
    cerr<<"\n";
}
/** Brief  Create a list, manipulate it, then destroy it */
void std_list_demo()
{
    cerr << "\n" << "std_list_demo()..." << "\n";

    // Initial list of integers
    std::list<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find( items.begin(), items.end(), 3), 8);
    show("B: ", items);

    // Sort the list
    items.sort();
    show( "C: ", items);

    // Erase '7'
    items.erase(std::find(items.begin(), items.end(), 7));
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}
std_list_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:
/** brief  Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
    cerr << "\n" << "std_vector_demo()..." << "\n";

    // Initial list of integers
    std::vector<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find(items.begin(), items.end(), 3), 8);
    show( "B: ", items );

    // Sort the list
    sort(items.begin(), items.end());
    show("C: ", items);

    // Erase '7'
    items.erase( std::find( items.begin(), items.end(), 7 ) );
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}
std_vector_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:
int main()
{
    raw_pointer_demo();
    shared_pointer_demo();
    std_list_demo();
    std_vector_demo();
}
Brent Bradburn
quelle
Die Node_referenceobige Deklaration befasst sich mit einem der interessantesten Unterschiede auf Sprachebene zwischen Java und C ++. In Java würde beim Deklarieren eines Objekts vom Typ Nodeimplizit ein Verweis auf ein separat zugewiesenes Objekt verwendet. In C ++ haben Sie die Wahl zwischen Referenzzuweisung (Zeiger) und direkter Zuordnung (Stapelzuweisung). Daher müssen Sie die Unterscheidung explizit behandeln. In den meisten Fällen verwenden Sie die direkte Zuordnung, jedoch nicht für Listenelemente.
Brent Bradburn
Ich weiß nicht, warum ich nicht auch die Möglichkeit eines std :: deque empfohlen habe .
Brent Bradburn
8

Überblick

Es gibt zwei Möglichkeiten, Objekte in C ++ zu referenzieren und zuzuweisen, während es in Java nur eine Möglichkeit gibt.

Um dies zu erklären, zeigen die folgenden Diagramme, wie Objekte im Speicher gespeichert werden.

1.1 C ++ - Elemente ohne Zeiger

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int          Code;
    char[50]     FirstName;
    char[50]     LastName;
    // "Address" IS NOT A pointer !!!
    AddressClass Address;
};

int main(...)
{
   CustomerClass MyCustomer();
     MyCustomer.Code = 1;
     strcpy(MyCustomer.FirstName, "John");
     strcpy(MyCustomer.LastName, "Doe");
     MyCustomer.Address.Code = 2;
     strcpy(MyCustomer.Address.Street, "Blue River");
     strcpy(MyCustomer.Address.Number, "2231 A");

   return 0;
} // int main (...)

.......................................
..+---------------------------------+..
..|          AddressClass           |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: Street            |..
..| [+] char[10]: Number            |..
..| [+] char[50]: POBox             |..
..| [+] char[50]: City              |..
..| [+] char[50]: State             |..
..| [+] char[50]: Country           |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..|          CustomerClass          |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: FirstName         |..
..| [+] char[50]: LastName          |..
..+---------------------------------+..
..| [+] AddressClass: Address       |..
..| +-----------------------------+ |..
..| | [+] int:      Code          | |..
..| | [+] char[50]: Street        | |..
..| | [+] char[10]: Number        | |..
..| | [+] char[50]: POBox         | |..
..| | [+] char[50]: City          | |..
..| | [+] char[50]: State         | |..
..| | [+] char[50]: Country       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

Warnung : Die in diesem Beispiel verwendete C ++ - Syntax ähnelt der Syntax in Java. Die Speicherzuordnung ist jedoch unterschiedlich.

1.2 C ++ - Elemente mit Zeigern

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int           Code;
    char[50]      FirstName;
    char[50]      LastName;
    // "Address" IS A pointer !!!
    AddressClass* Address;
};

.......................................
..+-----------------------------+......
..|        AddressClass         +<--+..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: Street        |...|..
..| [+] char[10]: Number        |...|..
..| [+] char[50]: POBox         |...|..
..| [+] char[50]: City          |...|..
..| [+] char[50]: State         |...|..
..| [+] char[50]: Country       |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|         CustomerClass       |...|..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: FirstName     |...|..
..| [+] char[50]: LastName      |...|..
..| [+] AddressClass*: Address  +---+..
..+-----------------------------+......
.......................................

int main(...)
{
   CustomerClass* MyCustomer = new CustomerClass();
     MyCustomer->Code = 1;
     strcpy(MyCustomer->FirstName, "John");
     strcpy(MyCustomer->LastName, "Doe");

     AddressClass* MyCustomer->Address = new AddressClass();
     MyCustomer->Address->Code = 2;
     strcpy(MyCustomer->Address->Street, "Blue River");
     strcpy(MyCustomer->Address->Number, "2231 A");

     free MyCustomer->Address();
     free MyCustomer();

   return 0;
} // int main (...)

Wenn Sie den Unterschied zwischen beiden Methoden überprüfen, werden Sie feststellen, dass bei der ersten Technik das Adresselement innerhalb des Kunden zugewiesen wird, während Sie bei der zweiten Methode jede Adresse explizit erstellen müssen.

Warnung: Java weist Objekte im Speicher wie bei dieser zweiten Technik zu, aber die Syntax ist wie bei der ersten Methode, was für Neulinge in "C ++" verwirrend sein kann.

Implementierung

Ihr Listenbeispiel könnte also dem folgenden Beispiel ähneln.

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

.......................................
..+-----------------------------+......
..|            Node             |......
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................

Zusammenfassung

Da eine verknüpfte Liste eine variable Anzahl von Elementen enthält, wird der Speicher nach Bedarf und nach Verfügbarkeit zugewiesen.

AKTUALISIEREN:

Ebenfalls erwähnenswert, wie @haccks in seinem Beitrag kommentierte.

Manchmal zeigen Referenzen oder Objektzeiger verschachtelte Elemente an (auch bekannt als "UML-Komposition").

Und manchmal weisen Referenzen oder Objektzeiger auf externe Elemente hin (auch bekannt als "UML-Aggregation").

Verschachtelte Elemente derselben Klasse können jedoch nicht mit der "No-Pointer" -Technik angewendet werden.

umlcat
quelle
7

Nebenbei bemerkt, wenn das allererste Mitglied einer Klasse oder Struktur der nächste Zeiger ist (also keine virtuellen Funktionen oder andere Merkmale einer Klasse, die bedeuten würden, dass das nächste nicht das erste Mitglied einer Klasse oder Struktur ist), dann Sie kann eine "Basis" -Klasse oder -Struktur mit nur einem nächsten Zeiger verwenden und allgemeinen Code für grundlegende verknüpfte Listenoperationen wie Anhängen, Einfügen vor, Abrufen von vorne, .... verwenden. Dies liegt daran, dass C / C ++ garantiert, dass die Adresse des ersten Mitglieds einer Klasse oder Struktur mit der Adresse der Klasse oder Struktur übereinstimmt. Die Basisknotenklasse oder -struktur hätte nur einen nächsten Zeiger, der von den grundlegenden Funktionen der verknüpften Liste verwendet werden könnte, und dann würde die Typumwandlung nach Bedarf verwendet, um zwischen dem Basisknotentyp und den "abgeleiteten" Knotentypen zu konvertieren. Randnotiz - in C ++, wenn die Basisknotenklasse nur einen nächsten Zeiger hat,

rcgldr
quelle
6

Warum ist es besser, Zeiger in einer verknüpften Liste zu verwenden?

Der Grund dafür ist, dass der NodeCompiler beim Erstellen eines Objekts Speicher für dieses Objekt zuweisen muss und dafür die Größe des Objekts berechnet wird.
Die Größe des Zeigers auf einen beliebigen Typ ist dem Compiler bekannt und daher kann mit einem selbstreferenziellen Zeiger die Größe des Objekts berechnet werden.

Wenn Node m_nodestattdessen verwendet wird, hat der Compiler keine Ahnung von der Größe von Nodeund bleibt in einer unendlichen Rekursion der Berechnung stecken sizeof(Node). Denken Sie immer daran: Eine Klasse kann kein Mitglied ihres eigenen Typs enthalten .

Haccks
quelle
5

Weil dies in C ++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

entspricht dem in Java

public static void main (..)
{
    MyClass myObjectReference = new MyClass();
}

Dabei erstellen beide ein neues Objekt MyClassmit dem Standardkonstruktor.

Khaled.K
quelle
0

Warum verwenden verknüpfte Listen Zeiger, anstatt Knoten innerhalb von Knoten zu speichern?

Es gibt natürlich eine triviale Antwort.

Wenn sie nicht verknüpfen durch einen Zeiger einen Knoten zum nächsten, würden sie nicht werden Listen verknüpft .

Die Existenz von verknüpften Listen liegt daran, dass wir Objekte miteinander verketten wollen. Zum Beispiel: Wir haben bereits ein Objekt von irgendwoher. Wir möchten nun beispielsweise das eigentliche Objekt (keine Kopie) am Ende einer Warteschlange platzieren. Dies wird erreicht, indem ein Link vom letzten Element, das sich bereits in der Warteschlange befindet, zu dem Eintrag hinzugefügt wird, den wir hinzufügen. In maschineller Hinsicht bedeutet dies, ein Wort mit der Adresse des nächsten Elements zu füllen.

user13784117
quelle