Когда я должен использовать список против LinkedList

Когда лучше использовать List против LinkedList ?

редактировать

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

Оригинальный ответ ...

Я нашел интересные результаты:

// Temporary class to show the example
class Temp
{
    public decimal A, B, C, D;

    public Temp(decimal a, decimal b, decimal c, decimal d)
    {
        A = a;            B = b;            C = c;            D = d;
    }
}

Связанный список (3,9 секунды)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.AddLast(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Список (2,4 секунды)

        List<Temp> list = new List<Temp>(); // 2.4 seconds

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.Add(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Даже если вы только получаете доступ к данным, это существенно медленнее! Я говорю, никогда не используйте связанный список.

Вот еще одно сравнение, выполняющее много вставок (мы планируем вставить элемент в середине списка)

Связанный список (51 секунда)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            var curNode = list.First;

            for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
                curNode = curNode.Next;

            list.AddAfter(curNode, a); // Insert it after
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Список (7,26 секунд)

        List<Temp> list = new List<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.Insert(i / 2, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Связанный список, имеющий ссылку на место, куда вставить (0,04 секунды)

        list.AddLast(new Temp(1,1,1,1));
        var referenceNode = list.First;

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            list.AddBefore(referenceNode, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

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

В большинстве случаев List<T>это более полезно. LinkedList<T>будет стоить меньше при добавлении / удалении элементов в середине списка, тогда как List<T>добавление / удаление в конце списка будет дешевым .

LinkedList<T>только в наиболее эффективном случае, если вы обращаетесь к последовательным данным (в прямом или обратном направлении) - произвольный доступ является относительно дорогим, поскольку он должен обходить цепочку каждый раз (следовательно, поэтому у него нет индексатора). Тем не менее, поскольку a List<T>по сути является просто массивом (с оберткой), произвольный доступ - это нормально.

List<T>также предлагает много методов поддержки - Find, ToArrayи т.д.; тем не менее, они также доступны для LinkedList<T>.NET 3.5 / C # 3.0 с помощью методов расширения, так что это менее важный фактор.

Представление связанного списка как списка может быть немного обманчивым. Это больше похоже на цепь. На самом деле в .NET LinkedList<T>даже не реализуют IList<T>. В связанном списке нет реальной концепции индекса, хотя может показаться, что она есть. Конечно, ни один из методов, предоставленных в классе, не принимает индексы.

Связанные списки могут быть односвязными или двусвязными. Это относится к тому, имеет ли каждый элемент в цепочке ссылку только на следующий (односвязный) или на оба предыдущих / следующих элемента (двусвязный). LinkedList<T>вдвойне связан.

Внутренне, List<T>поддерживается массивом. Это обеспечивает очень компактное представление в памяти. И наоборот, LinkedList<T>включает в себя дополнительную память для хранения двунаправленных связей между последовательными элементами. Таким образом, объем занимаемой памяти LinkedList<T>обычно будет больше, чем для List<T>(с оговоркой, которая List<T>может иметь неиспользуемые элементы внутреннего массива для повышения производительности во время операций добавления).

Они также имеют разные характеристики производительности:

Append

• LinkedList<T>.AddLast(item) постоянное время
• List<T>.Add(item) амортизированное постоянное время, линейный наихудший случай

Prepend

• LinkedList<T>.AddFirst(item) постоянное время
• List<T>.Insert(0, item) линейное время

вставка

• LinkedList<T>.AddBefore(node, item) постоянное время
• LinkedList<T>.AddAfter(node, item) постоянное время
• List<T>.Insert(index, item) линейное время

Удаление

• LinkedList<T>.Remove(item) линейное время
• LinkedList<T>.Remove(node) постоянное время
• List<T>.Remove(item) линейное время
• List<T>.RemoveAt(index) линейное время

подсчитывать

• LinkedList<T>.Count постоянное время
• List<T>.Count постоянное время

Содержит

• LinkedList<T>.Contains(item) линейное время
• List<T>.Contains(item) линейное время

Очистить

• LinkedList<T>.Clear() линейное время
• List<T>.Clear() линейное время

Как видите, они в основном эквивалентны. На практике API LinkedList<T>более громоздок в использовании, и детали его внутренних потребностей выливаются в ваш код.

Однако, если вам нужно сделать много вставок / удалений из списка, он предлагает постоянное время. List<T>предлагает линейное время, так как дополнительные элементы в списке должны быть перемешаны после вставки / удаления.

Связанные списки обеспечивают очень быструю вставку или удаление члена списка. Каждый член в связанном списке содержит указатель на следующий член в списке, поэтому для вставки члена в позицию i:

• обновить указатель в элементе i-1, чтобы он указывал на новый элемент
• установить указатель в новом элементе, чтобы он указывал на элемент i

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

Мой предыдущий ответ был недостаточно точным. Как верно было ужасно: D Но теперь я могу опубликовать гораздо более полезный и правильный ответ.

Я сделал несколько дополнительных тестов. Вы можете найти его источник по следующей ссылке и заново проверить его в своей среде: https://github.com/ukushu/DataStructuresTestsAndOther.git

Краткие результаты:

• Массив нужно использовать:

  • Так часто, как это возможно. Это быстро и занимает наименьший диапазон оперативной памяти для того же объема информации.
  • Если вы знаете точное количество клеток, необходимых
  • Если данные сохранены в массиве <85000 b (85000/32 = 2656 элементов для целочисленных данных)
  • При необходимости высокая скорость произвольного доступа

• Список нужно использовать:

  • При необходимости добавить ячейки в конец списка (часто)
  • При необходимости добавить ячейки в начале / середине списка (НЕ ЧАСТО)
  • Если данные сохранены в массиве <85000 b (85000/32 = 2656 элементов для целочисленных данных)
  • При необходимости высокая скорость произвольного доступа

• LinkedList нужно использовать:

  • При необходимости добавить ячейки в начале / середине / конце списка (часто)
  • При необходимости только последовательный доступ (вперед / назад)
  • Если вам нужно сохранить БОЛЬШИЕ предметы, но количество предметов мало.
  • Лучше не использовать для большого количества элементов, так как он использует дополнительную память для ссылок.

Больше деталей:

Интересно знать:

1. LinkedList<T>внутренне это не список в .NET. Это даже не реализовать IList<T>. И именно поэтому отсутствуют индексы и методы, связанные с индексами.

2. LinkedList<T>коллекция на основе указателя узла. В .NET это в двусвязной реализации. Это означает, что предыдущие / следующие элементы имеют ссылку на текущий элемент. И данные фрагментированы - разные объекты списка могут быть расположены в разных местах оперативной памяти. Также будет использовано больше памяти, LinkedList<T>чем для List<T>или для массива.

3. List<T>в .Net является альтернативой Java ArrayList<T>. Это означает, что это оболочка массива. Таким образом, он выделяется в памяти как один непрерывный блок данных. Если выделенный размер данных превышает 85000 байт, он будет перемещен в кучу больших объектов. В зависимости от размера это может привести к фрагментации кучи (легкая форма утечки памяти). Но в то же время, если размер <85000 байт - это обеспечивает очень компактное и быстрое представление в памяти.

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

Разница между List и LinkedList заключается в их базовой реализации. Список - это массив на основе массива (ArrayList). LinkedList - это основанная на указателе узла коллекция (LinkedListNode). Что касается использования уровня API, то оба они в значительной степени одинаковы, поскольку оба реализуют один и тот же набор интерфейсов, таких как ICollection, IEnumerable и т. Д.

Ключевое различие возникает, когда производительность имеет значение. Например, если вы реализуете список со сложной операцией «INSERT», LinkedList превосходит List. Поскольку LinkedList может сделать это за O (1) раз, но List может потребоваться расширить размер базового массива. Для получения дополнительной информации вы можете прочитать об алгоритмическом различии между LinkedList и структурами данных массива. http://en.wikipedia.org/wiki/Linked_list и Array

Надеюсь, это поможет,

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

Обычное обстоятельство использования LinkedList выглядит следующим образом:

Предположим, вы хотите удалить много определенных строк из списка строк большого размера, скажем, 100 000. Строки для удаления можно найти в HashSet dic, и список строк, как полагают, содержит от 30000 до 60000 таких строк для удаления.

Тогда какой тип списка лучше всего подходит для хранения 100 000 строк? Ответ LinkedList. Если они хранятся в ArrayList, то итерация по нему и удаление совпадающих строк может занять до миллиардов операций, в то время как с помощью итератора и метода remove () требуется всего около 100 000 операций.

LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
    String string = iterator.next();
    if (dic.contains(string))
    iterator.remove();
}

Когда вам нужен встроенный индексированный доступ, сортировка (и после этого двоичного поиска) и метод «ToArray ()», вы должны использовать List.

По сути, List<>в .NET это обертка над массивом . А LinkedList<> является связанным списком . Таким образом, вопрос сводится к тому, какова разница между массивом и связанным списком, и когда следует использовать массив вместо связанного списка. Вероятно, два наиболее важных фактора в вашем решении, которые следует использовать, сводятся к следующему:

• Связанные списки имеют намного лучшую производительность вставки / удаления, если только вставки / удаления не находятся на последнем элементе в коллекции. Это связано с тем, что массив должен сдвигать все оставшиеся элементы, которые идут после точки вставки / удаления. Однако, если вставка / удаление находится в конце списка, этот сдвиг не требуется (хотя может потребоваться изменить размер массива, если его емкость превышена).
• Массивы имеют гораздо лучшие возможности доступа. Массивы могут быть проиндексированы напрямую (в постоянное время). Связанные списки должны быть пройдены (линейное время).

Это адаптировано из принятого ответа Тоно Нама, исправляющего несколько неправильных измерений в нем.

Тест:

static void Main()
{
    LinkedListPerformance.AddFirst_List(); // 12028 ms
    LinkedListPerformance.AddFirst_LinkedList(); // 33 ms

    LinkedListPerformance.AddLast_List(); // 33 ms
    LinkedListPerformance.AddLast_LinkedList(); // 32 ms

    LinkedListPerformance.Enumerate_List(); // 1.08 ms
    LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms

    //I tried below as fun exercise - not very meaningful, see code
    //sort of equivalent to insertion when having the reference to middle node

    LinkedListPerformance.AddMiddle_List(); // 5724 ms
    LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
    LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
    LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms

    Environment.Exit(-1);
}

И код:

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

namespace stackoverflow
{
    static class LinkedListPerformance
    {
        class Temp
        {
            public decimal A, B, C, D;

            public Temp(decimal a, decimal b, decimal c, decimal d)
            {
                A = a; B = b; C = c; D = d;
            }
        }



        static readonly int start = 0;
        static readonly int end = 123456;
        static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);

        static Temp temp(int i)
        {
            return new Temp(i, i, i, i);
        }

        static void StopAndPrint(this Stopwatch watch)
        {
            watch.Stop();
            Console.WriteLine(watch.Elapsed.TotalMilliseconds);
        }

        public static void AddFirst_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(0, temp(i));

            watch.StopAndPrint();
        }

        public static void AddFirst_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddFirst(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Add(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        public static void Enumerate_List()
        {
            var list = new List<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        public static void Enumerate_LinkedList()
        {
            var list = new LinkedList<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        //for the fun of it, I tried to time inserting to the middle of 
        //linked list - this is by no means a realistic scenario! or may be 
        //these make sense if you assume you have the reference to middle node

        //insertion to the middle of list
        public static void AddMiddle_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(list.Count / 2, temp(i));

            watch.StopAndPrint();
        }

        //insertion in linked list in such a fashion that 
        //it has the same effect as inserting into the middle of list
        public static void AddMiddle_LinkedList1()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            LinkedListNode<Temp> evenNode = null, oddNode = null;
            for (int i = start; i < end; i++)
            {
                if (list.Count == 0)
                    oddNode = evenNode = list.AddLast(temp(i));
                else
                    if (list.Count % 2 == 1)
                        oddNode = list.AddBefore(evenNode, temp(i));
                    else
                        evenNode = list.AddAfter(oddNode, temp(i));
            }

            watch.StopAndPrint();
        }

        //another hacky way
        public static void AddMiddle_LinkedList2()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start + 1; i < end; i += 2)
                list.AddLast(temp(i));
            for (int i = end - 2; i >= 0; i -= 2)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        //OP's original more sensible approach, but I tried to filter out
        //the intermediate iteration cost in finding the middle node.
        public static void AddMiddle_LinkedList3()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
            {
                if (list.Count == 0)
                    list.AddLast(temp(i));
                else
                {
                    watch.Stop();
                    var curNode = list.First;
                    for (var j = 0; j < list.Count / 2; j++)
                        curNode = curNode.Next;
                    watch.Start();

                    list.AddBefore(curNode, temp(i));
                }
            }

            watch.StopAndPrint();
        }
    }
}

Вы можете увидеть результаты в соответствии с теоретическими характеристиками, которые другие документировали здесь. Совершенно ясно - LinkedList<T>выигрывает в случае вставок. Я не проверял удаление из середины списка, но результат должен быть таким же. Конечно, List<T>есть и другие области, где он работает лучше, чем O (1) произвольный доступ.

Используйте LinkedList<>когда

1. Вы не знаете, сколько объектов проходит через ворота затопления. Например, Token Stream.
2. Когда вы хотели только удалить \ вставить в конце.

Для всего остального лучше использовать List<>.

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

Но я просто хочу добавить, что есть много случаев, когда LinkedList гораздо лучший выбор, чем List для лучшей эффективности.

1. Предположим, вы просматриваете элементы и хотите выполнить много вставок / удалений; LinkedList делает это за линейное O (n) время, тогда как List делает это за квадратичное O (n ^ 2) время.
2. Предположим, что вы хотите снова и снова получать доступ к более крупным объектам, LinkedList стал очень полезным.
3. Deque () и queue () лучше реализованы с помощью LinkedList.
4. Увеличение размера LinkedList намного проще и лучше, если вы имеете дело со многими и более крупными объектами.

Надеюсь, кто-то найдет эти комментарии полезными.

Так много средних ответов здесь ...

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

Используйте связанные списки, когда

1) Вы хотите безопасность потока. Вы можете создавать более безопасные многопоточные алгоритмы. Затраты на блокировку будут доминировать в списке одновременных стилей.

2) Если у вас есть большие очереди, подобные структурам, и вы хотите удалить или добавить где угодно, но конец всегда. > 100К списков существует, но не так часто.

Я спросил похожий вопрос, связанный с производительностью коллекции LinkedList , и обнаружил, что реализация Deque Стивена Клири на C # была решением. В отличие от коллекции Queue, Deque позволяет перемещать предметы вперед / назад вперед и назад. Это похоже на связанный список, но с улучшенной производительностью.