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

Question

В этом вопросе статический связанный список определяется следующим образом: (код c ++)

template<typename T> struct Node{
    T elem;
    int next;//yes, int, which points to the index of the next element in the array.
};
Node static_linked_list [SOME_SIZE];
//some initialization code omitted.

Таким образом, в этом типе связанного списка он является статическим, поскольку его размер выделяется во время инициализации массива.Ссылка достигается через поле int next, которое указывает на индекс следующего элемента.

В чем преимущества этой структуры данных по сравнению со списком ссылок на основе указателей (или ссылок)?Каково его применение?Насколько я знаю, статический имеет время жизни, и может использоваться при реализации malloc.Но его int next, похоже, не потребляет меньше памяти, чем указатели.

Answer 1

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

Быстрее "удалить" элемент, чем если бы это был простой массив (который потребовал бы смещения более поздних элементов).Добавление элементов более сложное и, очевидно, ограничено размером всего массива элементов, но может быть ускорено при некотором внимательном учете.Я не уверен, при каких именно обстоятельствах вы бы решили, что вам нужна именно эта структура данных в другом виде списка.Я предполагаю, что вы были бы в довольно осторожных ограничениях памяти, где предсказуемость была главной: например, игровые приставки, встроенные устройства, драйверы / уровни операционной системы и т. Д.