Различия в производительности между ArrayList и LinkedList

Question 1

Да, это - старая тема, но у меня все еще есть некоторые беспорядки.

В Java говорят люди:

ArrayList быстрее, чем LinkedList, если я случайным образом получаю доступ к его элементам. Я думаю, что средства произвольного доступа "дают мне энный элемент". Почему ArrayList быстрее?
LinkedList быстрее, чем ArrayList для удаления. Я понимаю этого. ArrayList медленнее начиная с внутреннего массива поддержки должен быть перераспределен. Объяснение кода:
```
List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.remove("b");
System.out.println(list.get(1)); //output "c"
```
LinkedList быстрее, чем ArrayList для вставки. Что вставка означает здесь? Если это означает класть обратно некоторые элементы и затем помещать элемент в среднее пустое пятно, ArrayList должен быть медленнее, чем LinkedList. Если вставка только означает добавить (Объектную) операцию, как это могло быть медленно?

Question 2

ArrayList

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

LinkedList:-

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

Теперь прибытие в Ваш questions:-

1) ArrayList сохраняет данные согласно индексам, и это реализует интерфейс RandomAccess, который является интерфейсом маркера, который обеспечивает возможность Случайного извлечения к ArrayList, но LinkedList не делает реализует Интерфейс RandomAccess вот почему, ArrayList быстрее, чем LinkedList.

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

Question 3

Question 4

Я хочу добавить дополнительную информацию ее о разнице в производительности.

Мы уже знаем, что вследствие того, что ArrayList реализация поддерживается Object[], это - произвольный доступ поддержек и динамическое изменение размеров и LinkedList, реализация использует ссылки на голову и хвост для навигации по нему. Это не имеет никаких возможностей произвольного доступа, но это поддерживает динамическое изменение размеров также.

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

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

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

Выезд для больше ArrayList и различия LinkedList .

Archit Bhadauria · Answer 1 · 1 November 2019 в 16:26