Результаты теста
Без лишних слов, давайте сначала получим результаты теста. Автор сравнивает время, необходимое для вставки и поиска 100 000 элементов в начале, конце и середине ArrayList и LinkedList.Ниже приведены результаты теста.
(Спасибо @Hosalo за исправление, здесь я объясню тестовую среду. Вставка хвоста тестируется на основе пустой таблицы, а вставка головы и среднего положения тестируется на таблице со 100 000 элементов.)
| вставлять | найти | |
|---|---|---|
| Хвост ArrayList | 26ms | 4ms |
| Заголовок списка массивов | 2887ms | 3ms |
| средний список массивов | 1936ms | 4ms |
| Хвост LinkedList | 28ms | 9ms |
| Заголовок связанного списка | 15ms | 11ms |
| средний LinkedList | 12310ms | 11387ms |
Заключение теста
- Производительность поиска в ArrayList абсолютно первоклассная, независимо от того, где запрашивается элемент.
- Помимо лучшей производительности вставки ArrayList в конец (чем позже позиция, тем лучше производительность), производительность других позиций неудовлетворительна.
- LinkedList имеет высокую производительность поиска и вставки в начале и в конце, но если он работает в середине, производительность намного хуже, и она не того же порядка, что и ArrayList.
Анализ исходного кода
Мы рассматриваем ArrayList и LinkedList в Java как реализацию списка последовательностей и двусвязного списка соответственно, поэтому, прежде чем анализировать исходный код, давайте кратко рассмотрим ключевые концепции списка последовательностей и двусвязного списка в структуре данных.
- Таблица последовательности: вам необходимо подать заявку на непрерывное пространство памяти для сохранения элементов, и вы можете напрямую найти логическое расположение элемента через физическое расположение в памяти. Вставка или удаление элемента в середине таблицы последовательности требует перемещения всех элементов после элемента вперед или назад.
- Двусвязный список: нет необходимости обращаться к непрерывному пространству памяти для сохранения элементов, и вам нужно найти элементы-предшественники и элементы-последователи через указатели начала и конца элементов (при поиске элементов вам нужно пройти весь связанный список с начала или с конца, пока не будет найден целевой элемент). Вставка или удаление элементов в двусвязном списке не требует перемещения элементов, а требует только изменения указателей начала и конца связанных элементов.
Поэтому мы подсознательно думаем: поиск в ArrayList быстрый, добавления и удаления медленные. Поиск в LinkedList медленный, добавление и удаление быстрое. Но так ли это на самом деле? Мы вместе смотрим.
тестовая программа
Код тестовой программы в принципе не питательный, поэтому я не буду выкладывать его здесь, но я должен выложить результаты работы программы для удобства анализа один за другим.
результат операции
Вставка 100000 элементов в конец ArrayList занимает 26 мс.
Вставка 100000 элементов в конец LinkedList занимает много времени: 28 мс.
Вставка 100000 элементов в заголовок ArrayList занимает 859 мс: 859 мс
Вставка 100 000 элементов в заголовок LinkedList занимает 15 мс.
Вставка 100000 элементов в середину ArrayList занимает 1848 мс.
Вставка 100000 элементов в середину LinkedList занимает 15981 мс.
Длительность чтения 100 000 элементов в заголовке ArrayList: 7 мс.
Время, затраченное на чтение 100000 элементов в заголовке LinkedList: 11 мс.
Чтение 100 000 элементов в конце ArrayList занимает много времени: 12 мс.
Требуется много времени для чтения 100000 элементов в конце LinkedList: 9 мс
Чтение 100 000 элементов в середине ArrayList занимает много времени: 13 мс.
Время чтения 100000 элементов в LinkedList: 11387 мс
Вставка хвоста ArrayList
исходный код
метод add(E e)
public boolean add(E e) {
// 检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 直接在尾部添加元素
elementData[size++] = e;
return true;
}
Видно, что хвост ArrayList можно вставить напрямую без дополнительных операций.
Вставка конца LinkedList
исходный код
Головные и хвостовые узлы определены в LinkedList.
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
метод add(E e), который вызывает метод linkLast(E e)
public boolean add(E e) {
linkLast(e);
return true;
}
В методе linkLast(E e) видно, что при вставке в конец нет необходимости проходить весь связанный список с начала, потому что конечный узел был сохранен заранее, поэтому элементы можно вставлять напрямую после конечного узла.
/**
* Links e as last element.
*/
void linkLast(E e) {
// 先把原来的尾结点保存下来
final Node<E> l = last;
// 创建一个新的结点，其头结点指向last
final Node<E> newNode = new Node<>(l, e, null);
// 尾结点置为newNode
last = newNode;
if (l == null)
first = newNode;
else
// 修改原先的尾结点的尾结点，使其指向新的尾结点
l.next = newNode;
size++;
modCount++;
}
Суммировать
Для вставки хвоста производительность ArrayList и LinkedList почти одинакова.
Вставка заголовка ArrayList
исходный код
add(int index, E element) вы можете увидеть, что элемент перемещается, вызвав системный метод копирования массива. Следовательно, чем раньше позиция вставки, тем больше элементов нужно переместить.
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 把原来数组中的index位置开始的元素全部复制到index+1开始的位置（其实就是index后面的元素向后移动一位）
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 插入元素
elementData[index] = element;
size++;
}
Вставка заголовка LinkedList
исходный код
add(int index, E element), этот метод сначала оценивает, вставлен ли он в конец, если он вызывает метод linkLast(), в противном случае вызывает linkBefore(), то действительно ли ему нужно начинать обход с самого начала? Давайте посмотрим вместе
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Чтобы вставить элемент в позицию, отличную от головы и хвоста, конечно, вы должны узнать, где находится позиция.Метод node() является ключевым.Функция этой функции состоит в том, чтобы найти элемент по индексу , но он сначала определит положение индекса.Если индекс больше, чем Если половина размера (размер >> 1, операция сдвига вправо, эквивалентная делению на 2) меньше, он будет проходить с самого начала. В противном случае траверс из хвоста. Известно, что для LinkedList чем ближе положение рабочего элемента к середине, тем ниже эффективность.
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Работа этой функции состоит только в том, чтобы вставить элемент в соответствующую позицию.Ключевая работа была сделана в методе node().
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Суммировать
- Для LinkedList временная сложность вставки головы и вставки хвоста составляет O (1)
- Но для ArrayList каждая вставка головы должна перемещать элементы размером 1, эффективность можно представить
- Но если все они вставлены в среднюю позицию, скорость ArrayList почти в 10 раз выше, чем у LinkedList.
ArrayList, поиск в LinkedList
- Об этом и говорить нечего, для ArrayList, где бы ни была позиция, элемент находится сразу по индексу, а временная сложность O(1)
- Для поиска в LinkedList основным методом является метод node(), упомянутый выше, поэтому скорость поиска головы и хвоста чрезвычайно высока, а эффективность тем ниже, чем ближе вы подходите к середине.
Не по теме
Это мой первый блог о Наггетс, и я надеюсь поделиться с вами некоторыми интересными знаниями в будущем!