Неопределенное количество переменной-члена класса (C++)

Question

Программа C++, над которой я работаю, предназначена для создания настраиваемого двойного класса Linked List в C++ с использованием неопределенного числа указателей на структуру узлов с значением данных и двумя указателями внутри , Это предпосылка этой программы. Нельзя использовать класс STL LinkedList, должен сделать свой собственный.

Как говорится, как вы создаете переменную-член класса, которая не имеет определенного количества указателей на узлы? Я не хочу инициализировать пятьдесят узлов при объявлении класса, но затем использовать только десять из них. и в то же время я не хочу инициализировать только 5, а затем должен использовать больше, чем 5. Есть ли способ динамически добавлять указатели узлов в связанный класс списка в C++, когда указатели узлов считаются переменной-членом ?

Я даже об этом правильно? И если да, как я буду это делать?

Answer 1

Представьте:

+----------+-------+------+ 
| Previous | Data | Next | 
| Node  | Field | Node | 
+----------+-------+------+ 

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

Мы могли бы два из них:

+----------+-------+------+ 
| Previous | Data | Next | 
| Node  | Field | Node | 
+----------+-------+------+ 
    ^    | 
    |     V 
+----------+-------+------+ 
| Previous | Data | Next | 
| Node  | Field | Node | 
+----------+-------+------+ 

Previous Node поле 2-й точек узла к первому. У первого узла нет предшественников, поэтому это Previous Node поле пусто.

Аналогичным образом поле Next Node первого узла указывает на второй узел. Второй узел не имеет преемника, поэтому поле Next Node пустого места.

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

Edit 1: Три узла

+----------+-------+------+ 
| Previous | Data | Next | 
| Node  | Field | Node | 
+----------+-------+------+ 
    ^    | 
    |     V 
+----------+-------+------+ 
| Previous | Data | Next | 
| Node  | Field | Node | 
+----------+-------+------+ 
    ^    | 
    |     V 
+----------+-------+------+ 
| Previous | Data | Next | 
| Node  | Field | Node | 
+----------+-------+------+ 

Как вы можете видеть, посетить (траверс) узлы в вперед образом, вы будете следовать поле ссылки одного узла, чтобы добраться до следующего узел. Аналогично, чтобы перейти в назад, вы следуете ссылке Previous Node, чтобы перейти к предшественнику узла.

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

Edit 2: Контейнер класса
Связанный список является контейнер из узлов. Для простых реализаций класс Container не должен быть узлом.

Контейнер имеет, а указателя на первый узел и, необязательно, указатель на последний узел:

+------+-------+ 
| Last | First | 
| Node | Node | 
+------+-------+ 
    |  | 
    |  +---------------+ 
    |      | 
    |      V 
    | +----------+-------+------+ 
    | | Previous | Data | Next | 
    | | Node  | Field | Node | 
    | +----------+-------+------+ 
    | ^    | 
    |  |     V 
    | +----------+-------+------+ 
    | | Previous | Data | Next | 
    | | Node  | Field | Node | 
    | +----------+-------+------+ 
    | ^    | 
    |  |     V 
    | +----------+-------+------+ 
    | | Previous | Data | Next | 
    +->| Node  | Field | Node | 
    +----------+-------+------+ 

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

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