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

121

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

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

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

Node *m_next;

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

Node m_next;

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

c++ pointers linked-list m0meni
источник
14
@self Простите меня? Почему бы в языке, где все является указателем, не было бы связанных списков?
Энгью больше не гордится SO
41
Важно отметить, чем C и C ++ отличаются от Java с точки зрения указателей на объекты и ссылок. Node m_nextне является ссылкой на узел, это хранилище для всего Nodeсамого себя.
Брайан Кейн,
41
@self В Java есть указатели, которые вы просто не используете явно.
m0meni
27
Полностью опущенные черепахи - не вариант. Безумие должно где-то закончиться.
WhozCraig
26
Пожалуйста, забудьте все, что вы знаете о Java. C ++ и Java принципиально по-разному обрабатывают память. Посмотрите этот вопрос, чтобы получить рекомендации по книгам, выберите одну и прочтите. Вы окажете нам всем огромную услугу.
Роб К.

Ответы:

218

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

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

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

emlai
источник
25
* Если только не оценивать лениво. Возможны бесконечные списки, только не со строгой оценкой.
Carcigenicate
55
@Carcigenicate это не об оценке / выполнении некоторой функции на объекте Node - это о структуре памяти каждого экземпляра Node, которая должна быть определена во время компиляции, прежде чем может произойти какая-либо оценка.
Петерис
6
@DavidK Это сделать по логике невозможно. Здесь вам нужен указатель (ну, на самом деле косвенный указатель) - конечно, язык может скрыть его от вас, но, в конце концов, никуда.
Voo
2
@ Дэвид Я в замешательстве. Сначала вы соглашаетесь с тем, что это логически невозможно, но потом вы хотите это созерцать? Убрать что-нибудь из C или C ++ - насколько я понимаю, это невозможно ни на одном языке, о котором вы могли когда-либо мечтать. Эта структура по определению является бесконечной рекурсией, и без некоторого уровня косвенности мы не можем ее сломать.
Voo
13
@benjamin Я на самом деле указал (потому что я знал, что иначе кто-то поднимет этот вопрос - ну, это не помогло), что Haskell выделил преобразователи во время создания, и, следовательно, это работает, потому что эти преобразователи дают нам необходимое косвенное обращение. Это не что иное, как указатель с замаскированными дополнительными данными ...
Воу,
178

В Java 

Node m_node

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

Node *m_node

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

Node m_node

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

PM100
источник
2
@SalmanA Я уже знал это. Я просто хотел знать, почему это не будет работать без указателя, что гораздо лучше объяснил принятый ответ.
m0meni
3
@ AR7 Они оба дают одно и то же объяснение, только с использованием двух разных подходов. Если вы объявили его как «обычную» переменную, то при первом вызове конструктора он создал бы его для нового экземпляра. Но до того, как он завершит создание экземпляра - до того, как будет завершен первый конструктор - Nodeбудет вызван собственный конструктор члена , который создаст другой новый экземпляр ... и вы получите бесконечную псевдорекурсию. На самом деле это не столько проблема размера, если говорить строго и буквально, сколько проблема производительности.
Panzercrisis
Но все, что вам действительно нужно, это просто способ указать на то, что будет следующим в списке, а не то, Nodeчто на самом деле находится внутри первого Node. Таким образом, вы создаете указатель, который, по сути, является тем, как Java обрабатывает объекты, а не примитивы. Когда вы вызываете метод или создаете переменную, Java не сохраняет копию объекта или даже сам объект; он хранит ссылку на объект, который по сути представляет собой указатель с обернутым вокруг него кусочком детской перчатки. Об этом, по сути, говорят оба ответа.
Panzercrisis
это не проблема размера или скорости - это проблема невозможности. Включенный объект Node будет включать объект Node, который будет включать объект Node ... Фактически, его невозможно скомпилировать
pm100
3
@Panzercrisis Я знаю, что они оба дают одно и то же объяснение. Однако этот подход не был для меня таким полезным, потому что он был сосредоточен на том, что я уже понимал: как указатели работают в C ++ и как указатели обрабатываются в Java. В принятом ответе конкретно указано, почему не использовать указатель, потому что размер не может быть рассчитан. С другой стороны, этот оставил его более расплывчатым, как «рекурсивно определенную структуру». PS ваше объяснение, которое вы только что написали, объясняет это лучше, чем оба: D.
m0meni
38

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

Node m_next;

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

Node* m_next;

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

Node m_next;

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

cmaster - восстановить монику
источник
1
Чтобы получить что-то подобное в Java, вероятно, было бы «расширять», если SuperNode расширяет Node, SuperNodes включает в себя все атрибуты узла и должен зарезервировать все дополнительное пространство. Таким образом, в Java вы не можете сделать «Node extends Node»
Falco
@Falco Верно, наследование - это форма включения базовых классов на месте. Однако, поскольку Java не допускает множественного наследования (в отличие от C ++), вы можете извлекать только экземпляр одного другого уже существующего класса через наследование. Вот почему я бы не стал думать о наследовании как о замене включения членов на месте.
cmaster - восстановить монику
27

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

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

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

Наваз
источник
5
Хуже того, не существует допустимого размера: если k == sizeof(Node)удержания и у вашего типа есть данные, он также должен будет их удерживать, sizeof(Node) = k + sizeof(Data) = sizeof(Node) + sizeof(Data)а затем sizeof(Node) > sizeof(Node).
bitmask
4
@bitmask не действительного размера не существует в действительных числах . Если разрешить трансинфиниты, aleph_0работает. (Просто излишне педантично :-))
k_g
2
@k_g Что ж, стандарт C / C ++ требует, чтобы возвращаемое значение sizeofбыло беззнаковым целым типом, поэтому есть надежда на трансфинитные или даже реальные размеры. (будучи еще более педантичным!: p)
Thomas
@Thomas: Можно даже указать, что идут даже натуральные числа. (Переходя через -педантический верх: p)
bitmask
1
Фактически, Nodeон даже не определен до конца этого фрагмента, поэтому вы не можете использовать его внутри. Разрешение неявно объявлять указатели на еще не объявленный класс - это небольшая хитрость, разрешенная языком для того, чтобы сделать такие структуры возможными, без необходимости постоянно приводить указатели явно.
osa
13

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

wallyk
источник
3
Хуже того, для объекта было бы логически невозможно содержать что-то одного и того же типа.
Майк Сеймур,
Разве технически не было бы связывания, потому что это был бы узел, содержащий узел, содержащий узел, и так далее?
m0meni
9
@ AR7: Нет, сдерживание означает, что он буквально внутри объекта, а не связан с ним.
Майк Сеймур,
9

Подход , который вы описываете совместим не только с C ++, но и с его ( в основном) языка подмножество 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();
}
Брент Брэдберн
источник
Приведенное Node_referenceвыше объявление касается одного из наиболее интересных различий на уровне языков между Java и C ++. В Java при объявлении объекта типа Nodeнеявно используется ссылка на отдельно выделенный объект. В C ++ у вас есть выбор между выделением ссылки (указатель) или прямым (стек), поэтому вы должны явно обрабатывать различие. В большинстве случаев вы будете использовать прямое размещение, но не для элементов списка.
Brent
Не знаю, почему я также не рекомендовал возможность использования std :: deque .
Брент Брэдберн
8

обзор

В C ++ есть 2 способа ссылаться на объекты и выделять их, а в 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 выделяет объекты в памяти, как этот второй метод, но синтаксис аналогичен первому способу, что может сбить с толку новичков в «C ++».

Реализация

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

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 прокомментировал свой пост.

Иногда ссылки или указатели на объекты указывают на вложенные элементы (также известные как «композиция UML»).

А иногда ссылки или указатели объектов указывают на внешние элементы (также известные как «агрегирование UML»).

Но вложенные элементы одного и того же класса не могут применяться с техникой «без указателя».

umlcat
источник
7

С другой стороны, если самый первый член класса или структуры является следующим указателем (поэтому нет виртуальных функций или любой другой функции класса, которая означала бы, что следующий не является первым членом класса или структуры), тогда вы может использовать «базовый» класс или структуру только со следующим указателем, а также использовать общий код для основных операций со связанными списками, таких как добавление, вставка перед, извлечение с начала, .... Это связано с тем, что C / C ++ гарантирует, что адрес первого члена класса или структуры совпадает с адресом класса или структуры. Класс или структура базового узла будет иметь только следующий указатель, который будет использоваться базовыми функциями связанного списка, тогда при необходимости будет использоваться приведение типов для преобразования между типом базового узла и типами «производных» узлов. Боковое примечание - в C ++, если класс базового узла имеет только следующий указатель,

rcgldr
источник
6

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

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

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

haccks
источник
5

Потому что это в C ++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

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

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

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

Khaled.K
источник
0

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

Конечно, есть банальный ответ.

Если бы они не связали один узел с другим указателем, они не были бы связанными списками .

Связанные списки существуют потому, что мы хотим объединять объекты в цепочки. Например: у нас уже откуда-то есть объект. Теперь мы хотим поместить этот фактический объект (а не копию), например, в конец очереди. Это достигается путем добавления ссылки из последнего элемента, уже находящегося в очереди, на запись, которую мы добавляем. Говоря машинным языком, это заполнение слова адресом следующего элемента.

user13784117
источник