Предисловие
Связанные списки – хорошая вещь, но не всегда усилия, затрачиваемые на их создание, оправдывают результат. Поиски по спискам, а так же удаление их элементов – операции гораздо более медленные, чем аналогичные с использованием массивов. Тем более что иногда массивы занимают меньше места в памяти, чем связанные списки, даже если последние состоят из небольшого числа элементов.
Массивы
Что такое массивы, я думаю, знают все. Они состоят из линейно выделенного участка памяти того или иного размера. Их недостатком является то, что размер массивов – постоянная величина.
Если массив полон, то всё что Вы сможете сделать для добавления новых элементов – это создать новый, ещё больший массив. Затем скопировать туда все данные и освободить память, которую занимал старый. Можно, конечно, создать массив такого размера, чтобы туда с лихвой поместились все данные, но это нерационально, если вдруг там придётся хранить лишь несколько элементов. Взгляните на изображение – 8 элементов уже заняты, а ещё 4 свободны.
Чтобы вставить элементы в середину массива, придется сдвинуть последнюю половину на число вставленных байт. Так что массивы практично использовать тогда, когда добавление/удаление будет проходить с последними элементами. Зато к любому элементу массива можно получать доступ напрямую, не перебирая остальные, а так же удобно сохранять их на диск или считывать.
Связанные списки
Связанные списки состоят из узлов, каждый из которых содержит данные и указатель на следующий узел. Конец списка отмечен пустым указателем. Смотрите на изображение ниже:
Вставка новых узлов в список очень проста – нужно всего лишь изменить два указателя. К примеру, чтобы вставить узел В между узлами А и С необходимо установить указатель узла В на адрес С, а указатель узла А на адрес В. Всё просто. Но вот поиск по списку несколько медленнее, так как приходится искать по всем узлам последовательно.
Подсчет памяти
Для хранения указателей необходима память. По сегодняшним меркам – 4 байта на каждый указатель. Поскольку большинство игровых карт всегда будет содержать как минимум одну клетку, то значит нужно 8 байт для единственного указателя. Или, другими словами: для хранения 9 уровней в массиве требуется гораздо меньше памяти, чем для одного, хранящегося с помощью списка (указатель - 8 байт, данные – 1 байт). Если Вам нужно хранить больше чем 256 клеток на карте, то, возможно, запомнить 5 уровней, поскольку 8 байт под указатели остаются, плюс 1 слово под данные = 5 слов всего под данные. Я полагаю, что средняя карта содержит, по крайней мере, 2 клетки на каждую позицию, что даёт 12 байт для указателей и 2 (или 4) байта для данных = 14 (16) байт. Это позволит сохранить уровни по 14 клеток по 1 байту данных, или 8 уровней по 2 байта данных на клетку. И этого более чем достаточно даже для самых сложных игр.
В заключение
Поймите меня правильно: связанные списки – прекрасная вещь, но не для того, чтобы сохранять в них карты. Их имеет смысл использовать чтобы, к примеру, хранить активные спрайты или описывать структуру меню. Но, еще раз повторюсь, по моему мнению, нет смысла применять для хранения карт.
Верстка и поддержка: Lennart Steinke