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

Question

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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 хороши для однократного чтения или добавления, но плохо при добавлении / удалении спереди или по середине.

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

• Поиск

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

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

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

• вставка

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

• Удаление

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

Answer 7

Это наиболее часто используемые реализации 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)

Answer 8

Я провел несколько тестов и обнаружил, что класс списка на самом деле быстрее, чем 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 использует что-то лучше, чем просто массив.

Answer 9

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

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

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

Answer 10

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

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

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

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

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