Массивная реализация двусвязного списка

Question

Мне нужен способ реализовать двусвязный список, используя только массив и без указателей на C. В Томасе Кормене есть упоминание об этом, но я не могу придумать, как на самом деле реализовать его.

Answer 1

Вместо использования указателей, которые в C обычно являются числами, которые индексируют в адресном пространстве, используйте целочисленные индексы в вашем массиве в качестве ссылок на предыдущие и следующие члены, например,

struct Element 
{
    int next;
    int prev;
    // Any data you want for this element in the list 
};

struct Element array[MAX_ELEMENTS];

Тогда для элементапри индексе i в массиве следующий элемент в списке -

array[array[i].next]

, а предыдущий элемент -

array[array[i].prev]

Вместо использования NULL для обозначения нулевого указателяиспользуйте -1 для обозначения «нулевого» индекса.