- В чем разница между LinkedList
и ArrayList
? Когда предпочтительнее использовать LinkedList
?
Я думаю, что каждый разработчик Java слышал этот вопрос на собеседовании хотя бы один раз.
- Связанный список предпочтительнее, если вы хотите вставлять элементы в середине списка.
Это общий ответ на этот вопрос. Все это знают. Каждый раз, когда вы задаете вопрос о различии между реализациями List, вы получаете такие ответы, как:
Когда следует использовать LinkedList? Когда вам нужно эффективное удаление между элементами или в начале?
Забыл упомянуть о стоимости вставки. В LinkedList, когда у вас есть правильная позиция, затраты на вставку
O(1)
, а в ArrayList - доO(n)
- все элементы, находящиеся за точкой вставки, должны быть перемещены.
Связанные списки предпочтительнее, чем массивы, когда вы хотите вставлять элементы в середине списка (например, очередь приоритетов).
ArrayList работает медленнее, потому что ему нужно скопировать часть массива, чтобы удалить слот, который стал бесплатным. LinkedList просто должен манипулировать несколькими ссылками.
И еще...
Но вы когда-нибудь пытались воспроизвести его сами? Я пробовал вчера и получил следующие результаты:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String... args) {
final int MAX_VAL = 10000;
List<Integer> linkedList = new LinkedList<Integer>();
List<Integer> arrayList = new ArrayList<Integer>();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(i);
arrayList.add(i);
}
long time = System.nanoTime();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(MAX_VAL/2, i);
}
System.out.println("LL time: " + (System.nanoTime() - time));
time = System.nanoTime();
for(int i = 0; i < MAX_VAL; i++) {
arrayList.add(MAX_VAL/2, i);
}
System.out.println("AL time: " + (System.nanoTime() - time));
}
}
Вывод:
Время LL: 114098106
AL время: 24121889
Так что это? Почему LinkedList настолько высок? Может быть, мы должны попробовать операцию удаления вместо добавления? Хорошо, пусть попробует:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String... args) {
final int MAX_VAL = 10000;
List<Integer> linkedList = new LinkedList<Integer>();
List<Integer> arrayList = new ArrayList<Integer>();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(i);
arrayList.add(i);
}
long time = System.nanoTime();
for(int i = 0; i < MAX_VAL/2; i++) {
linkedList.remove(MAX_VAL/2);
}
System.out.println("LL time: " + (System.nanoTime() - time));
time = System.nanoTime();
for(int i = 0; i < MAX_VAL/2; i++) {
arrayList.remove(MAX_VAL/2);
}
System.out.println("AL time: " + (System.nanoTime() - time));
}
}
Вывод:
Время LL: 27581163
AL время: 3103051
О, ArrayList все же быстрее, чем LinkedList. Какова причина? Был ли этот миф разорен? Или, может быть, я ошибаюсь?