Skip to content

задание

Урок 2. LinkedList Цель задания: Познакомиться с LinkedList, сформировать базовые навыки работы по реализации Linked List и Array List Задание: 1. Как реализуется Array List? 2. Как реализуется Linked List? 3. Сравните их реализации

1. Как реализуется ArrayList?

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

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

  • Увеличение размера: Обычно размер массива увеличивается в 1.5-2 раза, когда он заполняется. Это позволяет уменьшить количество операций копирования при добавлении элементов.

  • Индексация: Элементы доступны по индексу, что позволяет быстро получать доступ к элементам (время доступа O(1)).

  • Добавление и удаление: При добавлении элемента в конец списка, если массив не заполнен, операция выполняется за O(1). Однако, если необходимо увеличить размер массива, это займет O(n) из-за копирования элементов. Удаление элемента может занять O(n), так как элементы после удаляемого элемента должны быть сдвинуты.

2. Как реализуется LinkedList?

LinkedList в Java реализуется как двусвязный список. Каждый элемент списка представлен узлом, который содержит данные и ссылки на предыдущий и следующий узлы. Вот основные моменты реализации LinkedList:

  • Узлы: Каждый узел содержит три компонента: данные, ссылку на следующий узел и ссылку на предыдущий узел.

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

  • Добавление и удаление: Добавление и удаление узлов выполняется за O(1), если известна позиция (например, при добавлении в начало или конец списка). Однако доступ к элементам по индексу требует O(n), так как необходимо пройти по узлам списка.

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

Характеристика ArrayList LinkedList
Структура данных Динамический массив Двусвязный список
Доступ по индексу O(1) O(n)
Добавление в конец O(1) (в среднем), O(n) (при увеличении размера) O(1)
Удаление O(n) (при сдвиге элементов) O(1) (если известен узел)
Использование памяти Меньше памяти на элемент (только данные) Больше памяти на элемент (данные + 2 ссылки)
Итерация Быстрая, так как элементы хранятся в непрерывной памяти Может быть медленнее из-за разрозненности узлов
Сценарии использования Подходит для частого доступа по индексу и редкого добавления/удаления Подходит для частого добавления/удаления элементов

Заключение

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

пример

https://gitlab.com/synergy9980417/razdel1/6_2