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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это наиболее часто используемые реализации 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) Как объяснялось выше, операции вставки и удаления дают хорошую производительность (O (1)) в LinkedList по сравнению с ArrayList (O (n)). Следовательно, если в приложении требуется частое добавление и удаление, то LinkedList - лучший выбор.

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

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

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

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

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

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

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

• Поиск

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

В: Так в чем же прелесть этого?

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

• Вставка

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

• Удаление

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

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

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

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

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

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

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

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

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

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

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

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

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

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