Почему связанные списки быстрее массивов?

Я очень озадачен этим. Везде написано «связные списки быстрее массивов», но никто не пытается сказать ПОЧЕМУ. Используя простую логику, я не могу понять, как связанный список может быть быстрее. В массиве все ячейки находятся рядом друг с другом, поэтому, если вы знаете размер каждой ячейки, легко достичь одной ячейки мгновенно. Например, если есть список из 10 целых чисел, и я хочу получить значение в четвертой ячейке, я просто перехожу непосредственно к началу массива + 24 байта и читаю оттуда 8 байтов.

С другой стороны, если у вас есть связанный список и вы хотите, чтобы элемент занял четвертое место, вам нужно начать с начала или с конца списка (в зависимости от того, одинарный или двойной список) и перейти от одного узла к другому, пока не найдете то, что ищете.

Так как же, черт возьми, шаг за шагом идти быстрее, чем переход непосредственно к элементу?

11
задан ckittel 26 August 2011 в 17:26
поделиться