предисловие

Утверждение, в этой статье используется jdk1.8

В предыдущей статье уже рассказывалось об обзоре Collection:Обзор коллекции, вводит некоторые основы.

Теперь в этой статье в основном рассказывается о трех подклассах коллекции List:

ArrayList
- Базовая структура данных представляет собой массив. поток небезопасен
LinkedList
- Базовая структура данных представляет собой связанный список. поток небезопасен
Vector
- Базовая структура данных представляет собой массив. потокобезопасность

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

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

Конечно, если что-то не так, пожалуйста, потерпите и поправьте меня в комментариях~

1. Анализ списка массивов

Прежде всего, давайте поговорим о коллекции ArrayList, которую мы часто используем~

Во-первых, давайте посмотрим на свойства ArrayList:

Из вышеизложенного мы можем ясно найти:Нижний слой ArrayList на самом деле является массивом., ArrayList имеетРасширениеТакая концепция из-за ее расширения можетДостижение «динамического» роста

1.2 Метод строительства

Давайте посмотрим на метод построения, чтобы подтвердить, что мы правы выше:

1.3Добавить метод

Можно сказать, что метод add является самым важным методом ArrayList, давайте рассмотрим его:

1.3.1add(E e)

шаг:

Проверьте, требуется ли расширение
вставить элемент

Во-первых, давайте посмотрим на этот метод:


    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

Метод очень короткий, и мы можем догадаться, что он делает, исходя из названия метода:

Подтвердите емкость списка, попробуйте добавить 1 к емкости и посмотрите, нужно ли это
добавить элемент

Далее посмотрим, соответствует ли эта небольшая емкость (+1) нашим потребностям:

тогда позвониensureExplicitCapacity()Чтобы определить явную емкость, давайте также посмотрим, как реализован этот метод:

Итак, давайте посмотримgrow()Как это случилось~

зайди и посмотриcopyOf()метод:

Пока что мы можем знатьadd(E e)Базовая реализация:

Во-первых, проверьте, достаточна ли емкость массива
- Достаточно: добавить напрямую
- Недостаточно: Расширение
  - Расширен в 1,5 раза по сравнению с оригиналом
  - После первого расширения, если емкость все еще меньше, чем minCapacity, емкость расширяется до minCapacity.

1.3.2add(int index, E element)

шаг:

Проверьте угловую метку
Проверка пробелов, расширение при необходимости
вставить элемент

Давайте посмотрим на реализацию вставки:

Мы обнаружили, что нижний слой метода добавления ArrayList, связанный с расширением, на самом делеarraycopy()достигать

Видетьarraycopy(), мы можем узнать:Метод написан на C/C++, не реализованный Java:

В целом:arraycopy()Это более надежный и эффективный метод.

Обратитесь к ответу R:Ууху. Call.com/question/53…

1.4 получить метод

Проверьте угловую метку
возвращаемый элемент




   // 检查角标
   private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
	
	// 返回元素
    E elementData(int index) {
        return (E) elementData[index];
    }

1,5 метод установки

шаг:

Проверьте угловую метку
альтернативный элемент
вернуть старое значение

1.6 метод удаления

шаг:

Проверьте угловую метку
удалить элемент
Подсчитайте количество ходов, которые нужно переместить, и переместите
Установите значение null, чтобы позволить Gc перерабатывать

1.7 Повторное описание деталей

ArrayList — этона основе динамического массива,существуетПри добавлении или удалении нужно скопировать массив.
Инициализированная емкость ArrayList по умолчанию равна 10, и при каждом расширении она увеличивается на половину исходной емкости, то есть становится в 1,5 раза больше исходной емкости.
Емкость не уменьшается при удалении элементов,Если вы хотите уменьшить емкость, вызовите функцию trimToSize().
Это не потокобезопасно. Он может содержать нулевые значения.

Использованная литература:

blog.CSDN.net/Пан Вэйвэй 19…
zhuanlan.zhihu.com/p/27878015

Во-вторых, разница между Vector и ArrayList

Vector — это класс jdk1.2, относительно старого класса коллекции.

Нижний слой Vector также представляет собой массив.Самое большое отличие от ArrayList заключается в следующем:Синхронизированный (потокобезопасный)

Вектор синхронен, это видно из метода~

В случае отсутствия синхронизации мы обычно используем ArrayList вместо Vector~

Если вы хотите, чтобы ArrayList достиг синхронизации, вы можете использовать метод Collections:List list = Collections.synchronizedList(new ArrayList(...));, вы можете добиться синхронизации ~

Есть еще одно отличие:

ArrayList расширяется в 0,5 раза на исходной основе, когда базового массива недостаточно, а Vector расширяется в 1 раз.,

Для анализа исходного кода Vector см.:

blog.CSDN.net/Пан Вэйвэй 19…
zhuanlan.zhihu.com/p/28241176

Три, анализ LinkedList

Нижний слой LinkedListДвусвязный список~ Если вы не знакомы со связанными списками, вы можете сначала взглянуть на мойОдносвязный список(Я еще не делал упражнение с двусвязным списком)【Java реализует односвязный список】

После понимания односвязного списка двусвязный список не представляет сложности.

Структурно мы также видимLinkedList реализует интерфейс Deque, так что мы можемУправление связными списками, например очередями и стеками~

Переменных LinkedList всего несколько, потому что мы также нашли их, когда работали с односвязным списком: с головным узлом мы можем получить другие данные. (То же верно и для двусвязных списков)

3.1 Метод строительства

Существует два метода построения LinkedList:

3.2 добавить метод

Если вы выполняли упражнения со связанными списками, вам знаком следующий код~

Метод add фактически добавляет элемент в конец связанного списка.


    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

3.3метод удаления

По сути, это операция следующего рисунка:

3.4 получить метод

Вы можете видеть, что метод get реализован в двух частях кода:

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

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

3.5установить метод

Метод set на самом деле похож на метод get.Определите, следует ли пройти с начала или с конца в соответствии с индексом


    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

...... Методов LinkedList гораздо больше, чем методов ArrayList, поэтому я не буду объяснять их здесь по отдельности. Для получения подробной информации см.:

blog.CSDN.net/Пан Вэйвэй 19…
zhuanlan.zhihu.com/p/24730576
zhuanlan.zhihu.com/p/28373321

4. Резюме

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

ArrayList, LinkedList и Vector являются общими точками знаний в вопросах интервью. Вот краткий обзор:

Список массивов:

Базовая реализация представляет собой массив
Инициализированная емкость ArrayList по умолчанию равна 10, и при каждом расширении она увеличивается на половину исходной емкости, то есть становится в 1,5 раза больше исходной емкости.
существуетПри добавлении или удалении требуется копирование и копирование массива (метод navite реализован на C/C++)

Связанный список:

Базовая реализацияДвусвязный список[Двусвязный список облегчает прямой обход]

Вектор:

Нижний слой — это массив, который сейчас используется реже и заменен ArrayList по двум причинам:
- Все методы Вектора синхронизированы,Есть штраф за производительность.
- Начальная длина вектора равна 10. Когда он превысит длину, он будет расти со скоростью 100%.Больше потребление памяти, чем ArrayList.
- Использованная литература:Ууху. Call.com/question/31…

В общем: ArrayList используется для запросов, а LinkedList — для добавления и удаления.

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

Если добавление элементов использовалосьadd()(добавлено в конец), тогда ArrayList быстрее
ВсегдаУдаление элементов в конце также выполняется быстрее для ArrayList.【Не копировать движущуюся позицию】
Что касается, еслиЕсли вы удалите среднюю позицию или ArrayList быстрее!

Но в целом:Добавляйте и удаляйте больше или используйте LinkedList, потому что описанная выше ситуация является экстремальной~

Проект с открытым исходным кодом, охватывающий все точки знаний о бэкэнде Java (уже 6 тысяч звезд):GitHub.com/Zhongf UC очень…

если ты хочешьв реальном времениЕсли вы обратите внимание на мои обновленные статьи и галантерейные товары, которыми я делюсь, поищите в WeChat.Java3y.

Содержимое PDF-документоввсе вручную, если вы ничего не понимаете, вы можете напрямуюспросите меня(В официальном аккаунте есть мои контактные данные).