Разница между ArrayList и LinkedList в Java

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

LinkedList реализован в виде связанного списка, эти показатели добавления и удаления лучше, чем у ArrayList, но они плохи для методов get() и set().

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

ArrayList vs LinkedList

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

1) Так как Поиск в ArrayList основан на индексе элемента, поэтому он очень быстрый. Метод get(index) имеет сложность O(1), но удаление обходится дорого, так как приходится смещать все элементы. В случае с LinkedList, он не имеет прямого доступа к элементам, вы должны пройти через весь список, чтобы получить элемент, его сложность равна O(n).

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

3) Удаление похоже на вставку, лучше в LikedList, чем в ArrayList.

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

Когда использовать LinkedList и ArraList в Java

Очевидно, что LinkedList не так популярен, как ArrayList, но все же является хорошим выбором в некоторых случаях:

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

2) В приложении больше операций вставки и удаления, чем восстановления. Обе эти операции выполняются быстрее в LikedList.

Используйте ArrayList в Java в тех ситуациях, когда вам нужен несинхронизированный доступ. ArrayList быстр и прост в использовании.

Пример ArrayList

ArrayList< Строка> al = новый ArrayList< Строка> (); 
al.add("a"); 
al.add("c"); 
al.add("e"); 
al.add("z"); 
al.add("t"); 
al.add("m"); 

for(String s: e){
 System.out.println(e); 
}

Пример LinkedList

LinkedList< Целое число> llist = новый LinkedList< Целое число> (); 
llist.add(8); 
llist.add(9); 
llist.add(5); 
llist.add(2); 
llist.add(6); 
 
Итератор< Целое число> it = llist.iterator(); 
while(it.hasNext()){
 System.out.println(it.next()); 
}

Производительность ArrayList и LinkedList

Временная сложность обоих списков:

Operation	ArrayList	LinkedList
get()	O(1)	O(n)
add()	O(1)	O(1)
remove()	O(n)	O(1)

- ArrayList имеет совместимость по времени O(n) для операций add() и remove(), но O(1) для операции в конце списка или для получения элемента с помощью метода get().

- LinkedList имеет сложность O(n) для операции get(), но O(n) для операции remove remove().

Этот код проверяет производительность на основе времени, необходимого для выполнения ряда операций:

import java.util.ArrayList; 
import java.util.LinkedList; 

public class ArrayListVsLinkedList {

 public static void main(String[] args) {
 ArrayList< Целое число> alist = новый ArrayList< Целое число> (); 
 LinkedList< Целое число> llist = новый LinkedList< Целое число> (); 
 
 /******************************/
 /* Метод add() */
 /******************************/
 
 // ArrayList
 long tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 999999; i++) {
 alist.add(i); 
 }
 long tpsfin = System.currentTimeMillis(); 
 long duration = tpsfin - tpsdebut; 
 System.out.println("ArrayList add: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 999999; i++) {
 llist.add(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("LinkedList add: " + duration); 
 
 /******************************/
 /* Метод get() */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 99999; i++) {
 alist.get(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("ArrayList get: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 99999; i++) {
 llist.get(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("LinkedList get: " + duration); 
 
 /******************************/
 /* Метод remove() */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 9999; i >=0; i--) {
 alist.remove(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("ArrayList remove: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 9999; i >=0; i--) {
 llist.remove(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("LinkedList remove: " + duration); 
 }
}

Result:

ArrayList add: 398
LinkedList add: 987
ArrayList get: 180
LinkedList get: 43276
ArrayList remove: 8721
LinkedList remove:  233

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

Основное различие заключается в методах get() и remove(). Очевидно, что LinkedList отнимает очень много времени при извлечении данных, потому что он проходит по всему списку каждый раз, когда хочет получить доступ к элементу. ArrayList имеет прямой доступ. В отличие от этого, ArrayList отнимает много времени на операцию remove().