#data-structures #complexity-theory
#структуры данных #теория сложности
Вопрос:
действительно нравится заголовок. Мой вопрос в том, можете ли вы привести пример, когда связанный список является НАИЛУЧШЕЙ структурой данных для использования. Я изо всех сил пытался придумать что-нибудь действительно, и в своем коде я почти всегда просто использую хэш-карты или списки и т. Д.
http://bigocheatsheet.com / Здесь вы можете увидеть шпаргалку Big O для различных операций. Связанный список ничем не лучше стека или очереди с точки зрения сложности. И поэтому я хотел знать, когда кто-то может использовать связанный список поверх них, например? Идеальный ответ будет гласить: «Представьте, что я пытаюсь выполнить XYZ, если бы я сделал это с массивом, это выглядело бы так {введите некоторый код}, однако, если я сделаю это со связанным списком, это будет выглядеть так {введите больше кода}. Сложность или пространство значительно лучше для связанного списка » и т. Д.
Мне не нужен ответ, в котором кто-то говорит мне, ЧТО такое связанный список. Я знаю, что такое связанный список и как они реализованы.
Спасибо
Комментарии:
1. Когда количество элементов невелико, связанный список — из-за его простоты — может быть быстрее, чем более сложная структура данных.
2. Когда вам нужна меньшая сложность или вообще отсутствие сложности. Связанные списки легче понять, чем другие сложные структуры.
Ответ №1:
Подумайте, есть ли у вас список людей, и где-то посередине вы хотите добавить много людей. Если бы вы использовали обычный ArrayList, вам нужно было бы переместить все элементы после него, так что O (N) из-за индексации на человека! В LinkedList каждый человек будет O (1), с O (N), чтобы добраться до середины. Связанные списки очень быстро добавляют элементы в середине, так как вам не нужно ничего переиндексировать и просто настроить локальный указатель.
Ответ №2:
Кто-то провел обзор стандартной библиотеки шаблонов C и обнаружил, что связанный список был наименее используемым из всех распространенных базовых структур. Так что вы правы, они мало используются. Они полезны, когда вам не нужен произвольный доступ к массиву, когда вы не знаете N или имеете достаточно жесткую верхнюю границу для N, и когда вставки и удаления являются общими и критичными по времени. Вставка в середину равна O (N), как в случае с массивом, но фактическая операция намного дешевле (разыменование указателя, а не смещение памяти), вставки в начале равны O (1) и в конце, если вы сохраняете конечный указатель.