Почему вы не можете создать связанные списки без создания узлов в качестве указателей?

Question

В * 1001 есть ответ * Создание связанного списка без объявления узла в качестве указателя . Но я хотел знать, были ли какие-то другие причины, по которым вы не можете создавать узлы в качестве указателей, просто чтобы прояснить ситуацию.

Одна из причин заключается в том, что область действия новых узлов выйдет за пределы функции ie. Нет ли способа решить эту проблему? И есть ли другие причины?

Answer 1

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

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

Еще одна распространенная и часто полезная опция - это создание связанных списков или деревьев, в которых нет указателей на все (даже не внутри узлов), используя вместо этого цифры_1007 * индексы в массиве. Например,

struct Tree {
    struct Node {
        double value;
        int left, right; // Index of left/right child, -1 if missing
    };
    int root = -1;
    std::vector<Node> nodes;
};

Answer 2

A связанный список буквально определяется как структура, в которой объекты указывают друг на друга:

В информатике, связанный list - это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий.

В C ++ объект может указывать на другой объект с помощью указателя или ссылки.

Ссылка возможна но неудобно, поскольку он должен быть установлен при создании объекта и не может быть изменен.

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

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

Answer 3

Почему вы не можете создавать связанные списки, не создавая узлы в качестве указателей?

Вы можете, но вам определенно нужна какая-то косвенная косвенность.

Почему указатели, обычно используемые для реализации связанных списков? Как уже упоминалось в своем ответе @ 6502, вы можете добиться того же с помощью массивов или любого другого контейнера, который вы храните как страницу / память списка. Но ради аргумента давайте сравним List, реализованный указателями, и один из которых сохраняет узел как член. Основной ответ: легче реализовать функциональность списка. Преимущество списков состоит в том, что вы можете легко перемещать / выдвигать вперед и назад и очень быстро удалять элементы. Как осуществляется удаление в списке? Вы просто меняете указатель, который указывает на «подлежащий удалению объект», на следующий узел (или в случае массива вы назначаете другой индекс). Но если ваш «подлежащий удалению объект» содержит другой объект как реальный объект, а не через указатель, вам придется move отложить его перед удалением, иначе он и остальная часть списка исчезнут.

Также вы можете реализовать только односвязный список, потому что только один узел может содержать другой. Если Node A имеет NodeB, то NodeB также не может иметь NodeA. Но с указателями NodeB может без проблем указывать на NodeA и наоборот.

TL; DR Если вы используете указатели или массивы, ваши действия со списком, такие как удаление, нажатие и т. Д., Просто переключают указатели или индексы. Если ваши узлы содержат данные, вы должны обновить их путем перемещения / копирования. И это громоздко для реализации и намного сложнее, чем перенаправление указатель / ссылка.

Answer 4

Если у вас есть связанный список в общей памяти или в отражающей памяти, то мир указателей не существует. Вы вернулись в 1970-е годы, используя индексы массивов вместо указателей.

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

Answer 5

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

Node* current;
while (current != nullptr) {
    // Do something
    current = current->next;
}

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