Массив по сравнению со связанным списком

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

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

Disadvatige мог быть то, что указатели занимают много места.

И о том кодировании более твердо: Обычно Вы не должны кодировать связанный список (или только однажды) они включены в STL, и это не так сложно, если все еще необходимо сделать это.

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

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

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

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

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

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

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

Википедия имеет очень хороший раздел о различиях.

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

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

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

http://en.wikipedia.org/wiki/Linked_list

Я добавлю другого - списки могут действовать как чисто функциональный структуры данных.

, Например, у Вас могут быть совершенно другие списки, совместно использующие тот же раздел конца

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

т.е.:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

, не имея необходимость копировать данные, указываемые a в b и c.

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

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

, Но откровенно говоря, я никогда не использовал связанный список. Каждый раз, когда мне были нужны быстрая вставка и удаление, мне также был нужен быстрый поиск, таким образом, я перешел к HashSet или Словарю.

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

РЕДАКТИРОВАНИЕ: Для разъяснения я означал "объединяться" здесь в незаказанном смысле, не как в сортировке слиянием. Возможно, "конкатенация" была бы лучшим словом.

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

В первую очередь, в связанных списках C++ не должно быть намного больше проблемы для работы с, чем массив. Можно использовать станд.:: список или список указателя повышения для связанных списков. Ключевыми вопросами со связанными списками по сравнению с массивами является дополнительное пространство, требуемое для указателей и ужасного произвольного доступа. Необходимо использовать связанный список, если Вы

• Вам не будет нужен произвольный доступ к данным
• , то Вы будете добавлять/удалять элементы, особенно посреди списка

Две вещи:

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

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

Что касается фактических различий между массивом и связанным списком, большая вещь для меня состоит в том, как Вы планируете использование структуры. Я буду использовать вектор терминов, так как это - термин для массива изменяемого размера в C++.

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

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

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

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

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

Вот быстрый: Удаление объектов более быстро.

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

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

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

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

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

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

A widely unappreciated argument for ArrayList and against LinkedList is that LinkedLists are uncomfortable while debugging. The time spent by maintenance developers to understand the program, e.g. to find bugs, increases and IMHO does sometimes not justify the nanoseconds in performance improvements or bytes in memory consumption in enterprise applicatons. Sometimes (well, of course it depends on the type of applications), it's better to waste a few bytes but have an application which is more maintainable or easier to understand.

For example, in a Java environment and using the Eclipse debugger, debugging an ArrayList will reveal a very easy to understand structure:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

On the other hand, watching the contents of a LinkedList and finding specific objects becomes a Expand-The-Tree clicking nightmare, not to mention the cognitive overhead needed to filter out the LinkedList internals:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

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

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

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

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