Другие части: массивы, итераторы, множества, ассоциативные массивы, деревья
После того, как изучены массивы, про списки особо сказать и нечего: это упорядоченные... ну да, списки элементов. Если мы посмотрим на массивы, то увидим, что это тоже упорядоченные списки элементов. В чём тогда разница между списком и массивом?
Строго говоря, в классическом массиве нельзя удалять или добавлять элементы, особенно если добавление/удаление происходит где-то в середине массива. А вот в списке – как раз можно. Но массивы-коллекции позволяют и удалять, и добавлять элементы в любой позиции. То есть они ничем не отличаются от списков, а списки от них.
Однако как внутренняя, так и внешняя реализация списков может существенно отличаться от массивов. И один из вариантов – это связный список (Linked List).
В связном списке между элементами существует связь: каждый элемент связан со следующим элементом.
Реализуется это так: каждый элемент связного списка хранится вместе с дополнительной информацией. Эта информация содержит указатель "следующий", или "next", который указывает на следующий элемент. Также может быть указатель "предыдущий", или "prev", который аналогичным образом указывает на предыдущий элемент. В таком случае список будет двусвязным (Double Linked List).
Если предыдущего элемента нет (т.е. наш элемент самый первый) или следующего нет (т.е. наш элемент самый последний), то соответствующий указатель будет равен null (как 0, только для указателей).
В общем, практический интерес представляют только связные списки.
Что интересного в связных списках?
Перебор элементов связного списка становится очень простым: мы берем первый элемент, затем по прямой ссылке из первого элемента попадаем на второй, затем по прямой ссылке из второго элемента попадаем на третий и так далее, пока не дойдём до последнего элемента. Если у элемента есть ссылка на предыдущий элемент, значит перебор можно осуществить и в обратную сторону.
От связного списка мы можем получить не только значение элемента, но и сам элемент вместе с его указателями, и далее самостоятельно перемещаться по этим указателям.
Вот например, у осьминога одно из щупалец, предназначенное для размножения, может отделяться от тела и действовать самостоятельно. Так же и в связном списке можно выделить любой элемент и, например, отправить его в функцию. При этом, имея доступ только к нему, мы всегда будем иметь связь с другими элементами через указатели, которые находятся в этом элементе и путешествуют вместе с ним.
Но это ещё не все. Как говорилось выше, список изначально предназначен для вставки и удаления элементов, а массив – нет. Давайте посмотрим, что нужно для вставки элемента в середину массива:
- Начиная с места вставки, отодвинуть все элементы назад.
- Вставить элемент в освободившееся место.
Мы должны отодвигать элементы от места вставки, чтобы сохранить порядок. Если мы вставляем в массив элемент в позицию 3, значит элемент, который занимал позицию 3, должен теперь занять 4, а тот, который занимал 4, должен занять 5 и т.д.
Если в массиве много элементов, то их сдвиг может оказаться затратной операцией.
В связном списке и вставка, и удаление элемента делаются за одну операцию, независимо от размера списка. Новому элементу совершенно необязательно вставляться в какую-то определённую позицию и сдвигать все остальные элементы. Его достаточно добавить в конец списка, но указатели "предыдущий" и "следующий" назначить так, чтобы они показывали на предыдущий и следующий элемент в правильном порядке. Порядок в связном списке не зависит от того, в какой последовательности хранятся элементы. И значит, связный список работает эффективнее при вставке новых элементов. Правда, ценой лишних затрат памяти.
Удаление элемента работает аналогично. В массиве нужно сдвинуть все следующие элементы влево, чтобы закрыть освободившееся место. В списке освобождённый элемент просто исключается из цепочки путём перенаправления указателей предыдущего и следующего элементов. Позже этот удаленный элемент можно будет использовать повторно, если понадобится добавить элемент. Для этого, конечно, должен быть сделан какой-то учёт свободных элементов.
И может оказаться, что в определенных обстоятельствах связный список окажется даже медленнее массива. Но для этого и нужны разные типы коллекций: одни работают хорошо на одних задачах, другие на других. А наша обязанность – выбирать те, которые подходят лучше.
Подборка материалов про коллекции: