Как стать автором
Обновить

Комментарии 22

Спасибо — очень просто написано и легко для понимания.

Nibbler порадовал :-)
Хороший цикл статей. Спасибо!
В связи со статьей возник вопрос: кто-нибудь в реальном проекте когда-либо использовал LinkedList?

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

Объяснение простое: ArrayList внутри себя использует System.arrayCopy — нативную функцию, которая отрабатывает на удивление шустро. В то же время для LinkedList'а приходится переопределять несколько указателей, но это не самое главное. Все эти указатели на предыдущего и следующего обходятся сборщиком мусора. Из-за этого растет время, необходимое для стадии маркинга, а с учетом того, что в одном списке оказываются элементы из разных поколений, вся процедура затягивается еще больше.

В единственный раз, когда LinkedList почти догнал ArrayList по производительности, я решил попробовать PersistentVector из Clojure, и тот оказался в полтора раза быстрее обоих. PersistentVector внутри представляет из себя дерево массивов, поэтому операции вставки приводят к изменению только одного или нескольких сегментов дерева, т.е. одной или нескольким операциям arrayCopy, которая для небольших массивов остается непревзойденной по скорости.

Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.
В LinkedList добавление в конец или начало списка будет производиться всегда за одинаковое время независимо от текущего размера списка. Если вы не знаете какого размера будет ваш список заранее, то (ИМХО) для операции составления больших списков, лучше использовать LinkedList.
Да, это ясно, но ведь список будет какое-то время жить в рантайме, по нему нужно будет итерироваться, и с учетом того, что мы добавляем туда элементы, итерироваться придется неоднократно. А это довольно дорогая операция по сравнению с ArrayList'ом.

Если нам так уж нужно, чтобы элементы находились в определенном порядке, не лучше ли формализовать этот порядок в виде компаратора и использовать SortedSet?

А если порядок не нужен, почему бы не добавлять элементы в конец списка?

А если ожидаемое количество элементов известно, не проще ли создать ArrayList с заданным первоначальным размером?

А если все-таки, несмотря на все вышеперечисленные предложения, больше подходит LinkedList, не стоит ли посмотреть в сторону B-деревьев?

Есть только один сценарий, при котором LinkedList уместен — когда он стоит в основе реализации очереди, используемой несколькими потоками.
В бинарных деревьях удобно искать, а не добавлять. Процесс добавления может иногда может вызывать перестроение дерева, что «дорого».
В LinkedList же все наоборот, по крайней мере при добавлении в конец(начало).
Думаю, что от связанных списков вообще важна идея ) а в качестве отдельных элементов подоблного списка уже давно используют массивы.
Я использовал. LinkedList реализует Queue. Там где нет потенциальных состязаний LinkedList меня устраивает.
ArrayList тоже устроит, не так ли? :-)
Точно такой же вопрос возник с самого начала статьи. Помню времена, когда на еще на Паскале я делал разные динамические структуры в качестве задания… Кольцевой LinkedList я использовал для хранения виджетов в контейнере, чтобы удобней было Tab-ом фокус переключать.

Вообще LinkedList не позволяет random-access и может обрабатываться только последовательно. Поэтому область его применения сильно ограничена. ArrayList реально работает и быстрее и эффективнее.
Согласен, что очень специфичный и редко используемый контейнер. Для интереса запустил поиск по исходникам, которые когда-то писал… Примеры нашёл, хотя везде бы и ArrayList нормально сработал.

Вот пример: история введённых URL в программе с GUI. При введении нового адреса надо добавить его в начало списка, а если он уже был где-то в списке, то старый элемент удалить (чтобы не было дубликатов).

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

Еще нашёлся пример с задачкой с diofant.ru: в алгоритме надо было в списке городов часто удалять из середины города по известному названию.
В LinkedList итерирование займет больше, чем копирование части массива в ArrayList. Это утверждение верно как минимум для <=1024 элементов (проверено)
В обоих случаях (ArrayList и LinkedList) удаление дубликата потребует линейного времени.
Здесь подойдет LinkedHashSet: как и в списке, порядок элементов сохраняется, а удаление и добавление занимают постоянное время.
В итогах опечаточка. O(1) — из концов списка.
Если вы про
на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1)
то здесь всё верно написано. Загляните в исходник, в этих методах нет перебора элементов.
O(1), когда итератор уже «дошел» до нужного элемента. Если посмотреть в доку, то там сказано, что будет удален последний элемент, возвращенный методом next() (или previous()). А вот чтобы дойти до нужного элемента потребуется О(n/2) = O(n).
Однозначно в закладки. И периодически пересчитывать. Отличный цикл статей где можно сжато почитать о многом и освежевать в памяти забытые знания.
Знания всё-таки освежают, освежевывать их — это как-то уж слишком сурово :)
«header — псевдо-элемент списка. Его значение всегда равно null...»
Что-то я не вижу у себя никакого header`а. Или его и не должно быть? Тогда как он может быть null?

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

Java 6: http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/5f4bfda58ef8/src/share/classes/java/util/LinkedList.java#l95


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

О, спасибо. Теперь вижу — в Java 7 header тоже еще был, а в восьмой исчез.
То есть, это private поле, только в пустом списке оно не равно null, как указанно в статье, а имеет null поля: header.next = header.prev = header.element = null.
А я себе думаю, что за магия такая — откуда у него могут быть поля (пусть и null`евые) если он сам null.

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