Когда вы используете java.util.LinkedList

Можно создать дубликат:
When to use LinkedList<> over ArrayList<>?Когда вы используете java.util.LinkedList

Это искренняя попытка узнать, когда будет один использовать LinkedList;

От того, что я понимаю, поскольку java.util.LinkedList не поддерживает случайный доступ, единственный способ получить n-й элемент - пропустить от 1 до (n-1) или использовать get (n), который сам является очень неэффективен. Итак, зачем использовать LinkedList? ArrayList будет использоваться для большей части, если вы не хотите итерировать коллекцию с обеих сторон с помощью ListIterator?

источник

2012-03-19 sachinrahulsourav

Получение n-го элемента достоверно звучит как произвольный доступ. –

@Steve Kuo, LinkedList не разрешают случайный доступ. Вы можете сделать get (n), но сама реализация этого метода начинается с пропуска с 1 на (n-1). Поэтому его неслучайный доступ – sachinrahulsourav

Подумайте об этом методе:

List list = // choose your list here 
list.add(0, new Object());

Для больших списков, LinkedList будет сильно из-выполнить ArrayList. То же самое относится к

list.remove(0);

... и многие другие методы. Для получения дополнительной информации я предлагаю ознакомиться с интерфейсом java.util.Deque, который также реализован LinkedList

источник

2012-03-19 17:26:04

list.remove() - это интерфейс Iterator, и эта операция будет иметь такую же эффективность и в ArrayList. Что касается list.add(), я согласен с тем, что элемент, расположенный где-то в списке, эффективен для больших списков с LinkedList. – sachinrahulsourav

@sachinrahulsourav: Проверьте исходный код 'remove (int)'. 'ArrayList' выполняет вызов' System.arraycopy', тогда как 'LinkedList' просто обновляет некоторые ссылки ... Объявление в интерфейсе не влияет на факты реализации ... Кроме того, обратите внимание, что' remove (int) ' не объявляется в 'Iterator', но в' List' ... –

Вы правы. Я только что понял, remove() должен будет сделать копию и обновить ссылки. – sachinrahulsourav

Рассмотрим 3 общих оператора в этих типах структур данных: доступ к случайным элементам, добавление элементов и удаление элементов.

В LinkedList доступ к случайным элементам медленный (O (N)), но добавление и удаление быстрые (O (1)). Для ArrayList обратное верно: доступ к произвольному элементу выполняется быстро (O (N)), но добавление и удаление элементов медленнее.

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

источник

2012-03-19 17:30:45 Oleksi

Вставьте или удалите элемент откуда? Это может быть O (n). –

@ TomHawtin-tackline Только если вы включили поиск узла списка для этого элемента. В некоторых случаях у вас уже есть это, или вы можете получить его в постоянное время. И во многих случаях, когда вы должны искать, вам приходилось искать все равно, даже если у вас был массив. – delnan

-1

LinkedList лучше подходит (по сравнению с ArrayList) для вставки/удаление для произвольных индексов. При вставке или удалении из ArrayList внутренний массив должен быть сдвинут. Для LinkedList это вопрос просто повторения указатели узлов.

источник

2012-03-19 17:32:23

Произвольные индексы? O (n) для обоих. Только «ArrayList» будет скорее быстрее. –

Когда вы используете java.util.LinkedList

ответ

Смежные вопросы