Java-LinkList медленнее, чем Arraylist при добавлении элементов?

Question

я думал, что связанные списки должны были быть быстрее, чем массив при добавлении элементов? я только что проверил, сколько времени занимает добавление, сортировка и поиск элементов (arraylist vs connectedlist vs hashset). я просто использовал классы java.util для массива и связанного списка ... используя оба метода add (object), доступных для каждого класса.

arraylist из выполненного связанного списка при заполнении списка ... и при линейном поиске списка.

это правильно? я сделал что-то не так в реализации, может быть?

************** * EDIT ************ *****

Я просто хочу убедиться, что я правильно использую эти вещи. вот что я делаю:

public class LinkedListTest {

    private List<String> Names;

    public LinkedListTest(){
            Names = new LinkedList<String>();
    }

Тогда я просто использовал методы связного списка, т.е. "Names.add (strings)". И когда я проверял arraylists, это почти идентично:

public class ArrayListTest {

    private List<String> Names;

    public ArrayListTest(){
            Names = new ArrayList<String>();
    }

Я правильно делаю?

Answer 1

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

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

Когда вы планируете вставлять только в конце List, ArrayList является вариантом выбора.

Answer 2

Помните, что:

• есть разница в производительности "raw" для данного количества элементов и в том, как различаются структуры scale ;
• разные структуры работают по-разному в разных операциях, и это, по сути, является частью того, что вам необходимо учитывать при выборе структуры для использования.

Так, например, связанный список имеетбольше нужно добавить в конец, потому что у него есть дополнительный объект для выделения и инициализации для каждого добавленного элемента, но независимо от этой «внутренней» стоимости за элемент, обе структуры будут иметь производительность O (1) для добавления в конец спискат. е. иметь фактически «постоянное» время на добавление независимо от размера списка, но эта константа будет отличаться между ArrayList и LinkedList и, вероятно, будет больше для последнего.

С другой стороны, связанныйlist имеет постоянное время для добавления в начало списка, тогда как в случае ArrayList элементы должны быть«перемещаемая» вдоль, операция, которая занимает некоторое время, пропорциональное количеству элементов.Но для заданного размера списка, скажем, 100 элементов, все еще может быть быстрее "замешать" 100 элементов, чем выделять и инициализировать один объект-заполнитель из связанного списка (но к тому времени, когда вы, скажем,тысяча или миллион объектов или какой бы то ни было порог, это не будет).

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

Answer 3

Связанный список может быть медленнее, чем список массивов в этих случаях по нескольким причинам.Если вы вставляете в конец списка, вполне вероятно, что в списке массивов это место уже выделено.Базовый массив обычно увеличивается большими кусками, потому что это очень трудоемкий процесс.Таким образом, в большинстве случаев для добавления элемента в конец требуется только вставка ссылки, в то время как связанный список требует создания узла.Добавление в начало и в середину должно дать различную производительность для обоих типов списка.

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

Answer 4

Почему вы думаете, LinkedList будет быстрее?В общем случае вставка в список массивов - это просто случай обновления указателя на одну ячейку массива (с O (1) произвольным доступом).Вставка LinkedList также является произвольным доступом, но она должна выделять объект «ячейка» для хранения записи и обновлять пару указателей , а также , в конечном итоге устанавливая ссылку на вставляемый объект.

Конечно, периодически может потребоваться изменение размера резервного массива ArrayList (что не будет иметь место, если он был выбран с достаточно большой начальной емкостью), но, поскольку массив растет экспоненциально, амортизируемая стоимость будет низкой, иограничен O(lg n) сложностью.

Проще говоря - вставка в списки массивов намного проще и, следовательно, намного быстрее в целом.

Answer 5

При добавлении элемента в конец списка LinkedList (в Java список LinkedList на самом деле является двусвязным списком), это операция O(1), так же как и добавление элемента в начало.Добавление элемента в позицию i является операцией * 1003. *

Так что, если вы добавляете в начало списка, LinkedList будет значительно быстрее.

Answer 6

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

РЕДАКТИРОВАТЬ: нет ли реализации связного списка, которая помнит последний элемент?Выполнение этого таким образом ускорит вставку в конце, используя связанный список.