В чем разница между ArrayList и LinkedList?

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

  1. Операция поиска
  2. Манипуляция
  3. Поведение
  4. Накладные расходы памяти

Операция поиска

Операция поиска в ArrayList довольно быстро по сравнению с операцией поиска LinkedList. Метод ArrayList get (int index) дает производительность O (1), в то время как производительность LinkedList равна O (n). Это связано с тем, что ArrayList позволяет произвольный доступ к элементам в списке, поскольку он работает с основанной на индексе структурой данных, в то время как LinkedList не разрешает произвольный доступ, поскольку он не имеет индексов для непосредственного доступа к элементам, он должен пересекать список для извлечения или получить доступ к элементу из списка.

Манипуляции

Манипуляция с ArrayList медленная, поскольку она внутренне использует массив. Если нам нужно вставить или удалить элемент в ArrayList, он может принимать O (n), поскольку он внутренне использует массив, и нам может потребоваться сдвинуть элементы в случае вставки или удаления. С другой стороны, манипуляции с LinkedList быстрее, чем ArrayList, потому что он использует двусвязный список, поэтому в памяти не требуется сдвиг бит. Если нам нужно вставить или удалить элемент в LinkedList, он будет принимать O (1), поскольку он внутренне использует дважды.

ArrayList Vs LinkedList в Java

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

Поведение

Arraylist ведет себя как List, поскольку он реализует список. LinkedList ведет себя как List a, а также Queue, поскольку он реализует List и Queue.

Накладные расходы памяти

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

Реализация ArrayList

Выход

Реализация LinkedList

Выход

Источник: http://net-informations.com/Java/cJava/linkedlist.htm

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)

Add a Comment

Ваш e-mail не будет опубликован. Обязательные поля помечены *