Когда использовать связанный список над массивом / списком массивов?

176

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

faceless1_14
источник
В Java ArrayList и LinkedList используют точно такой же код, кроме конструктора. Ваш "список массивов ... используемый так же легко или просто, как связанный список" не имеет смысла. Пожалуйста, приведите пример того, как ArrayList «проще», чем LinkedList.
S.Lott
2
Проверьте это также, stackoverflow.com/questions/322715/…
NoNaMe
Возможный дубликат массива против связанного списка
Hawkeye Parker
3
С. Лотт Это не правда. Java ArrayList - это оболочка для Array, с некоторыми добавленными служебными функциями. Связанный список - это, очевидно, связанный список. developer.classpath.org/doc/java/util/ArrayList-source.html
kingfrito_5005

Ответы:

261

Связанные списки предпочтительнее массивов, когда:

  1. вам нужны постоянные вставки / удаления из списка (например, в вычислениях в реальном времени, где предсказуемость времени абсолютно необходима)

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

  3. вам не нужен произвольный доступ к любым элементам

  4. вы хотите иметь возможность вставлять элементы в середину списка (например, очередь с приоритетами)

Массивы предпочтительнее, когда:

  1. вам нужен индексированный / произвольный доступ к элементам

  2. Вы заранее знаете количество элементов в массиве, чтобы вы могли выделить правильный объем памяти для массива.

  3. вам нужна скорость при переборе всех элементов в последовательности. Вы можете использовать указатель на массиве для доступа к каждому элементу, тогда как вам нужно искать узел на основе указателя для каждого элемента в связанном списке, что может привести к сбоям страницы, что может привести к падению производительности.

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

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

Lamar
источник
7
Хорошее начало, но это оставляет важные вещи: списки поддерживают совместное использование структуры, массивы плотнее и имеют лучшую локальность.
Дариус Бэкон
1
Практически разница в производительности между массивами и массивами незначительна. Это предполагает, что вы сравниваете сопоставимые данные и, например, когда вы заранее знаете размер, вы сообщаете об этом arraylist.
свик
40
С каких это пор LinkedList имеет O (1) вставки / удаления (что, я полагаю, вы имеете в виду, когда говорите, что вставляет / удаляет постоянное время )? Вставить материал в середину LinkedList всегда O (n)
Pacerier
28
LinkedLists имеют O (1) вставки, если вы уже находитесь в месте вставки (через итератор). Хотя не всегда.
Адам
4
Использование связанных списков для приоритетных очередей - очень глупая идея. Динамические кучи на основе массива допускают вставку с амортизацией O (lg n) и логарифмическое удаление в наихудшем случае min-min и являются одними из самых быстрых практических структур очередей с приоритетами.
Фред Фу
54

Массивы имеют O (1) произвольный доступ, но очень дорого добавлять или удалять вещи.

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

Dustin
источник
3
Удаление элементов из конца массива является продолжением времени, как и вставка / удаление элементов с любого конца связанного списка. Посередине ... не так уж и много.
Джои
1
@Joey не вставка / удаление в конце связанного списка O (n)? Если вы уже не расположены на предпоследней ссылке, вам все равно понадобится O (n) шагов, чтобы найти последний элемент, не так ли?
Алекс Мур-Ниеми,
@ AlexMoore-Niemi: для односвязного списка, да. Но многие имеют ссылки вперед и назад, и, следовательно, сохраняют указатели на любой конец.
Джои
2
Наличие двусвязных списков заставит вас выполнять поиск вперед и назад, если только ваш LL не имеет упорядоченных значений ... и все же наихудший сценарий - O (n)
securecurve
«Связанные списки действительно дешевы, чтобы добавлять или удалять элементы в любом месте и повторять их» не совсем верно. Если я хочу удалить элемент, который находится в середине связанного списка, мне нужно будет выполнить итерацию с самого начала, пока не достигну этого элемента в списке. Время O (n / 2), где n = количество элементов в списке. Из вашего ответа кажется, что вы предлагаете его постоянное время O (1), как в массиве. Это постоянное время для добавления / удаления из заголовка / корневого узла связанного списка.
Явар Муртаза
22
Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayLists хороши для записи один раз для чтения или добавления, но плохо подходят для добавления / удаления спереди или посередине.

Vpn_talent
источник
14

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

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

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

Джей Конрод
источник
1
Кроме того, вы также можете реализовать связанные списки (в смысле абстрактного типа данных), используя динамические массивы. Таким образом, вы можете использовать компьютерный кэш, амортизируя вставки и удаления с постоянным временем в начале списка, а также амортизируя вставки и удаления с постоянным временем в середине списка, когда у вас есть индекс элемента, после которого вставка должна быть сделано или индекс элемента для удаления (не требуется сдвиги / отмены). Хорошая ссылка для этого - CLRS 10.3 .
Доменико де Феличе,
7

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

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

Uri
источник
Сдвиг и изменение размера массива - это то, что действительно происходит, когда вы делаете инверсии в середине. Сдвиг вам потребуется без изменения размера, если вы не достигнете предела амортизации.
securecurve
3

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

  • Поиск

Поскольку массив - это структура данных, основанная на индексе, поиск в array.get (index) займет O (1) времени, в то время как связанный список не является индексным DS, поэтому вам нужно перейти к индексу, где index <= n, n - размер связанного списка, так что массив быстрее связывает список, когда имеет произвольный доступ к элементам.

Q. Так в чем красота этого?

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

  • вставка

Это легко и быстро в LinkedList, так как вставка является операцией O (1) в LinkedList (в Java) по сравнению с массивом, рассмотрим случай, когда массив заполнен, нам нужно скопировать содержимое в новый массив, если массив заполнится, что делает вставку элемент в ArrayList из O (n) в худшем случае, в то время как ArrayList также должен обновить свой индекс, если вы вставляете что-либо где-нибудь, кроме конца массива, в случае связанного списка нам не нужно изменять его размер, вам просто нужно обновить указатели.

  • делеция

Он работает как вставки и лучше в LinkedList, чем массив.

Harleen
источник
2

Это наиболее распространенные используемые реализации Collection.

ArrayList:

  • вставка / удаление в конце обычно O (1) худший случай O (n)

  • вставить / удалить в середине O (n)

  • восстановить любую позицию O (1)

LinkedList:

  • вставить / удалить в любой позиции O (1) (обратите внимание, если у вас есть ссылка на элемент)

  • получить в середине O (N)

  • получить первый или последний элемент O (1)

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

HashMap

вставить / удалить / получить по ключу в O (1)

TreeSet вставить / удалить / содержит в O (журнал N)

HashSet вставить / удалить / содержит / размер в O (1)

Правин Кумар Верма
источник
1

В действительности локальность памяти оказывает огромное влияние на производительность при реальной обработке.

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

Если есть какой-либо способ последовательного доступа к массиву, это, безусловно, самый эффективный способ. Проектирование с этой целью должно, по крайней мере, рассматриваться, если важна производительность.

user3150186
источник
0

Хмм, Arraylist может быть использован в следующих случаях:

  1. Вы не уверены, сколько элементов будет присутствовать
  2. но вам нужно получить доступ ко всем элементам случайным образом с помощью индексации

Например, вам нужно импортировать и получить доступ ко всем элементам в списке контактов (размер которых вам неизвестен)

Рагу
источник
0

Используйте связанный список для Radix Sort по массивам и для полиномиальных операций.

gizgok
источник
0

1) Как объяснено выше, операции вставки и удаления дают хорошую производительность (O (1)) в LinkedList по сравнению с ArrayList (O (n)). Следовательно, если существует требование частого добавления и удаления в приложении, тогда LinkedList является лучшим выбором.

2) Операции поиска (получения метода) выполняются быстро в Arraylist (O (1)), но не в LinkedList (O (n)), поэтому, если операций добавления и удаления меньше и требуется больше операций поиска, лучшим выбором будет ArrayList.

Аваниш Кумар
источник
0

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

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

Для связанного списка это o (1), потому что вам нужно только создать узел, переназначить заголовок и назначить ссылку next как предыдущий заголовок.

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

Я думаю, что поиск в связанном списке и массивах будет o (log n), потому что вы, вероятно, будете использовать бинарный поиск.

Curious_goat
источник
0

Я провел несколько тестов и обнаружил, что класс списка на самом деле быстрее, чем LinkedList для случайной вставки:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            ll.AddLast(0);
            for (int i = 1; i < count; i++)
            {
                ll.AddBefore(ll.Find(rand.Next(i)),i);

            }
            Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);

            watch = Stopwatch.StartNew();
            List<int> list = new List<int>();
            list.Add(0);
            for (int i = 1; i < count; i++)
            {
                list.Insert(list.IndexOf(rand.Next(i)), i);

            }
            Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);

            Console.ReadLine();
        }
    }
}

Требуется 900 мс для связанного списка и 100 мс для класса списка.

Создает списки последующих целых чисел. Каждое новое целое число вставляется после случайного числа, которое уже есть в списке. Может быть, класс List использует что-то лучше, чем просто массив.

Эмиль Альберт
источник
Список - это интерфейс, а не класс
borgmater
0

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

Связанные списки полезны для реализации стеков и очередей в ситуациях, когда их размер может варьироваться. Каждый узел в связанном списке может быть выдвинут или вытолкнут, не нарушая большинство узлов. То же самое касается вставки / удаления узлов где-то посередине. В массивах, однако, все элементы должны быть сдвинуты, что является дорогостоящей работой с точки зрения времени выполнения.

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

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

фотонный
источник
0

Простой ответ на вопрос можно дать, используя следующие пункты:

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

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

  3. Для массивов конкретный размер должен быть объявлен изначально. Но связанные списки имеют динамический размер.

Рохит Гойнар
источник