Комментарии 45
за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции вставки элемента);
Как раз сложность поиска элемента в двусвязном списке как раз O(N), и это надо прямо указывать. А то у меня от этой вставки и удаления из середины за О(1) глаза на лоб вылезли.
Из приятного — наглядность картинок порадовала. Продолжайте пробовать писать, но что-то более существенное и интересное, ибо то, что написано здесь — прям для совсем начинающих.
Ну, справделивости ради — через итераторы сложность удаления будет как-раз O(1). А вот если удалять по индексу/элементу — тут всё печально, да…
Но нужно до элемента доитерироватся, а это печально. Если стоять на месте и вставлять элементв временный лист и addAll часто оптимальнее.
Prototik а вы можете дать ссылку на какой-нибудь авторитетный ресурс, который подтвердит, что перебор элементов списка с помощью итератора осуществляется за О(1)?
перебор элементов списка с помощью итератора осуществляется за О(1)?
Перебор, очевидным образом осуществляется за O(n). Предыдущий комментарий был о том, что, если у нас есть итератор, который уже стоит на каком-то конкретном узле, скорость удаления этого узла никак не будет зависеть от количества элементов в LinkedList.
Объяснение хорошее, хотел бы добавить, что часто ArrayList даст фору LinkedList, даже там где, где вычислительная сложность у последнего лучше. Связано это с тем, при расчете вычислительной сложности, не учитывается особенности работы кеша. Когда в кеш загружается массив ArrayList, он делает это максимально быстро, все элементы находятся последовательно в одной области памяти. Объекты же связанного листа могут быть разбросаны в памяти и их придется загружать в кеш поштучно, что относительно дорого.
Да, и кроме того — иногда забывают, что ArrayList (по сути массив) занимает непрерывную область памяти и если попытаться создать такой список очень большого размера, то вполне реально упасть с ошибкой выделения памяти.
Процесс упадет, если попытаетесь выделить память превышающую лимит, а непрерывность, следствие фрагментации, это проблема языков с неуправляемой памятью. GC, когда занимается сбором мусора, именно для того останавливает все потоки исполнения, чтобы сдвинуть все оставшиеся в живых объекты в начало памяти, по сути он делает дефрагментацию. Просто пометить память как свободную от удаленных объектов, он мог бы на фоне, без остановки всего и вся. И именно поэтому в Java нет указателей, а есть ссылки, которые не дают доступ к физическому адресу в памяти, потому что этот адрес может меняться.
Далее, если мы имеем дело с большим объемом данных, то LinkedList тем более не подойдет, расходы памяти на него выше, чем у ArrayList. Каждый элемент оборачивается, небольшим, но все таки объектом Node. Когда ваша программа работает на пределе возможностей, универсального рецепта нет, но вероятно и от ArrayList придется отказаться тоже и работать с простыми массивами, как с наиболее низкоуровневыми объектами.
Далее, если мы имеем дело с большим объемом данных, то LinkedList тем более не подойдет, расходы памяти на него выше, чем у ArrayList. Каждый элемент оборачивается, небольшим, но все таки объектом Node. Когда ваша программа работает на пределе возможностей, универсального рецепта нет, но вероятно и от ArrayList придется отказаться тоже и работать с простыми массивами, как с наиболее низкоуровневыми объектами.
занимает непрерывную область памяти и если попытаться создать такой список очень большого размера, то вполне реально упасть с ошибкой выделения памяти.
Обычно JVM будет перемещать объекты пока не сможет выделить такую область памяти. То есть ошибка out of memory будет если банально кончится вся или почти вся свободная память. Но LinkedList занимает (по моим подсчетам) примерно в 4 раза больше места чем ArrayList, то есть он упадет с out of memory намного раньше, не говоря уже о бешеной нагрузке на сборщик мусора от миллионов объектов типа Node.
P.S. Есть разумеется фундаментальное ограничение на ArrayList и LinkedList в виде использования int в качестве их счетчика (а это 2 с небольшим миллиарда). Поэтому List не может быть больше 2 млд. с хвостиков значений, но это несколько гигабайт, а учитывая что в List хранятся только ссылки, то с объектами это десятки гигабайт на одну структуру. Как правило, для большинства даже серверных задач это с головой хватает (если вам нужно в памяти одного процесса держать десятки гигабайт данных в одном List — у вас что не так со архитектурой приложения).
Зря вы не упомянули add/remove в итераторе, это существенная часть внутреннего устройства (единственная реализация за O(1))
Как давно признался Шипилёву автор LinkedList,
Рекомендую прочитать весь тред.
twitter.com/joshbloch/status/583813919019573248
Рекомендую прочитать весь тред.
twitter.com/joshbloch/status/583813919019573248
Поавила использования LinkedList:
1. Не существует задач когда стоит использовать LinkedList,
2. Если у вас такая задача см. пункт 1,
Надо часто удалять из середины? Используйте ArrayList заменяя элементы на null, а потом их игнорируяя. При слишком большом кол-ве null — можно создать новый лист без null.
Надо всавлять в начало — переверните ArrayList и вставляйте в конец, С двух сторон — просто используйте 2 листа,
Надо вставлять в середину много элементом — используйте временный лист и addAll,
В конце концов, самое лучшее используйте TreeList из Apache коллекций. Не хотите /не можете тянуть зависимость? Просто скопируйте ее код.
Это осуждалось уже в моей статье
1. Не существует задач когда стоит использовать LinkedList,
2. Если у вас такая задача см. пункт 1,
Надо часто удалять из середины? Используйте ArrayList заменяя элементы на null, а потом их игнорируяя. При слишком большом кол-ве null — можно создать новый лист без null.
Надо всавлять в начало — переверните ArrayList и вставляйте в конец, С двух сторон — просто используйте 2 листа,
Надо вставлять в середину много элементом — используйте временный лист и addAll,
В конце концов, самое лучшее используйте TreeList из Apache коллекций. Не хотите /не можете тянуть зависимость? Просто скопируйте ее код.
Это осуждалось уже в моей статье
Его удобно использовать в качестве Dequeue. Каждый раз когда мне нужно решать какую-то задачу со стеком — использую его.
Так-то ArrayList тоже может использоватся для этого, добавление и удаление из конца вообще очень быстрое, разве что интерфейса он не реализует и писать чуть дольше, но можно увереным что он не станет узким местом в производительности.
А как работает удаление из начала?
Если все равно на производительность — то точно так же, если нет см. мой пост выше.
Это был риторический вопрос. Понятно что удаление из начала линкдлиста очень быстро, так же как и получение знаечния оттуда. Поэтому если нам надо Dequeue — LinkedList хорошая структура данных.
Когда говорят «очевидно/понятно/несомненно» темную сторону силы вижу я. Нет, не понятно и не очевидно, что будет быстрее (вы, видимо, совсем не смотрели мой комментарий и комментарии выше, в том числе от того кто написал LinkedList и те кто занимается производительностью JVM).
Придумайте любую задачу и тест производительности, а перепишу с использованием ArrayList (на крайний случай двух ArrayList) реализацию быстрее. Я уже не говорю о TreeList от апача, которые быстрее будет практически всегда.
И это не говоря о диких расходах памяти (намного больших чем ArrayList) и мусора для сборщика
Придумайте любую задачу и тест производительности, а перепишу с использованием ArrayList (на крайний случай двух ArrayList) реализацию быстрее. Я уже не говорю о TreeList от апача, которые быстрее будет практически всегда.
И это не говоря о диких расходах памяти (намного больших чем ArrayList) и мусора для сборщика
Лист, обёмом в полтора миллиарда long. Удаляем элемент по 0 индексу. Замеряем время до конца операции. Сравниваем ArrayList и LinkedList.
Не вопрос, заменяем элемент ArrayList на null и меняем внутренний индекс первого элемента. И замеряем скорость.
При вставке в первый элемент проводим обратную операцию (на случай вставки до удаления можно изначально начинать с firstIndex равным 10-30% от ожидаемого размера коллекции).
public class MyList {
private List<Long> list = new ArrayList<Long>(1500000000);
private int firstIndex;
public Long remove(int index) {
Long old = list.set(index + firstIndex, null);
if(index == 0) {
firstIndex++;
}
return old;
}
...
}
При вставке в первый элемент проводим обратную операцию (на случай вставки до удаления можно изначально начинать с firstIndex равным 10-30% от ожидаемого размера коллекции).
Не, я прошу удалить первый элемент с помощью remove(0). Чтобы работало как popFirst(). А вы предлагает саблисты использовать. Что ошибкоопасно. Да и итератор если получить — нас итератор от основного листа вернётся.
И раз уж мы тут говорим про сравнение листов — то ArrayList на 3 миллиарда элементов тоже не сделаешь.
И раз уж мы тут говорим про сравнение листов — то ArrayList на 3 миллиарда элементов тоже не сделаешь.
А вы предлагает саблисты использовать. Что ошибкоопасно.
Не хотите писать руками используйте (или скопируйте) TreeList от апача.
Да и итератор если получить — нас итератор от основного листа вернётся.
Кто сказал? Сложно написать свой итератор?
И раз уж мы тут говорим про сравнение листов — то ArrayList на 3 миллиарда элементов тоже не сделаешь.
С такими запросами вам классы BigList нужны
Учитывая что линкедлист занимает в 6 раз больше памяти (не говоря уже о 3 миллиардах объектов для сборщика), мы можем выделять в обе стороны по 100% запасу и все равно выиграем линкедлист в 2 раза по памяти.
Я скорость предлагаю мерить, а не память. Вы сказали вам подобрать пример когда ArrayList эффективнее чем LinkedList. Я подобрал и сказал что именно мы выигрываем. Почему вы мне говорите про то что мы на линдлисте проигрываем по памяти мне абсолютно непонятно. А ещё мы по скорости случайного доступа!
Я сказал, что нет задач для которых использование LinkedList имело бы смысл даже чисто по производительности, так как есть возможность либо написать свой код, либо использовать намного лучшие аналоги из сторонних коллекций (проверенные и оттестированные), если так уж не хочется свой код.
О чем вы спорите я тоже не знаю.
О чем вы спорите я тоже не знаю.
А разве в Java нет чего-нибудь вроде std::deque из c++ STL? Если нет, возможно, эффективнее будет реализовать руками, чем использовать LinkedList.
Он работает примерно следующим образом: храним массив (одним куском) + его размер, и два указателя на него: на первый элемент дека и на следующий после последнего.
При добавлении в конец или начало: смотрим, есть ли у нас свободное место в массиве. Если нет — выделяем новый массив в X (от 1 до 2) раз больше текущего и все элементы перемещаем в него. Дальше добавляем новый элемент по указателю на конец или начало, сдвигая его в нужную сторону. Сложность получается O(N) в случае увеличения размера, но, учитывая экспоненциальность выделения памяти, в среднем O(1).
В итоге у нас добавление и удаление элементов как в начало, так и в конец за O(1), а еще за O(1) поиск элемента по индексу и вообще все cache friendly.
Он работает примерно следующим образом: храним массив (одним куском) + его размер, и два указателя на него: на первый элемент дека и на следующий после последнего.
При добавлении в конец или начало: смотрим, есть ли у нас свободное место в массиве. Если нет — выделяем новый массив в X (от 1 до 2) раз больше текущего и все элементы перемещаем в него. Дальше добавляем новый элемент по указателю на конец или начало, сдвигая его в нужную сторону. Сложность получается O(N) в случае увеличения размера, но, учитывая экспоненциальность выделения памяти, в среднем O(1).
В итоге у нас добавление и удаление элементов как в начало, так и в конец за O(1), а еще за O(1) поиск элемента по индексу и вообще все cache friendly.
ArrayDeque.
Тогда почему бы не использовать его вместо LinkedList в качестве дека?
Допустим у меня в стеке должно лежить 3 миллиарда элементов…
Допустим. И?
Например, я вижу такое существенное отличие в данном случае, как экономия 6 млрд указателей (48 Гб памяти) по сравнению с LinkedList. Да и скорость итерирования за счет лучшего использования кеша будет лучше.
Например, я вижу такое существенное отличие в данном случае, как экономия 6 млрд указателей (48 Гб памяти) по сравнению с LinkedList. Да и скорость итерирования за счет лучшего использования кеша будет лучше.
PS: Сорри, возможно, я что-то как-то не так понимаю, ибо с C# сто лет как не работал, а когда работал, это было несерьезно. Но концепция дека на массиве от этого хуже не становится. В c++ нет ну вообще никаких проблем с тем, чтобы сделать std::deque (или std::vector, если такой класс пишется самостоятельно) на 3 млрд элементов.
В массиве не помещается 3 миллиарда элементов. Но вообще-то да, экономим мы либо память, либо процессор.
Это какое-то ограничение C#? Ну, тогда можно написать свой массив, который будет лишен этого недостатка.
Для хранения, скажем, 3 млрд 32-битных чисел в массиве нам нужно 3*4=12 Гб памяти, а для хранения их же в списке нам уже потребуется 3*(4 + 2*8)=60 Гб памяти. Как может такое быть, что первое не умещается в память, а второе умещается?
Для хранения, скажем, 3 млрд 32-битных чисел в массиве нам нужно 3*4=12 Гб памяти, а для хранения их же в списке нам уже потребуется 3*(4 + 2*8)=60 Гб памяти. Как может такое быть, что первое не умещается в память, а второе умещается?
Про шарп ничего ен знаю, тольк опро джаву, которую тут вроде бы и обсуждали. В массив в джаве в принципе не умещается больше чем Integer.MAX_VALUE элементов. А вот в линкдлисте таких ограничений нет.
Да, действительно, Java — опечатка.
А вот в линкдлисте таких ограничений нет.
Правда нет? То есть то что все методы интерфейса List принимают только int в качестве индекса вас не смущает?
А то что внутренне поле size у LinkedList тоже int — тоже не наводит на смутные сомнения, что больше Integer.MAX_VALUE элементов в LinkedList никак не влезет?
Поавила использования LinkedList:
- Не существует задач когда стоит использовать LinkedList,
- Если у вас такая задача см. пункт 1,
А как насчёт кейса, когда нужна стабильная производительность? Когда просадок на вырастание внутреннего массива надо избегать?
Тогда заранее можно выделить память с запасом, LinkedList в разы больше памяти ест. Ну и стабильно плохая производительность вряд ли лучше очень хорошей производительностью с ростом до чуть менее хорошей. Выделение массива не так сильно влияет на производительность, так как там используется системная функция выделения куска памяти и копирования, в большинстве случаев по сравнению с запуском сборщика (а LinkedList куда больше объектов создает) расширения массива нечто почти незаметное.
Правила именования листов:
1. Если перед вами лист дерева (структура данных или растение) — называйте его листом.
2. Если перед вами лист бумаги — называйте его листом.
2. Если перед вами ArrrayList или LinkedList — называйте их списками (точнее, списочным массивом и связанным списком). Вы, конечно, можете называть их и листами, но это так же неправильно, как называть их деревьями, массивами, графами, кошками или космическими кораблями.
1. Если перед вами лист дерева (структура данных или растение) — называйте его листом.
2. Если перед вами лист бумаги — называйте его листом.
2. Если перед вами ArrrayList или LinkedList — называйте их списками (точнее, списочным массивом и связанным списком). Вы, конечно, можете называть их и листами, но это так же неправильно, как называть их деревьями, массивами, графами, кошками или космическими кораблями.
LinkedList может быть полезен в качестве источника «сырых» данных (например, запроса из таблицы, который заранее условиями WHERE разбивать на части не удобно или не эффективно), которые приходится в цикле обрабатывать несколько раз, разделяя данные на части по какому-то условию. При каждом проходе из списка удаляются записи, соответствующими критерию из данного цикла, так что в следующем цикле приходится обходить гораздо меньше записей (null оставляет количество записей первоначальным, создание новой копии списка на каждом проходе снижает эффективность).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Что «под капотом» у LinkedList?