Почему связанные списки используют указатели вместо хранения узлов внутри узлов

Я работал со связанными списками раньше широко в Java, но я очень новичок в C++. Я использовал этот класс узла, который был дан мне в проекте просто отлично

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

но у меня был один вопрос, на который не очень хорошо ответили. Почему необходимо использовать

Node *m_next;

чтобы он указывал на следующий узел в списке вместо

Node m_next;

Я понимаю, что лучше использовать версию указателя; я не буду спорить с фактами, но я не знаю, почему это так лучше. Я получил не очень ясный ответ о том, как указатель лучше подходит для выделения памяти, и мне было интересно, может ли кто-нибудь здесь помочь мне понять это лучше.

10 114
c++ pointers linked-list

10 ответов:

Это не просто лучше, это единственный возможный путь.

если вы сохранили Nodeобъект внутри себя, что бы sizeof(Node) быть? Это было бы sizeof(int) + sizeof(Node), что было бы равно sizeof(int) + (sizeof(int) + sizeof(Node)), что было бы равно sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node))) и т. д. до бесконечности.

такой объект не может существовать. Это невозможно.

216

В Java 

Node m_node

хранит указатель на другой узел. У тебя нет выбора. В C++ 

Node *m_node

означает то же самое. Разница в том, что в C++ вы можете хранить объект, а не указатель на него. Вот почему вы должны сказать, что хотите указатель. В C++:

Node m_node

- означает сохранить узел прямо здесь (и что явно не может работать для списка - вы в конечном итоге с рекурсивно определенной структурой).

175

C++ - это не Java. Когда вы пишете

Node m_next;

в Java это то же самое, что писать

Node* m_next;

в C++. В Java указатель является неявным, в C++ он является явным. Если вы пишете

Node m_next;

в C++ вы ставите экземпляр Node прямо там, внутри объекта, который вы определяете. Он всегда есть и не может быть опущен, он не может быть выделен с new и он не может быть удален. Такого эффекта невозможно достичь в Java, и это полностью отличается от того, что Java делает с тем же синтаксисом.

38

вы используете указатель, иначе ваш код:

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

будет...не компиляции, поскольку компилятор не может вычислить размер Node. Это связано с тем, что он зависит от самого себя - что означает, что компилятор не может решить, сколько памяти он будет потреблять.

27

последние (Node m_next) будет содержат узел. Это не будет указывать на него. И тогда не было бы никакой связи элементов.

13

описываемый вами подход совместим не только с C++, но и с его (в основном) язык подмножеств C. Обучение разработке связанного списка в стиле C-это хороший способ познакомиться с низкоуровневыми методами программирования (такими как ручное управление памятью), но обычно это не лучшая практика для современной разработки C++.

ниже я реализовал четыре варианта того, как управлять списком элементов в С.++

  1. raw_pointer_demo использует тот же подход, что и ваш -- ручное управление памятью требуется с использованием необработанных указателей. Использование C++ здесь только для синтаксический сахар, и используемый подход в противном случае совместим с языком C.
  2. на shared_pointer_demo управление списком по-прежнему выполняется вручную, но управление памятью автоматическая (не использовать сырые указатели). Это очень похоже на то, что у вас есть вероятно, опыт работы с Java.
  3. std_list_demo использует стандартную библиотеку list контейнер. Это показывает, насколько проще все становится, если вы полагаетесь на существующие библиотеки, а не на свои собственные.
  4. std_vector_demo использует стандартную библиотеку vector контейнер. Это управляет хранением списка в одном непрерывном выделении памяти. Другими словами, нет указателей на отдельные элементы. Для некоторых довольно экстремальных случаев, это может становятся значительно неэффективными. Для типичных случаев, однако,это рекомендуемая передовая практика для управления списком в C++.

примечание: из всех этих, только raw_pointer_demo на самом деле требуется, чтобы список был явно уничтожен, чтобы избежать "утечки" памяти. Остальные три метода будут автоматически уничтожить список и его содержимое, когда контейнер выходит из области видимости (в конце функции). Дело в том,: C++ способен быть очень "Java-подобным" в этом отношении, но только если вы решите разработать свою программу с использованием инструментов высокого уровня, имеющихся в вашем распоряжении.

/*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();
}
9

обзор

есть 2 способа ссылаться и выделять объекты в C++, в то время как в Java есть только один способ.

чтобы объяснить это, на следующих диаграммах показано, как объекты хранятся в памяти.

1.1 на C++ без указателей

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

предупреждение: синтаксис C++, используемый в этом примере, похож на синтаксис в Java. Но, выделение памяти отличающийся.

1.2 C++ элементы с помощью указателей

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

Если вы проверите разницу между обоими способами, вы увидите, что в первом методе адресный элемент выделяется внутри клиента, в то время как второй способ, вы должны создать каждый адрес явно.

предупреждение: Java выделяет объекты в памяти, как этот второй метод, но синтаксис похож на первый способ, который может сбить с толку новичков "С."++

реализация

таким образом, ваш пример списка может быть чем-то похожим на следующий пример.

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

резюме

поскольку связанный список имеет переменное количество элементов, память выделяется по мере необходимости и, как доступно.

обновление:

также стоит упомянуть, как прокомментировал @haccks в своем посте.

что иногда, ссылки или указатели на объекты, указывают вложенные элементы (а.к.а. "У. М. Л. Композиция").

а иногда, ссылки или указатели на объекты, указывает на внешние элементы (a.k.a. "U. M. L. Aggregation").

но вложенные элементы того же класса не могут быть применены с помощью метода "без указателя".

8

на стороне обратите внимание, если самый первый член класса или структуры является следующим указателем (так что никакие виртуальные функции или любая другая функция класса, которая означала бы, что next не является первым членом класса или структуры), то вы можете использовать "базовый" класс или структуру только со следующим указателем и использовать общий код для основных операций связанного списка, таких как append, insert before, retrieve from front,... . Это связано с тем, что C / C++ гарантирует, что адрес первого члена класса или структуры является же класса или структуры. Базовый класс узла или структура будет иметь только следующий указатель, который будет использоваться основными функциями связанного списка, а затем типизация будет использоваться по мере необходимости для преобразования между базовым типом узла и "производными" типами узлов. Примечание-в C++, если класс базового узла имеет только следующий указатель, то я предполагаю, что производные классы не могут иметь виртуальные функции.

7

почему лучше использовать указатели в связанном списке?

причина в том, что при создании Node объект, компилятор должен выделить память для этого объекта и для этого вычисляется размер объекта.
размер указателя на любой тип известен компилятору и поэтому с помощью собственного ссылочного указателя можно вычислить размер объекта.

если Node m_node используется вместо этого компилятор понятия не имеет о размере Node и он застрял в бесконечная рекурсия из расчета sizeof(Node). Всегда помните: класс не может содержать членов его собственного типа.

6

потому что это C++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

эквивалентно этому в Java

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

где оба они создают новый объект MyClass С помощью конструктора по умолчанию.

5