Массив против связанного списка

Question

Зачем кому-то использовать связанный список над массивом?

Кодирование связанного списка, без сомнения, немного сложнее, чем использование массива, и можно задаться вопросом, что оправдывает дополнительные усилия.

Я думаю, что вставка новых элементов тривиальна в связанном списке, но это основная работа в массиве. Есть ли другие преимущества использования связанного списка для хранения набора данных по сравнению с хранением его в массиве?

Этот вопрос не является дубликатом этого вопроса , поскольку другой вопрос касается конкретно определенного класса Java, в то время как этот вопрос касается общих структур данных.

Answer 1

У Эрика Липперта недавно была запись по одной из причин, по которой массивы следует использовать консервативно.

Answer 2

Быстрая вставка и удаление действительно лучшие аргументы для связанных списков. Если ваша структура растет динамически и доступ к любому элементу в постоянном времени не требуется (например, к динамическим стекам и очередям), хорошим выбором будет связанный список.

Answer 3

Вот быстрый: удаление предметов происходит быстрее.

Answer 4

Никто больше не кодирует свой собственный связанный список. Это было бы глупо. Предположение, что использование связанного списка требует больше кода, просто неверно.

В наши дни создание связного списка - это просто упражнение для студентов, чтобы они могли понять концепцию. Вместо этого каждый использует предварительно составленный список. В C ++, основываясь на описании в нашем вопросе, это, вероятно, означало бы вектор stl (#include <vector>).

Таким образом, выбор связанного списка против массива равен полностью относительно взвешивания различных характеристик каждой структуры относительно потребностей вашего приложения. Преодоление дополнительного бремени программирования должно иметь нулевое влияние на решение.

Answer 5

Помимо добавления и удаления из середины списка, мне больше нравятся связанные списки, потому что они могут динамически увеличиваться и уменьшаться.

Answer 6

Linked-list особенно полезны, когда коллекция постоянно растет и сокращается. Например, трудно представить себе попытку реализовать Очередь (добавить в конец, удалить спереди) с помощью массива - вы бы потратили все свое время на смещение вещей вниз. С другой стороны, это тривиально со связанным списком.

Answer 7

Массивы имеют смысл там, где будет известно точное количество элементов, и где поиск по индексу имеет смысл. Например, если бы я хотел сохранить точное состояние моего видеовыхода в данный момент без сжатия, я бы, вероятно, использовал массив размером [1024] [768]. Это даст мне именно то, что мне нужно, и список будет намного, намного медленнее, чтобы получить значение данного пикселя. В местах, где массив не имеет смысла, как правило, типы данных лучше, чем список, для эффективной обработки данных.

Answer 8

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

Answer 9

Массивы против связанного списка:

1. Выделение памяти массива иногда происходит из-за фрагментации памяти.
2. Кэширование лучше в массивах, поскольку все элементы выделяются непрерывным пространством памяти.
3. Кодирование является более сложным, чем массивы.
4. Нет ограничений на размер в связанном списке, в отличие от массивов
5. Вставка / удаление быстрее в связанном списке и доступ быстрее в массивах.
6. Связанный список лучше с точки зрения многопоточности.

Answer 10

Связанные списки требуют больше обслуживания, чем массива, они также требуют дополнительной памяти, все эти точки согласованы. Но есть несколько вещей, которые массив не может сделать. Во многих случаях предположим, что вам нужен массив длиной 10 ^ 9, вы не можете его получить, потому что там должна быть одна непрерывная ячейка памяти. Связанный список может быть спасителем здесь.

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

Контейнеры STL обычно имеют реализацию связанного списка за сценой.