Чем отличается arraylist от vector

Обновлено: 05.07.2024

В этой статье мы рассмотрим, в чем разница между ArrayList и LinkedList в Java. Мы сравним их код и производительность, чтобы подчеркнуть различие.

Вступление

Списки-это некоторые из наиболее часто используемых структур данных. В Java распространенным вопросом при использовании реализации List является:

Какую реализацию я использую?

Следует ли вам выбрать ArrayList или Связанный список ? В чем разница между этими двумя?

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

Обзор списков на Java

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

Список s часто идет рука об руку с другими механизмами, такими как потоки Java, которые предлагают простые, но эффективные способы итерации, фильтрации, сопоставления и других полезных операций.

В Java List является интерфейсом в пакете java.util . Поскольку это интерфейс, он просто предоставляет список методов, которые необходимо переопределить в реальном классе реализации.

ArrayList и LinkedList являются двумя различными реализациями этих методов. Однако LinkedList также реализует интерфейс Очередь|/.

Внутренняя работа ArrayList и LinkedList

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

Связанный список содержит не массив, а двустороннюю очередь взаимосвязанных элементов. Первый элемент указывает на второй, который указывает на третий и так далее. Поскольку это дважды -связанный список, каждый элемент также указывает на своего предшественника. Пятый элемент, например, указывает как на четвертый элемент, так и на шестой элемент.

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

Чтобы сохранить элемент B , недостаточно просто сохранить его значение, как это было бы с ArrayList .

Указатель на предыдущий и следующий элементы также необходим для того, чтобы связанный список можно было обойти. Таким образом, вся структура списка состоит из взаимосвязанных узлов. Каждый узел содержит свой элемент и два указателя: ссылку на предыдущий узел и ссылку на следующий узел. У первого узла нет предыдущего узла, а у последнего узла нет следующего узла.

Наконец, в случае связанного списка мы можем предположить существование двух указателей, которые непрерывно отслеживают первый и последний элементы списка. Первый указатель, head , указывает на первый элемент и обновляется всякий раз, когда в начале вставляется новый элемент. Второй указатель, tail , указывает на последний элемент и аналогично обновляется всякий раз, когда в конце добавляется новый элемент.

Сравнение реализаций ArrayList и LinkedList

Извлечение Элементов С Помощью get()

Если кто-то хочет извлечь элемент из ArrayList с помощью метода get(индекс int) , реализация может просто делегировать эту задачу своему внутреннему массиву:

Конечно, выполняется дополнительная проверка данного индекса (убедитесь, что он не меньше нуля или больше размера массива).

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

Слот для второго элемента расположен точно после первого, а слот для n -го элемента расположен точно перед n+1 -т. е. Опираясь на эту внутреннюю структуру, любой элемент может быть легко извлечен по индексу.

Список ссылок.get()

Ранее мы упоминали, что связанный список не существует в одном месте в памяти, а содержит разные узлы, соединенные друг с другом. Чтобы извлечь элемент, список необходимо просмотреть с начала (или до конца, в зависимости от того, что ближе) и следовать соединениям каждого узла, пока не будет найден нужный элемент.

Реализация того же метода выглядит следующим образом:

Во-первых, производится проверка, чтобы убедиться, что индекс не 0 или выше размера Связанного списка . Затем метод node() проходит по списку, пока не встретит тот, который мы ищем.

Вставка Элементов С Помощью add()

Если элемент необходимо вставить в начале, метод может быть вызван с индексом 0 . Если элемент необходимо вставить в конец, индекс будет соответствовать текущему размеру списка. Если элемент нужно вставить где-то посередине, то пользователь должен указать этот индекс.

ArrayList.добавить()

Вставка элемента в конце довольно проста, особенно для такой структуры, как ArrayList . Вы просто увеличиваете длину на единицу и вставляете элемент в конце:

Чем больше скопированная часть, тем медленнее выполняется эта операция. Это делает добавление элементов в ArrayList относительно неэффективной операцией. Тем не менее, добраться до точки, где должна быть выполнена вставка, действительно эффективно.

Список ссылок.добавить()

Реализация LinkedList позволяет нам довольно легко добавлять элементы в любой заданный индекс. Вы просто указываете указатели head и tail предыдущего и последующего элементов на новый, соответственно. Если вы вставляете в начале или в конце списка, необходимо обновить только один указатель.

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

Давайте взглянем на реализацию:

В качестве альтернативы, если мы указываем индекс, то вызываются как linkLast () , так и ссылка перед() :

Независимо от того, насколько велик список, нужно изменить только два указателя. Это делает добавление элементов в Связанный список высокоэффективной операцией. Однако достижение позиции, в которую должен быть вставлен элемент, является неэффективным.

Поиск Элементов С индексом()

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

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

ArrayList.indexOf()

В реализации ArrayList это делается с помощью простого для цикла, идущего от 0 в размер-1 и проверка соответствия элемента текущего индекса заданному значению:

Это буквально линейный поиск, который не очень эффективен, но на самом деле это единственный способ поиска элемента в перетасованной коллекции (если мы игнорируем метаэвристические алгоритмы и приближения).

Список ссылок.индекс()

Удаление Элементов С Помощью Функции удалить()

ArrayList.удалить()

Очень похоже на добавление элементов в заданный индекс, для их удаления требуется ArrayList , чтобы скопировать часть самого себя и повторно инициализировать массив без значения, переместив скопированную часть влево:

Чем больше скопированная часть, тем медленнее выполняется эта операция. Опять же, это делает удаление элементов из ArrayList неэффективной операцией. Хотя, хорошая вещь в ArrayList s заключается в том, что вы можете очень легко добраться до этого элемента. elementData(индекс) возвращает элемент, который вы хотите удалить в O(1) время.

Список ссылок.удалить()

Это делает операцию удаления элементов из Связанного списка эффективной, поскольку, опять же, необходимо изменить только несколько пунктов. Хотя, чем длиннее список, тем больше времени потребуется, чтобы добраться до элемента, который необходимо удалить, так как мы не можем получить доступ к элементам через их индекс.

Сравнение Производительности

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

В этом разделе мы кратко сравним две реализации с точки зрения производительности:

Кредиты: Миро Медиум

Сравнение get()

Мы видим, что извлечение элементов из списка всегда O(1) для ArrayList .

Для Связанного списка выбор первого или последнего элемента равен O(1) , потому что в нем всегда есть указатели на эти два элемента. Нет необходимости в дополнительной логике обхода. Однако извлечение любого другого элемента-это O(N) , потому что мы не можем просто получить к ним доступ через индекс.

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

Сравнение вставки()

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

Сложность Связанного списка будет O(1) как для вставки в начале, так и в конце. Еще раз, это связано с указателями head и tail , которые можно использовать для мгновенной вставки элемента в любую из этих двух позиций.

LinkedList сложность вставки посередине составляет O(N) , такая же, как для ArrayList . Операция вставки действительно эффективна, но чтобы добраться до этой точки, она должна пройти все предыдущие элементы.

Как правило, вставка элементов выполняется одинаково как в ArrayList , так и в Связанном списке , если вы в основном не работаете с первым и последним элементами.

Сравнение удалить()

LinkedList s имеют O(1) сложность для удаления с начала или конца и O(N) в других случаях.

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

Вывод

ArrayList и LinkedList являются двумя различными реализациями интерфейса List|/. У них есть свои различия, которые важно понимать, чтобы правильно их использовать.

Какая реализация должна использоваться, зависит от конкретных вариантов использования. Если элементы будут часто извлекаться, нет смысла использовать LinkedList , так как извлечение происходит медленнее по сравнению с ArrayList . С другой стороны, если требуются вставки с постоянным временем или если общий размер заранее неизвестен, то предпочтительнее LinkedList .

Рост данных

Внутри, как ArrayList, так и Vector удерживают их содержимое с помощью массива. Оба могут расти и сжиматься динамически, чтобы поддерживать оптимальное использование хранилища, однако способ изменения размеров отличается. ArrayList создается с начальным размером по умолчанию 10. Если этот размер превышен, коллекция автоматически увеличивается до половины размера по умолчанию, равным 15. Векторные приращения 100% означают удвоение размера массива, если общее количество элементов превышает его емкость ,

Git Essentials

Давайте взглянем на реализацию:

В качестве альтернативы, если мы указываем индекс, то вызываются как linkLast () , так и ссылка перед() :

Поиск Элементов С индексом()

ArrayList.indexOf()

Список ссылок.индекс()

Удаление Элементов С Помощью Функции удалить()

ArrayList.удалить()

Список ссылок.удалить()

Сравнение Производительности

В этом разделе мы кратко сравним две реализации с точки зрения производительности:

Кредиты: Миро Медиум

Сравнение get()

Мы видим, что извлечение элементов из списка всегда O(1) для ArrayList .

Сравнение вставки()

Сравнение удалить()

LinkedList s имеют O(1) сложность для удаления с начала или конца и O(N) в других случаях.

Вывод

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

ArrayList дает лучшую производительность, так как он не синхронизирован. Операции с вектором дают низкую производительность, так как они потокобезопасны, поток, который работает на Vector, получает блокировку, которая заставляет другой поток ждать, пока блокировка не будет выпущена. Это означает, что в ArrayList два или более потока могут одновременно обращаться к коду, а Vector ограничено одним потоком за раз.

Перемещение (Итератор)

Элементы ArrayList можно перемещать с помощью Iterator, ListIterator и с использованием обычного или расширенного цикла. Vector использует интерфейс Enumeration для перемещения элементов.

2. В чем разница?

Для быстрого начала давайте представим ключевые различия ArrayList и Vector. Затем мы обсудим некоторые моменты более подробно:

синхронизация – первое существенное различие между этими двумя. Вектор синхронизирован, а ArrayList нет.
рост размера – Еще одно различие между ними заключается в том, как они изменяют размер при достижении своей емкости. | Векторудваивает свой размер. Напротив,ArrayListувеличивается только на половину своей длиныитерация – И
Вектор может использоватьИтераториПеречислениедля обхода элементов.С другой стороны, ArrayList может использовать только Итератор . производительность – В основном из-за синхронизации,
Вектор операции выполняются медленнее по сравнению с Список объектов фреймворк – Кроме того,
ArrayList является частью фреймворка коллекций и был представлен в JDK 1.2. Между тем, Вектор присутствует в более ранних версиях Java как устаревший класс.

Однако эти классы имеют существенные различия в своих реализациях.

Каковы различия между ArrayList и Vector в Java?

Java ArrayList и Vector реализуют интерфейс List и поддерживают порядок вставки. Но между ArrayList и Vector есть некоторые отличия.

Вектор синхронизируется по умолчанию, а ArrayList - нет.

Что такое синхронизация?

Когда мы запускаем два или более потока внутри программы, может возникнуть ситуация, когда несколько потоков пытаются получить доступ к одному и тому же ресурсу, и, наконец, они могут создать непредвиденный результат из-за проблем с параллелизмом. Синхронизированное ключевое слово заставляет поток получать блокировку при вводе метода, так что только один поток может выполнить метод в одно и то же время. Обычно это называется созданием класса потокобезопасным. Без синхронизации не гарантируется, в каком порядке происходит чтение и запись, возможно, оставляя переменную с мусором.

То, что означает это (Синхронизация), состоит в том, что только один поток может вызывать методы по Vector за раз, и есть небольшие накладные расходы при приобретении блокировки. Важно отметить, что вы можете заставить ArrayList также синхронизироваться, передав объект arraylist методу Collections.synchronizedList().

3. Вектор

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

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

Мы можем создать вектор типичным способом:

Конструктор по умолчанию создает пустой Вектор с начальной емкостью 10.

Давайте добавим несколько значений:

И, наконец, давайте пройдемся по значениям с помощью интерфейса итератора:

Или мы можем пересечь Вектор , используя Перечисление :

Теперь давайте более подробно рассмотрим некоторые из их уникальных особенностей.

6. Краткое изложение

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

5. Производительность

Как мы уже обсуждали выше, Вектор синхронизируется, что оказывает прямое влияние на производительность .

Чтобы увидеть разницу в производительности между операциями Vector и ArrayList , давайте напишем простой тест JMH/|.

В прошлом мы рассматривали временную сложность операций Arraylist , поэтому давайте добавим тестовые примеры для Vector.

Сначала , давайте протестируем метод get() :

Мы настроим JMH на использование трех потоков и 10 итераций прогрева.

И давайте сообщим о среднем времени на операцию на наносекундном уровне:

Теперь давайте сравним результаты операции contains() :

И распечатайте результаты:

Как мы видим, для операции contains() время выполнения Vector намного больше, чем ArrayList .

Наследство

Этот вектор не был частью структуры коллекции, позже он был включен в коллекции. Его можно считать устаревшим кодом. В коллекции Vector Collection ничего не может быть. Поэтому Vector следует избегать.

List vs ArrayList vs Vector

Хочу узнать в чём глобальная разница между ArrayList и Vector. Я поискал и нашёл только информацию о том,что вектор синхронизирован ( с чем?). Я не очень понял. Также не понимаю чем принципиальная разница List от ArrayList. Буду рад вашим пояснениям

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

4. Параллелизм

Мы уже упоминали, что ArrayList и Вектор отличаются друг от друга стратегией параллелизма, но давайте рассмотрим ее поближе. Если бы мы погрузились в сигнатуры вектора метода, мы бы увидели, что у каждого из них есть ключевое слово synchronized:

Проще говоря, это означает, что только один поток может одновременно получить доступ к заданному вектору .

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

Поэтому, напротив, ArrayList использует другой подход. Его методы не синхронизированы, и эта проблема разделена на классы, которые посвящены параллелизму.

Например, мы можем использовать CopyOnWriteArrayList или Коллекции.synchronizedList для получения эффекта, аналогичного векторному :

Читайте также: