Комментарии 22
Спасибо — очень просто написано и легко для понимания.
Nibbler порадовал :-)
Nibbler порадовал :-)
Хороший цикл статей. Спасибо!
В связи со статьей возник вопрос: кто-нибудь в реальном проекте когда-либо использовал LinkedList?
Из своего опыта скажу, что даже в тех случаях, когда он по идее должен был дать прирост в производительности — т.е. большой список с частым удалением и добавлением элементов в середину и начало списка — ArrayList все равно оказывался быстрее.
Объяснение простое: ArrayList внутри себя использует System.arrayCopy — нативную функцию, которая отрабатывает на удивление шустро. В то же время для LinkedList'а приходится переопределять несколько указателей, но это не самое главное. Все эти указатели на предыдущего и следующего обходятся сборщиком мусора. Из-за этого растет время, необходимое для стадии маркинга, а с учетом того, что в одном списке оказываются элементы из разных поколений, вся процедура затягивается еще больше.
В единственный раз, когда LinkedList почти догнал ArrayList по производительности, я решил попробовать PersistentVector из Clojure, и тот оказался в полтора раза быстрее обоих. PersistentVector внутри представляет из себя дерево массивов, поэтому операции вставки приводят к изменению только одного или нескольких сегментов дерева, т.е. одной или нескольким операциям arrayCopy, которая для небольших массивов остается непревзойденной по скорости.
Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.
Из своего опыта скажу, что даже в тех случаях, когда он по идее должен был дать прирост в производительности — т.е. большой список с частым удалением и добавлением элементов в середину и начало списка — ArrayList все равно оказывался быстрее.
Объяснение простое: ArrayList внутри себя использует System.arrayCopy — нативную функцию, которая отрабатывает на удивление шустро. В то же время для LinkedList'а приходится переопределять несколько указателей, но это не самое главное. Все эти указатели на предыдущего и следующего обходятся сборщиком мусора. Из-за этого растет время, необходимое для стадии маркинга, а с учетом того, что в одном списке оказываются элементы из разных поколений, вся процедура затягивается еще больше.
В единственный раз, когда LinkedList почти догнал ArrayList по производительности, я решил попробовать PersistentVector из Clojure, и тот оказался в полтора раза быстрее обоих. PersistentVector внутри представляет из себя дерево массивов, поэтому операции вставки приводят к изменению только одного или нескольких сегментов дерева, т.е. одной или нескольким операциям arrayCopy, которая для небольших массивов остается непревзойденной по скорости.
Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.
В LinkedList добавление в конец или начало списка будет производиться всегда за одинаковое время независимо от текущего размера списка. Если вы не знаете какого размера будет ваш список заранее, то (ИМХО) для операции составления больших списков, лучше использовать LinkedList.
Да, это ясно, но ведь список будет какое-то время жить в рантайме, по нему нужно будет итерироваться, и с учетом того, что мы добавляем туда элементы, итерироваться придется неоднократно. А это довольно дорогая операция по сравнению с ArrayList'ом.
Если нам так уж нужно, чтобы элементы находились в определенном порядке, не лучше ли формализовать этот порядок в виде компаратора и использовать SortedSet?
А если порядок не нужен, почему бы не добавлять элементы в конец списка?
А если ожидаемое количество элементов известно, не проще ли создать ArrayList с заданным первоначальным размером?
А если все-таки, несмотря на все вышеперечисленные предложения, больше подходит LinkedList, не стоит ли посмотреть в сторону B-деревьев?
Есть только один сценарий, при котором LinkedList уместен — когда он стоит в основе реализации очереди, используемой несколькими потоками.
Если нам так уж нужно, чтобы элементы находились в определенном порядке, не лучше ли формализовать этот порядок в виде компаратора и использовать SortedSet?
А если порядок не нужен, почему бы не добавлять элементы в конец списка?
А если ожидаемое количество элементов известно, не проще ли создать ArrayList с заданным первоначальным размером?
А если все-таки, несмотря на все вышеперечисленные предложения, больше подходит LinkedList, не стоит ли посмотреть в сторону B-деревьев?
Есть только один сценарий, при котором LinkedList уместен — когда он стоит в основе реализации очереди, используемой несколькими потоками.
Я использовал. LinkedList реализует Queue. Там где нет потенциальных состязаний LinkedList меня устраивает.
Точно такой же вопрос возник с самого начала статьи. Помню времена, когда на еще на Паскале я делал разные динамические структуры в качестве задания… Кольцевой LinkedList я использовал для хранения виджетов в контейнере, чтобы удобней было Tab-ом фокус переключать.
Вообще LinkedList не позволяет random-access и может обрабатываться только последовательно. Поэтому область его применения сильно ограничена. ArrayList реально работает и быстрее и эффективнее.
Вообще LinkedList не позволяет random-access и может обрабатываться только последовательно. Поэтому область его применения сильно ограничена. ArrayList реально работает и быстрее и эффективнее.
Согласен, что очень специфичный и редко используемый контейнер. Для интереса запустил поиск по исходникам, которые когда-то писал… Примеры нашёл, хотя везде бы и ArrayList нормально сработал.
Вот пример: история введённых URL в программе с GUI. При введении нового адреса надо добавить его в начало списка, а если он уже был где-то в списке, то старый элемент удалить (чтобы не было дубликатов).
В этом случае у ArrayList по логике вещей будет больше операций (т. к. удаление будет всегда долгим, а изредка и добавление), хотя на практике еще непонятно кто будет работать быстрее.
Еще нашёлся пример с задачкой с diofant.ru: в алгоритме надо было в списке городов часто удалять из середины города по известному названию.
Вот пример: история введённых URL в программе с GUI. При введении нового адреса надо добавить его в начало списка, а если он уже был где-то в списке, то старый элемент удалить (чтобы не было дубликатов).
В этом случае у ArrayList по логике вещей будет больше операций (т. к. удаление будет всегда долгим, а изредка и добавление), хотя на практике еще непонятно кто будет работать быстрее.
Еще нашёлся пример с задачкой с diofant.ru: в алгоритме надо было в списке городов часто удалять из середины города по известному названию.
В итогах опечаточка. O(1) — из концов списка.
Однозначно в закладки. И периодически пересчитывать. Отличный цикл статей где можно сжато почитать о многом и освежевать в памяти забытые знания.
«header — псевдо-элемент списка. Его значение всегда равно null...»
Что-то я не вижу у себя никакого header`а. Или его и не должно быть? Тогда как он может быть null?
Да я понимаю, что статье уже 6 лет. Но все же джава привержена обратной совместимости. Если все же с тех пор все поменялось, то буду благодарен если кто-то поделится в какой версии это header был.
Что-то я не вижу у себя никакого header`а. Или его и не должно быть? Тогда как он может быть null?
Да я понимаю, что статье уже 6 лет. Но все же джава привержена обратной совместимости. Если все же с тех пор все поменялось, то буду благодарен если кто-то поделится в какой версии это header был.
Если наблюдаемое поведение не меняется, то и проблем с совместимостью нет.
Сейчас и пустой ArrayList, созданный без явного указания capacity, массива из 10 элементов не содержит и создаёт его только после начала заполнения.
Спасибо. Чуть промахнулся веткой: https://habrahabr.ru/post/127864/#comment_10187886
О, спасибо. Теперь вижу — в Java 7 header тоже еще был, а в восьмой исчез.
То есть, это private поле, только в пустом списке оно не равно null, как указанно в статье, а имеет null поля: header.next = header.prev = header.element = null.
А я себе думаю, что за магия такая — откуда у него могут быть поля (пусть и null`евые) если он сам null.
То есть, это private поле, только в пустом списке оно не равно null, как указанно в статье, а имеет null поля: header.next = header.prev = header.element = null.
А я себе думаю, что за магия такая — откуда у него могут быть поля (пусть и null`евые) если он сам null.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных в картинках. LinkedList