LinkedList против ArrayList
Прежде чем мы сравним LinkedList и Arraylist, мы увидим, когда нам следует использовать реализацию списка в java. Список можно использовать для хранения данных по порядку (порядок вставки) и для хранения повторяющихся объектов. Итак, что список может сделать? В основном он может добавлять элементы или удалять элементы. Давайте посмотрим, как ArrayList и LinkedList выполняют эти операции.
ArrayList
ArrayList был реализован с использованием динамического массива. Что это значит? В java мы знаем, что длина массива фиксирована. Но в ArrayList просто представьте, что у нас есть обычный массив, и мы вставляем некоторые элементы в обычный массив, и есть способ вернуть другой массив с тем же именем. Итак, у нас есть массив, мы помещаем некоторые данные в массив, он дает новый массив с тем же именем. Аналогичный процесс произошел при удалении элементов из ArrayList. Аналогично, этот массив можно изменить динамически. Это простое значение того, как работает динамический массив. Когда новый элемент добавляется (кроме конца ArrayList) в ArrayList, все элементы справа от нового элемента должны быть смещены вправо.
Возьмем ArrayList из 6 элементов
Давайте добавим элемент во второй индекс
добавить(2", новый")
Что теперь произошло? ” new приходят к индексу 2. Все остальные значения справа от индекса 2 должны быть смещены вправо.
Вы можете видеть здесь, что мы добавили один элемент, но 4 элемента были смещены вправо. Если у него было 1000 элементов после индекса 2, все они должны быть добавлены справа.
Посмотрим, что получилось удалить элемент
удалить(2)
При удалении элемента индекса 2 все элементы справа от индекса 2 должны быть смещены влево.
Связанный список
LinkedList реализован с использованием интерфейсов List и Deque. В LinkedList есть средства для добавления элементов как в начале, так и в конце в постоянное время. Каждый узел LinkedList имеет два специальных узла, называемых предыдущим узлом и следующим узлом. Что произошло при добавлении нового элемента в LinkedList, так это его предыдущая ссылка, указывающая на левый узел нового узла, и следующая ссылка, указывающая слева от нового узла.
Возьмем LinkedList с 6 узлами.
Добавим новый узел.
добавить (2", новый)
Понятно, что в стадии находятся только три узла. Другие узлы не затрагиваются при добавлении нового узла (элемента). Хотя, если у нас есть 1000 узлов, изменяются только два узла из существующего списка.
Поскольку LinkedList реализовал интерфейсы List и deque, он предоставляет некоторые дополнительные функции для добавления данных, такие как addFirst(), addLast().
Когда мы удаляем элемент в LinkedList, соединяются только его левый и правый узлы. Это не влияет на другие узлы. Поскольку LinkedList реализовал deque, он предоставляет некоторые дополнительные функции, чем ArrayList, такие как deleteFirst() , deleteLast().
Сравнение элементов чтения (получения) из ArrayList и LinkedList
Мы уже знаем, что ArrayList был реализован с использованием динамического массива. Таким образом, ArrayLists имеет поведение массивов и базы индексов. Когда мы читаем данные из ArrayList, он просто проверяет индекс и выдает значение, что обычно занимает O(1) раз.
Как LinkedList выполняет это?
LinkedList не основан на индексах, основанных на узлах (цепочке узлов). Поэтому чтение значений занимает больше времени, чем ArrayList. Почему, потому что узлы не имеют индексов в связанных списках (можно вызывать значения с помощью get (index), но это логические индексы, а не индексы массива). Предположим, нам нужно прочитать данные индекса N, тогда нам нужно начать с головного узла и перейти по списку N раз требуется O(N) раз.
летний
- И в ArrayList, и в LinkedList реализован интерфейс списка.
- LinkedList также реализовал deque.
- LinkedList предоставляет дополнительные функции для вставки и удаления данных, такие как addFirst(), removeFirst().
- LinkedList лучше использовать, если мы используем для добавления и удаления операций больше, чем для чтения данных из списка.
- ArrayList лучше использовать, если нам нужно часто читать данные из списка.
