Dlaczego listy połączone używają wskaźników zamiast przechowywania węzłów wewnątrz węzłów

121

Wcześniej intensywnie pracowałem z listami połączonymi w Javie, ale jestem bardzo nowy w C ++. Używałem tej klasy węzła, która została mi przekazana w projekcie

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

ale miałem jedno pytanie, na które nie udzielono zbyt dobrej odpowiedzi. Dlaczego konieczne jest użycie

Node *m_next;

wskazywać na następny węzeł na liście zamiast

Node m_next;

Rozumiem, że lepiej jest użyć wersji wskaźnikowej; Nie będę dyskutować o faktach, ale nie wiem, dlaczego jest lepiej. Otrzymałem niezbyt jasną odpowiedź na temat tego, w jaki sposób wskaźnik jest lepszy do alokacji pamięci i zastanawiałem się, czy ktoś tutaj mógłby mi pomóc lepiej to zrozumieć.

c++ pointers linked-list m0meni
źródło
14
@ self Pardon me? Dlaczego język, w którym wszystko jest wskaźnikiem, nie miałby mieć połączonych list?
Angew nie jest już dumny z SO
41
Należy zauważyć, że C i C ++ różnią się od Javy pod względem wskaźników obiektów i referencji. Node m_nextnie jest odniesieniem do węzła, jest magazynem dla całego Nodesiebie.
Brian Cain
41
@self Java ma wskaźniki, których po prostu nie używasz.
m0meni
27
Żółwie aż do końca to nie wchodzi w grę. Szaleństwo musi się gdzieś skończyć.
WhozCraig
26
Zapomnij o wszystkim, co wiesz o Javie. C ++ i Java obsługują pamięć na zasadniczo różne sposoby. Przejdź do tego pytania, aby uzyskać rekomendacje dotyczące książek, wybierz jedno i przeczytaj je. Zrobisz nam wszystkim wielką przysługę.
Rob K

Odpowiedzi:

218

To nie tylko lepsze, to jedyny możliwy sposób.

Co by było, gdybyś przechowywał w sobie jakiś Node przedmiotsizeof(Node) ? Byłoby sizeof(int) + sizeof(Node), co byłoby równe sizeof(int) + (sizeof(int) + sizeof(Node)), które byłoby równe sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))itd. Nieskończoności.

Taki obiekt nie może istnieć. To niemożliwe .

emlai
źródło
25
* Chyba że jest oceniany leniwie. Możliwe są nieskończone listy, ale nie przy ścisłej ocenie.
Carcigenicate
55
@Carcigenicate nie chodzi o ocenę / wykonanie jakiejś funkcji na obiekcie Node - chodzi o układ pamięci każdej instancji Node, który musi zostać określony w czasie kompilacji, zanim nastąpi jakakolwiek ocena.
Peteris,
6
@DavidK Jest to logicznie niemożliwe do zrobienia. Ty potrzebować wskaźnik (no naprawdę zadnie) tutaj - upewnić się, że język może ukryć przed tobą, ale w końcu, że nie odwrotnie.
Voo
2
@David Jestem zdezorientowany. Najpierw zgadzasz się, że jest to logicznie niemożliwe, ale potem chcesz to kontemplować? Usuń cokolwiek z C lub C ++ - nie jest to możliwe w żadnym języku, jaki kiedykolwiek wymyśliłeś, o ile widzę. Ta struktura jest z definicji nieskończoną rekurencją i bez pewnego poziomu pośrednictwa nie możemy tego przerwać.
Voo,
13
@benjamin Właściwie zwróciłem uwagę (ponieważ wiedziałem, że w przeciwnym razie ktoś by to poruszył - cóż, nie pomogło), że Haskell przydzielił zwroty w czasie tworzenia i dlatego to działa, ponieważ te pliki dają nam pośredni kierunek, którego potrzebujemy. To nic innego jak wskaźnik z dodatkowymi danymi w przebraniu ...
Voo
178

W Javie 

Node m_node

przechowuje wskaźnik do innego węzła. Nie masz co do tego wyboru. W C ++

Node *m_node

oznacza to samo. Różnica polega na tym, że w C ++ można faktycznie przechowywać obiekt, a nie wskaźnik do niego. Dlatego musisz powiedzieć, że chcesz mieć wskaźnik. W C ++:

Node m_node

oznacza przechowywanie węzła tutaj (i to wyraźnie nie może działać dla listy - kończy się rekurencyjnie zdefiniowaną strukturą).

pm100
źródło
2
@SalmanA Już to wiedziałem. Chciałem tylko wiedzieć, dlaczego nie zadziałaby bez wskaźnika, co znacznie lepiej wyjaśnia przyjęta odpowiedź.
m0meni
3
@ AR7 Obaj podają to samo wyjaśnienie, tylko pod dwoma różnymi podejściami. Jeśli zadeklarowałeś ją jako „zwykłą” zmienną, to przy pierwszym wywołaniu konstruktora utworzyłby to w nowej instancji. Ale zanim zakończy tworzenie instancji - zanim pierwszy konstruktor zostanie zakończony - Nodezostanie wywołany własny konstruktor członka , który utworzy instancję kolejnej nowej instancji ... i otrzymasz nieskończoną pseudorekurencję. Nie jest to tak bardzo kwestia rozmiaru w całkowicie ścisłych i dosłownych kategoriach, jak kwestia wydajności.
Panzercrisis
Ale wszystko, czego tak naprawdę chcesz, to po prostu sposób wskazania następnego na liście, a nie Nodetego, który faktycznie znajduje się wewnątrz pierwszego Node. Tworzysz więc wskaźnik, który zasadniczo jest sposobem, w jaki Java obsługuje obiekty, w przeciwieństwie do prymitywów. Kiedy wywołujesz metodę lub tworzysz zmienną, Java nie przechowuje kopii obiektu ani nawet samego obiektu; przechowuje odniesienie do obiektu, który jest zasadniczo wskaźnikiem z owiniętą wokół niego odrobiną dziecięcej rękawiczki. Oto, co zasadniczo mówią obie odpowiedzi.
Panzercrisis
to nie jest problem z rozmiarem ani szybkością - jest to problem niemożliwości. Dołączony obiekt Node zawierałby obiekt Node, który zawierałby obiekt Node ... W rzeczywistości nie można go skompilować
pm100
3
@Panzercrisis Zdaję sobie sprawę, że obaj podają to samo wyjaśnienie. To podejście nie było jednak dla mnie tak pomocne, ponieważ skupiało się na tym, co już zrozumiałem: jak działają wskaźniki w C ++ i jak obsługiwane są wskaźniki w Javie. Zaakceptowana odpowiedź dotyczyła konkretnie tego, dlaczego nie użycie wskaźnika byłoby niemożliwe, ponieważ nie można obliczyć rozmiaru. Z drugiej strony, ta pozostawiła go bardziej niejasno jako „rekurencyjnie zdefiniowaną strukturę”. PS Twoje wyjaśnienie, które właśnie napisałeś, wyjaśnia to lepiej niż jedno i drugie: D.
m0meni
38

C ++ to nie Java. Kiedy piszesz

Node m_next;

w Javie to to samo, co pisanie

Node* m_next;

w C ++. W Javie wskaźnik jest niejawny, w C ++ jest jawny. Jeśli piszesz

Node m_next;

w C ++ umieszczasz instancję Nodebezpośrednio wewnątrz definiowanego obiektu. Jest zawsze obecny i nie można go pominąć, nie można go przypisać newi nie można go usunąć. Ten efekt jest niemożliwy do osiągnięcia w Javie i jest zupełnie inny niż to, co robi Java z tą samą składnią.

cmaster - przywróć monikę
źródło
1
Uzyskanie czegoś podobnego w Javie byłoby prawdopodobnie „rozszerzone”, gdyby SuperNode rozszerzył węzeł, SuperNodes zawiera wszystkie atrybuty węzła i musi zarezerwować całe dodatkowe miejsce. Tak więc w Javie nie można zrobić „Węzeł rozszerza węzeł”
Falco,
@Falco Prawda, dziedziczenie jest formą lokalnego uwzględniania klas bazowych. Ponieważ jednak Java nie zezwala na wielokrotne dziedziczenie (w przeciwieństwie do C ++), przez dziedziczenie można pobierać tylko wystąpienie jednej innej istniejącej wcześniej klasy. Dlatego nie myślałbym o dziedziczeniu jako substytutie włączenia członków na miejscu.
cmaster
27

Używasz wskaźnika, w przeciwnym razie twój kod:

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

… Nie może się skompilować, ponieważ kompilator nie może obliczyć rozmiaru Node. Dzieje się tak, ponieważ zależy to od siebie - co oznacza, że ​​kompilator nie może zdecydować, ile pamięci zajmie.

Nawaz
źródło
5
Co gorsza, nie istnieje prawidłowy rozmiar: jeśli k == sizeof(Node)blokady, a Twój typ zawiera dane, musiałby również przechowywać ten sizeof(Node) = k + sizeof(Data) = sizeof(Node) + sizeof(Data)i wtedy sizeof(Node) > sizeof(Node).
maska ​​bitów
4
@bitmask nie ma prawidłowego rozmiaru w liczbach rzeczywistych . Jeśli pozwolisz na transinfinites, aleph_0działa. (Po prostu zbyt pedantyczny :-))
k_g
2
@k_g Cóż, standard C / C ++ wymaga, aby zwracana wartość sizeofbyła typem całkowitym bez znaku, więc istnieje nadzieja na rozmiary nieskończone, a nawet rzeczywiste. (będąc jeszcze bardziej pedantycznym!: p)
Thomas
@ Thomas: Można nawet wskazać, że istnieją nawet liczby naturalne. (Przechodząc przez -edantycki szczyt: p)
bitów
1
W rzeczywistości Nodenie jest nawet zdefiniowany przed końcem tego fragmentu, więc tak naprawdę nie można go używać w środku. Zezwolenie na niejawne deklarowanie w przód wskaźników do jeszcze niezadeklarowanej klasy jest małym oszustwem, na które pozwala język, aby umożliwić takie struktury, bez konieczności jawnego rzutowania wskaźników przez cały czas.
osa
13

Ta ostatnia ( Node m_next) musiałaby zawierać węzeł. To by na to nie wskazywało. I nie byłoby wtedy łączenia elementów.

wallyk
źródło
3
Co gorsza, byłoby logicznie niemożliwe, aby obiekt zawierał coś tego samego typu.
Mike Seymour
Czy technicznie nie byłoby jeszcze łączenia, ponieważ byłby to węzeł zawierający węzeł zawierający węzeł i tak dalej?
m0meni
9
@ AR7: Nie, zawieranie oznacza, że ​​jest dosłownie wewnątrz obiektu, a nie jest z nim połączone.
Mike Seymour
9

Podejście, które można opisać jest kompatybilny nie tylko z C ++, ale także z jego (w większości) języka podzbiór C . Nauka tworzenia listy połączonej w stylu C jest dobrym sposobem na zapoznanie się z technikami programowania niskiego poziomu (takimi jak ręczne zarządzanie pamięcią), ale generalnie nie jest to najlepsza praktyka w przypadku nowoczesnego programowania w języku C ++.

Poniżej zaimplementowałem cztery warianty zarządzania listą elementów w C ++.

  1. raw_pointer_demostosuje takie samo podejście jak Twoje - ręczne zarządzanie pamięcią wymagane przy użyciu surowych wskaźników. Użycie C ++ jest tutaj tylko dla cukru syntaktycznego , a zastosowane podejście jest poza tym zgodne z językiem C.
  2. Na shared_pointer_demoliście zarządzanie nadal odbywa się ręcznie, ale zarządzanie pamięcią jest automatyczne (nie używa surowych wskaźników). Jest to bardzo podobne do tego, czego prawdopodobnie doświadczyłeś z Javą.
  3. std_list_demoużywa listkontenera biblioteki standardowej . To pokazuje, o ile łatwiejsze staje się to, jeśli polegasz na istniejących bibliotekach zamiast zmieniać własne.
  4. std_vector_demoużywa vectorkontenera biblioteki standardowej . To zarządza przechowywaniem listy w jednej ciągłej alokacji pamięci. Innymi słowy, nie ma wskaźników do poszczególnych elementów. W niektórych, raczej skrajnych przypadkach, może to stać się znacznie nieefektywne. Jednak w typowych przypadkach jest to zalecana najlepsza praktyka zarządzania listami w C ++ .

Uwaga: ze wszystkich z nich, tylko raw_pointer_demofaktycznie wymaga, aby lista została jawnie zniszczona, aby uniknąć „wycieku” pamięci. Pozostałe trzy metody automatycznie niszczą listę i jej zawartość, gdy kontener znajdzie się poza zakresem (na zakończenie funkcji). Chodzi o to, że: C ++ może być pod tym względem bardzo podobny do języka Java - ale tylko wtedy, gdy zdecydujesz się rozwijać swój program przy użyciu dostępnych narzędzi wysokiego poziomu.

/*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
źródło
Powyższa Node_referencedeklaracja odnosi się do jednej z najbardziej interesujących różnic na poziomie języka między Javą a C ++. W Javie zadeklarowanie obiektu typu Nodespowodowałoby niejawne użycie odwołania do oddzielnie przydzielonego obiektu. W C ++ masz wybór między odniesieniem (wskaźnikiem) a bezpośrednim (stosem) przydziałem - więc musisz jawnie obsłużyć rozróżnienie. W większości przypadków użyjesz bezpośredniego przydziału, chociaż nie dla elementów listy.
Brent Bradburn,
Nie wiem, dlaczego nie poleciłem również możliwości std :: deque .
Brent Bradburn
8

Przegląd

Istnieją 2 sposoby odwoływania się i przydzielania obiektów w C ++, podczas gdy w Javie jest tylko jeden.

Aby to wyjaśnić, poniższe diagramy pokazują, jak obiekty są przechowywane w pamięci.

1.1 Elementy C ++ bez wskaźników

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       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

Ostrzeżenie : składnia języka C ++ używana w tym przykładzie jest podobna do składni języka Java. Ale alokacja pamięci jest inna.

1.2 Elementy C ++ używające wskaźników

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 (...)

Jeśli sprawdzisz różnicę między tymi dwoma sposobami, zobaczysz, że w pierwszej technice pozycja adresu jest przypisana do klienta, podczas gdy w drugiej musisz jawnie utworzyć każdy adres.

Ostrzeżenie: Java alokuje obiekty w pamięci jak ta druga technika, ale składnia jest podobna do pierwszej, co może być mylące dla nowicjuszy w C ++.

Realizacja

Twoja przykładowa lista może być podobna do poniższego przykładu.

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].
.......................................

Podsumowanie

Ponieważ lista połączona ma zmienną liczbę elementów, pamięć jest przydzielana w miarę potrzeb i w miarę dostępności.

AKTUALIZACJA:

Warto również wspomnieć, jak skomentował @haccks w swoim poście.

Czasami odniesienia lub wskaźniki do obiektów wskazują elementy zagnieżdżone (znane też jako „Kompozycja UML”).

Czasami odwołania lub wskaźniki obiektów wskazują elementy zewnętrzne (inaczej „Agregacja UML”).

Jednak zagnieżdżonych elementów tej samej klasy nie można zastosować przy użyciu techniki „bez wskaźnika”.

umlcat
źródło
7

Na marginesie, jeśli pierwszy element członkowski klasy lub struktury jest następnym wskaźnikiem (więc żadne funkcje wirtualne ani żadna inna cecha klasy, która oznaczałaby, że next nie jest pierwszym członkiem klasy lub struktury), to może używać "bazowej" klasy lub struktury z tylko następnym wskaźnikiem i używać wspólnego kodu do podstawowych połączonych operacji na listach, takich jak dołączanie, wstawianie przed, pobieranie z przodu, ... Dzieje się tak, ponieważ C / C ++ gwarantuje, że adres pierwszego elementu członkowskiego klasy lub struktury jest taki sam, jak adres klasy lub struktury. Klasa lub struktura węzła bazowego miałaby tylko następny wskaźnik do użycia przez podstawowe funkcje listy połączonej, a następnie w razie potrzeby do konwersji między typem węzła podstawowego a „pochodnymi” typami węzłów zostanie użyte rzutowanie typów. Nota boczna - w C ++, jeśli klasa węzła bazowego ma tylko następny wskaźnik,

rcgldr
źródło
6

Dlaczego lepiej jest używać wskaźników na połączonej liście?

Powodem jest to, że kiedy tworzysz Nodeobiekt, kompilator musi przydzielić pamięć dla tego obiektu i w tym celu obliczany jest rozmiar obiektu.
Kompilator zna rozmiar wskaźnika do dowolnego typu dlatego można obliczyć rozmiar wskaźnika obiektu za pomocą wskaźnika odwołującego się do siebie.

Jeśli Node m_nodejest używane zamiast tego, kompilator nie ma pojęcia o rozmiarze Nodei utknie w nieskończonej rekurencji obliczeń sizeof(Node). Zawsze pamiętaj: klasa nie może zawierać elementu członkowskiego własnego typu .

haccks
źródło
5

Ponieważ to w C ++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

jest odpowiednikiem tego w Javie

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

gdzie obaj tworzą nowy obiekt MyClassprzy użyciu domyślnego konstruktora.

Khaled.K
źródło
0

Dlaczego listy połączone używają wskaźników zamiast przechowywania węzłów wewnątrz węzłów?

Jest oczywiście banalna odpowiedź.

Jeśli oni nie odwołują jednego węzła do drugiego przez wskaźnik, nie byłby powiązany list .

Istnienie połączonych list jest rzeczą, ponieważ chcemy mieć możliwość łączenia obiektów w łańcuchy. Na przykład: skądś już mamy obiekt. Teraz chcemy na przykład umieścić ten rzeczywisty obiekt (nie kopię) na końcu kolejki. Osiąga się to poprzez dodanie linku z ostatniego elementu już w kolejce do wpisu, który dodajemy. W kategoriach maszynowych jest to wypełnienie słowa z adresem następnego elementu.

user13784117
źródło