CursorList - это версия массива связанного списка. По сути, у вас есть массив узлов списка, но вместо каждого узла, содержащего указатель на следующий элемент в связанном списке, каждый элемент узла в массиве содержит индекс для следующего элемента узла. Так, например, если бы мы хотели сохранить 5, 3, 2, 11, 9
в связанном списке, у нас было бы 5 -> 3 -> 2 -> 11 -> 9 -> NULL
. Вставка не является проблемой, так как мы просто меняем последний указатель, чтобы он указывал на вставленный узел, а для вставленного узла указываем NULL
. Удаление то же самое, мы просто перенастраиваем указатели. Однако необходимость всегда динамически выделять (используя malloc или new) память для нового узла может быть проблематичной.
Если мы должны были сохранить в CursorList, мы сначала объявляем максимальный размер массива, а затем заполняем его. Поэтому мы говорим listNode cursorList[10]
, где мы объявляем объект listNode следующим образом:
class listNode {
public:
listNode() {
data = -1;
next = NULL;
}
listNode(int inputData, &listNode inputNext) {
data = inputData;
next = inputNext;
}
private:
int data;
listNode* next;
};
поэтому после заполнения массива объектами listNode у нас будет что-то похожее на это:
Теперь, если мы хотим удалить 5, все, что нам нужно сделать, это обновить индекс next
. Итак, мы остались с этим:
Возникает вопрос, как мы узнаем, на что нужно установить индекс next
5? Что ж, вот тут и появляется Freelist (упомянутый в ответе @Justin Ethier). Freelist содержит индексы, которые все еще свободны в массиве. Таким образом, при создании CursorList, Freelist имеет 0-9. Поскольку объекты listNode назначаются элементам массива, Freelist удаляет эти индексы. Когда число удаляется (например, в примере с 5 выше), индекс добавляется обратно во Фрилист. Если мы хотим добавить число в CursorList, мы просто обновляем индексы next
для соответствующих элементов.