Глава 2. List — списки в Java
Интерфейс List и его особенности
В мире программирования, и в Java в частности, необходимость хранить и управлять наборами данных — одна из самых частых задач. Начинающие разработчики знакомы с массивами — простыми и эффективными, но обладающими серьезным недостатком: их размер фиксирован после создания. Что же делать, если количество элементов заранее неизвестно? На помощь приходит интерфейс List (список), который является одной из краеугольных концепций в Java Collections Framework (фреймворке коллекций Java).
Что такое интерфейс List?
List — это интерфейс, который расширяет более общий интерфейс Collection. Если говорить просто, List — это контракт, который обещает определенное поведение для всех классов, которые его реализуют. Сам по себе List не является классом, поэтому вы не можете создать объект типа «List». Он лишь определяет «правила игры», а конкретные классы, такие как ArrayList или LinkedList, уже следуют этим правилам, реализуя функционал по-своему.
Главная идея List — это упорядоченная последовательность. Это его ключевая особенность, отличающая его от других коллекций, например, Set (множества).
Ключевые особенности интерфейса List
Гарантированный порядок элементов.
Это самый важный принцип. Когда вы добавляете элементы в список, система запоминает именно ту последовательность, в которой вы их добавили. Элемент «A», добавленный первым, всегда будет находиться на позиции 0 (если только его не удалили или не переместили). Элемент «B», добавленный вторым, будет на позиции 1, и так далее. Этот порядок сохраняется на протяжении всей жизни списка (если только вы сами его не измените). Это кардинально отличает список от, например, мешка с яблоками, где порядок не важен.
Доступ по индексу.
Благодаря строгому порядку, List предоставляет возможность работать с элементами по их целочисленному индексу (позиции). Индексация всегда начинается с 0, как и в массивах. Вы можете «спросить» список: «Дай мне элемент, который находится на пятой позиции», и он его вернет. Эта операция является одной из базовых и высокооптимизированной в большинстве реализаций списков.
Допустимость дубликатов.
В отличие от множеств (Set), которые гарантируют уникальность своих элементов, список совершенно спокойно относится к повторяющимся значениям. Вы можете добавить одну и ту же строку «Привет» в список десять раз, и все десять копий будут храниться в нем как самостоятельные элементы, занимая разные позиции.
Динамический размер.
В отличие от массива, список не имеет фиксированной длины. Он является динамической структурой данных. Когда вы создаете пустой список, он занимает немного памяти. При добавлении каждого нового элемента список самостоятельно заботится о том, чтобы для него хватило места, при необходимости выделяя дополнительную память «про запас». Это избавляет программиста от необходимости заранее знать точное количество элементов и вручную управлять памятью.
Null-допустимость.
Список разрешает хранение специального значения null, которое обозначает отсутствие объекта. Это означает, что вы можете добавить null в список в качестве валидного элемента. Однако с этим нужно быть осторожным, так как при попытке выполнить какие-либо операции с этим null-элементом (например, вызвать его метод) может быть выброшено исключение NullPointerException.
#Java #для_новичков #beginner #List
Интерфейс List и его особенности
В мире программирования, и в Java в частности, необходимость хранить и управлять наборами данных — одна из самых частых задач. Начинающие разработчики знакомы с массивами — простыми и эффективными, но обладающими серьезным недостатком: их размер фиксирован после создания. Что же делать, если количество элементов заранее неизвестно? На помощь приходит интерфейс List (список), который является одной из краеугольных концепций в Java Collections Framework (фреймворке коллекций Java).
Что такое интерфейс List?
List — это интерфейс, который расширяет более общий интерфейс Collection. Если говорить просто, List — это контракт, который обещает определенное поведение для всех классов, которые его реализуют. Сам по себе List не является классом, поэтому вы не можете создать объект типа «List». Он лишь определяет «правила игры», а конкретные классы, такие как ArrayList или LinkedList, уже следуют этим правилам, реализуя функционал по-своему.
Главная идея List — это упорядоченная последовательность. Это его ключевая особенность, отличающая его от других коллекций, например, Set (множества).
Ключевые особенности интерфейса List
Гарантированный порядок элементов.
Это самый важный принцип. Когда вы добавляете элементы в список, система запоминает именно ту последовательность, в которой вы их добавили. Элемент «A», добавленный первым, всегда будет находиться на позиции 0 (если только его не удалили или не переместили). Элемент «B», добавленный вторым, будет на позиции 1, и так далее. Этот порядок сохраняется на протяжении всей жизни списка (если только вы сами его не измените). Это кардинально отличает список от, например, мешка с яблоками, где порядок не важен.
Доступ по индексу.
Благодаря строгому порядку, List предоставляет возможность работать с элементами по их целочисленному индексу (позиции). Индексация всегда начинается с 0, как и в массивах. Вы можете «спросить» список: «Дай мне элемент, который находится на пятой позиции», и он его вернет. Эта операция является одной из базовых и высокооптимизированной в большинстве реализаций списков.
Допустимость дубликатов.
В отличие от множеств (Set), которые гарантируют уникальность своих элементов, список совершенно спокойно относится к повторяющимся значениям. Вы можете добавить одну и ту же строку «Привет» в список десять раз, и все десять копий будут храниться в нем как самостоятельные элементы, занимая разные позиции.
Динамический размер.
В отличие от массива, список не имеет фиксированной длины. Он является динамической структурой данных. Когда вы создаете пустой список, он занимает немного памяти. При добавлении каждого нового элемента список самостоятельно заботится о том, чтобы для него хватило места, при необходимости выделяя дополнительную память «про запас». Это избавляет программиста от необходимости заранее знать точное количество элементов и вручную управлять памятью.
Null-допустимость.
Список разрешает хранение специального значения null, которое обозначает отсутствие объекта. Это означает, что вы можете добавить null в список в качестве валидного элемента. Однако с этим нужно быть осторожным, так как при попытке выполнить какие-либо операции с этим null-элементом (например, вызвать его метод) может быть выброшено исключение NullPointerException.
#Java #для_новичков #beginner #List
👍2
Абстракция и полиморфизм
Одна из сильных сторон использования интерфейса List — принцип полиморфизма. В своем коде вы можете объявить переменную типа List, а затем присвоить ей любой объект, который реализует этот интерфейс.
Это позволяет писать гибкий и слабосвязанный код. Основная логика вашей программы, которая использует методы add, get, remove, будет работать с любой реализацией List. А вы, в зависимости от конкретных требований к производительности (например, если чаще нужен быстрый доступ по индексу или частое добавление в начало), можете легко подменить одну реализацию на другую, не переписывая весь код.
#Java #для_новичков #beginner #List
Одна из сильных сторон использования интерфейса List — принцип полиморфизма. В своем коде вы можете объявить переменную типа List, а затем присвоить ей любой объект, который реализует этот интерфейс.
List<String> myList; // Объявление переменной интерфейсного типа
myList = new ArrayList<>(); // Работаем с динамическим массивом
// ... позже в коде ...
myList = new LinkedList<>(); // Теперь работаем со связным списком
Это позволяет писать гибкий и слабосвязанный код. Основная логика вашей программы, которая использует методы add, get, remove, будет работать с любой реализацией List. А вы, в зависимости от конкретных требований к производительности (например, если чаще нужен быстрый доступ по индексу или частое добавление в начало), можете легко подменить одну реализацию на другую, не переписывая весь код.
#Java #для_новичков #beginner #List
👍2
Глава 2. List — списки в Java
Реализации: ArrayList и LinkedList. Сравнение производительности
ArrayList: динамический массив под капотом
Самая популярная и часто используемая реализация List. Её название раскрывает всю суть: ArrayList — это список, реализованный на основе массива.
Внутреннее устройство:
Массив как основа. Когда вы создаете ArrayList, внутри него создается обычный массив типа Object[] (или E[] после дженериков). Изначально этот массив имеет некоторый начальный размер (емкость, capacity), часто по умолчанию это 10 элементов.
Динамическое расширение.
Когда вы добавляете новый элемент с помощью add(), ArrayList проверяет, осталось ли место во внутреннем массиве.
Если место есть, элемент просто помещается в первую свободную ячейку elementData[size], и значение size увеличивается на 1. Это очень быстрая операция, comparable с работой с массивом.
Если массив полон, происходит следующее:
Создается новый массив большего размера. Стандартная логика увеличения — (старый_размер * 1.5) + 1.
Все элементы из старого массива копируются в новый.
Старый массив удаляется сборщиком мусора, а ссылка elementData начинает указывать на новый массив.
Только после этого новый элемент добавляется в конец.
Этот процесс пересоздания и копирования массива является относительно медленным, поэтому, если вы заранее знаете примерное количество элементов, лучше создать ArrayList с нужной начальной емкостью через конструктор new ArrayList<>(1000). Это позволит избежать или минимизировать количество операций расширения.
LinkedList: цепочка связанных элементов
LinkedList подходит к задаче иначе. Его название также прямо говорит о структуре: LinkedList — это связный список.
Внутреннее устройство:
Узлы (Node). LinkedList не использует массив. Вместо этого он построен на основе узлов.
Каждый узел — это самостоятельный объект, который хранит три вещи:
Сам элемент (например, строку или число).
Ссылку на следующий узел (next).
Ссылку на предыдущий узел (prev).
Двусвязность. LinkedList в Java является двусвязным списком. Это означает, что он хранит ссылки как на следующий, так и на предыдущий элемент. Благодаря этому можно легко перемещаться по списку как от начала к концу, так и от конца к началу.
Отсутствие массива. Элементы не хранятся в непрерывной области памяти. Они разбросаны по куче (Heap), а связаны между собой лишь этими ссылками-«ниточками». Голова списка — это поле first, а хвост — last.
#Java #для_новичков #beginner #List #ArrayList #LinkedList
Реализации: ArrayList и LinkedList. Сравнение производительности
ArrayList: динамический массив под капотом
Самая популярная и часто используемая реализация List. Её название раскрывает всю суть: ArrayList — это список, реализованный на основе массива.
Внутреннее устройство:
Массив как основа. Когда вы создаете ArrayList, внутри него создается обычный массив типа Object[] (или E[] после дженериков). Изначально этот массив имеет некоторый начальный размер (емкость, capacity), часто по умолчанию это 10 элементов.
// Примерно так выглядит внутри ArrayList
public class ArrayList<E> {
private Object[] elementData; // Внутренний массив
private int size; // Текущее количество реальных элементов
// ...
}
Динамическое расширение.
Когда вы добавляете новый элемент с помощью add(), ArrayList проверяет, осталось ли место во внутреннем массиве.
Если место есть, элемент просто помещается в первую свободную ячейку elementData[size], и значение size увеличивается на 1. Это очень быстрая операция, comparable с работой с массивом.
Если массив полон, происходит следующее:
Создается новый массив большего размера. Стандартная логика увеличения — (старый_размер * 1.5) + 1.
Все элементы из старого массива копируются в новый.
Старый массив удаляется сборщиком мусора, а ссылка elementData начинает указывать на новый массив.
Только после этого новый элемент добавляется в конец.
Этот процесс пересоздания и копирования массива является относительно медленным, поэтому, если вы заранее знаете примерное количество элементов, лучше создать ArrayList с нужной начальной емкостью через конструктор new ArrayList<>(1000). Это позволит избежать или минимизировать количество операций расширения.
LinkedList: цепочка связанных элементов
LinkedList подходит к задаче иначе. Его название также прямо говорит о структуре: LinkedList — это связный список.
Внутреннее устройство:
Узлы (Node). LinkedList не использует массив. Вместо этого он построен на основе узлов.
Каждый узел — это самостоятельный объект, который хранит три вещи:
Сам элемент (например, строку или число).
Ссылку на следующий узел (next).
Ссылку на предыдущий узел (prev).
// Примерная структура узла
private static class Node<E> {
E item; // Данные
Node<E> next; // Ссылка на следующий узел
Node<E> prev; // Ссылка на предыдущий узел
// ...
}
Двусвязность. LinkedList в Java является двусвязным списком. Это означает, что он хранит ссылки как на следующий, так и на предыдущий элемент. Благодаря этому можно легко перемещаться по списку как от начала к концу, так и от конца к началу.
Отсутствие массива. Элементы не хранятся в непрерывной области памяти. Они разбросаны по куче (Heap), а связаны между собой лишь этими ссылками-«ниточками». Голова списка — это поле first, а хвост — last.
#Java #для_новичков #beginner #List #ArrayList #LinkedList
👍1
Сравнение производительности
Время выполнения операций принято описывать в нотации "Big O", которая показывает, как время работы растет с увеличением объема данных (n).
1. Доступ к элементу по индексу (get(index))
ArrayList: O(1) — константное время.
Это его сильнейшая сторона. Поскольку внутри обычный массив, чтобы получить элемент по индексу 5, система просто делает одну операцию: берет начальный адрес массива и смещается на 5 ячеек в памяти. Это происходит мгновенно, независимо от размера списка.
LinkedList: O(n) — линейное время.
Это его главный недостаток для данной операции. У списка нет индексов в памяти. Чтобы найти элемент с индексом 5, ему приходится начинать с начала (или с конца, если индекс ближе к нему) и последовательно переходить по ссылкам next (или prev).
Для доступа к первому или последнему элементу (get(0) или get(last)) скорость будет высокой O(1), так как есть прямые ссылки first и last. Но для элемента в середине — очень низкой.
2. Вставка элемента (add(element)) и удаление с конца
ArrayList: В среднем O(1), но в худшем случае O(n).
Добавление в конец (add(element)) обычно очень быстрое (O(1)), так как это запись в свободную ячейку. Однако, если массив полон, требуется дорогостоящая операция копирования всего массива (O(n)).
LinkedList: O(1) — константное время.
Добавление в конец всегда выполняется за константное время. Для этого нужно просто создать новый узел, сделать его prev ссылку на старый последний узел, и обновить ссылку last. Это несколько операций, но их количество не зависит от размера списка.
3. Вставка/удаление в произвольной позиции (add(index, element), remove(index))
ArrayList: O(n) — линейное время.
Это его слабое место. Представьте, что вы вставляете элемент в начало списка (индекс 0). ArrayList вынужден сдвинуть все существующие элементы на одну позицию вправо, чтобы освободить место для нового.
Эта операция arraycopy требует времени, пропорционального количеству сдвигаемых элементов (n). Удаление из начала/середины имеет ту же проблему, так как требует сдвига всех последующих элементов влево.
LinkedList: В среднем O(n), но само изменение ссылок — O(1).
Время операции здесь определяется не самим добавлением/удалением, а поиском нужной позиции. Как мы помним, поиск по индексу в LinkedList занимает O(n). Однако, как только узел найден, вставка или удаление выполняются очень быстро: нужно всего лишь поменять несколько ссылок у соседних узлов. Не нужно перемещать половину списка!
Поэтому, если у вас уже есть ссылка на узел (например, вы находитесь в середине итерации), вставка и удаление рядом с этим узлом будут исключительно быстрыми (O(1)).
Когда использовать ArrayList (в 95% случаев):
Когда преобладают операции чтения и получения элементов по индексу.
Когда вы в основном добавляете элементы в конец.
Когда память несколько критична, и вы хотите минимизировать overhead.
Когда использовать LinkedList:
Когда преобладают операции вставки и удаления в начале или середине списка, и при этом у вас нет частой необходимости в быстром доступе по индексу.
Когда вы активно используете структуры типа "стек" (LIFO) или "очередь" (FIFO) (хогда для этого есть более специализированные классы, как ArrayDeque).
#Java #для_новичков #beginner #List #ArrayList #LinkedList
Время выполнения операций принято описывать в нотации "Big O", которая показывает, как время работы растет с увеличением объема данных (n).
1. Доступ к элементу по индексу (get(index))
ArrayList: O(1) — константное время.
Это его сильнейшая сторона. Поскольку внутри обычный массив, чтобы получить элемент по индексу 5, система просто делает одну операцию: берет начальный адрес массива и смещается на 5 ячеек в памяти. Это происходит мгновенно, независимо от размера списка.
// Внутренняя логика ArrayList.get(index)
public E get(int index) {
// ... проверка индекса ...
return (E) elementData[index]; // Прямое обращение по индексу массива
}
LinkedList: O(n) — линейное время.
Это его главный недостаток для данной операции. У списка нет индексов в памяти. Чтобы найти элемент с индексом 5, ему приходится начинать с начала (или с конца, если индекс ближе к нему) и последовательно переходить по ссылкам next (или prev).
// Примерная логика (упрощенно). Чтобы найти узел с индексом 5:
Node<E> x = first;
for (int i = 0; i < 5; i++) { // Нужно сделать 5 итераций
x = x.next;
}
return x.item;
Для доступа к первому или последнему элементу (get(0) или get(last)) скорость будет высокой O(1), так как есть прямые ссылки first и last. Но для элемента в середине — очень низкой.
2. Вставка элемента (add(element)) и удаление с конца
ArrayList: В среднем O(1), но в худшем случае O(n).
Добавление в конец (add(element)) обычно очень быстрое (O(1)), так как это запись в свободную ячейку. Однако, если массив полон, требуется дорогостоящая операция копирования всего массива (O(n)).
LinkedList: O(1) — константное время.
Добавление в конец всегда выполняется за константное время. Для этого нужно просто создать новый узел, сделать его prev ссылку на старый последний узел, и обновить ссылку last. Это несколько операций, но их количество не зависит от размера списка.
3. Вставка/удаление в произвольной позиции (add(index, element), remove(index))
ArrayList: O(n) — линейное время.
Это его слабое место. Представьте, что вы вставляете элемент в начало списка (индекс 0). ArrayList вынужден сдвинуть все существующие элементы на одну позицию вправо, чтобы освободить место для нового.
// При вставке в середину/начало в ArrayList
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = newElement;
size++;
Эта операция arraycopy требует времени, пропорционального количеству сдвигаемых элементов (n). Удаление из начала/середины имеет ту же проблему, так как требует сдвига всех последующих элементов влево.
LinkedList: В среднем O(n), но само изменение ссылок — O(1).
Время операции здесь определяется не самим добавлением/удалением, а поиском нужной позиции. Как мы помним, поиск по индексу в LinkedList занимает O(n). Однако, как только узел найден, вставка или удаление выполняются очень быстро: нужно всего лишь поменять несколько ссылок у соседних узлов. Не нужно перемещать половину списка!
// Вставка `newNode` между `prevNode` и `currentNode`
newNode.prev = prevNode;
newNode.next = currentNode;
prevNode.next = newNode;
currentNode.prev = newNode;
Поэтому, если у вас уже есть ссылка на узел (например, вы находитесь в середине итерации), вставка и удаление рядом с этим узлом будут исключительно быстрыми (O(1)).
Когда использовать ArrayList (в 95% случаев):
Когда преобладают операции чтения и получения элементов по индексу.
Когда вы в основном добавляете элементы в конец.
Когда память несколько критична, и вы хотите минимизировать overhead.
Когда использовать LinkedList:
Когда преобладают операции вставки и удаления в начале или середине списка, и при этом у вас нет частой необходимости в быстром доступе по индексу.
Когда вы активно используете структуры типа "стек" (LIFO) или "очередь" (FIFO) (хогда для этого есть более специализированные классы, как ArrayDeque).
#Java #для_новичков #beginner #List #ArrayList #LinkedList
👍1