LinkedList, отличие от ArrayList
LinkedList — это одна из реализаций интерфейса List в Java. Он представляет собой двусвязный список, где каждый элемент содержит ссылки на предыдущий и следующий элементы. LinkedList подходит для сценариев, где часто выполняются операции вставки и удаления элементов в середине списка.
Особенности LinkedList
Двусвязный список:
Каждый элемент в LinkedList содержит ссылки на предыдущий и следующий элементы, что позволяет эффективно добавлять и удалять элементы в середине списка.
Доступ к элементам:
В отличие от ArrayList, доступ к элементам в LinkedList осуществляется линейным поиском, что делает его менее эффективным для операций случайного доступа.
Итерация по элементам:
Поскольку элементы связаны ссылками, итерация по списку может быть выполнена с постоянным использованием памяти и временем для операций добавления и удаления.
Не синхронизированность:
Как и ArrayList, LinkedList не является потокобезопасной коллекцией. В многопоточных средах требуется внешняя синхронизация.
Отличие от ArrayList
Структура хранения:
ArrayList использует массив для хранения элементов, тогда как LinkedList использует двусвязный список.
Время доступа:
ArrayList обеспечивает быстрый доступ к элементам по индексу (O(1)), в то время как LinkedList требует линейного времени (O(n)) для доступа к элементам по индексу.
Вставка и удаление элементов:
Вставка и удаление элементов в середине списка эффективнее в LinkedList (O(1)), в то время как в ArrayList эти операции требуют сдвига элементов и выполняются за время O(n).
Емкость и размер:
В ArrayList размер массива увеличивается автоматически при добавлении элементов, что может привести к перераспределению памяти. LinkedList не имеет проблемы перераспределения памяти, так как элементы связаны ссылками.
Примеры использования
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://habr.com/ru/articles/127864/
https://javarush.com/groups/posts/1938-linkedlist
#Java #Training #Medium #LinkedList
LinkedList — это одна из реализаций интерфейса List в Java. Он представляет собой двусвязный список, где каждый элемент содержит ссылки на предыдущий и следующий элементы. LinkedList подходит для сценариев, где часто выполняются операции вставки и удаления элементов в середине списка.
Особенности LinkedList
Двусвязный список:
Каждый элемент в LinkedList содержит ссылки на предыдущий и следующий элементы, что позволяет эффективно добавлять и удалять элементы в середине списка.
Доступ к элементам:
В отличие от ArrayList, доступ к элементам в LinkedList осуществляется линейным поиском, что делает его менее эффективным для операций случайного доступа.
Итерация по элементам:
Поскольку элементы связаны ссылками, итерация по списку может быть выполнена с постоянным использованием памяти и временем для операций добавления и удаления.
Не синхронизированность:
Как и ArrayList, LinkedList не является потокобезопасной коллекцией. В многопоточных средах требуется внешняя синхронизация.
Отличие от ArrayList
Структура хранения:
ArrayList использует массив для хранения элементов, тогда как LinkedList использует двусвязный список.
Время доступа:
ArrayList обеспечивает быстрый доступ к элементам по индексу (O(1)), в то время как LinkedList требует линейного времени (O(n)) для доступа к элементам по индексу.
Вставка и удаление элементов:
Вставка и удаление элементов в середине списка эффективнее в LinkedList (O(1)), в то время как в ArrayList эти операции требуют сдвига элементов и выполняются за время O(n).
Емкость и размер:
В ArrayList размер массива увеличивается автоматически при добавлении элементов, что может привести к перераспределению памяти. LinkedList не имеет проблемы перераспределения памяти, так как элементы связаны ссылками.
Примеры использования
import java.util.LinkedList;
import java.util.List;
public class LinkedListExample {
public static void main(String[] args) {
List<String> linkedList = new LinkedList<>();
// Добавление элементов
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Cherry");
// Получение элемента
System.out.println("First element: " + linkedList.get(0)); // Apple
// Вставка элемента
linkedList.add(1, "Orange");
System.out.println("After insertion: " + linkedList); // [Apple, Orange, Banana, Cherry]
// Удаление элемента
linkedList.remove("Banana");
System.out.println("After removal: " + linkedList); // [Apple, Orange, Cherry]
// Итерация по элементам
for (String fruit : linkedList) {
System.out.println(fruit);
}
}
}
Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://habr.com/ru/articles/127864/
https://javarush.com/groups/posts/1938-linkedlist
#Java #Training #Medium #LinkedList
Хабр
Структуры данных в картинках. LinkedList
Приветствую вас, хабражители! Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java. В прошлый раз мы говорили об...
👍1
Внутреннее устройство и основные методы LinkedList
LinkedList основан на структуре данных двусвязного списка. Каждый элемент списка представлен узлом (Node), который содержит данные и ссылки на предыдущий и следующий узлы.
Класс Node:
Класс Node — это внутренний класс LinkedList, который представляет элемент списка.
Узлы:
LinkedList содержит ссылки на первый (first) и последний (last) узлы списка.
Добавление элементов:
При добавлении элемента в конец списка создается новый узел, и ссылки next и prev соответствующим образом обновляются.
Удаление элементов:
Удаление элемента включает обновление ссылок next и prev соседних узлов.
Поиск узла:
Для доступа к элементу по индексу необходимо пройти по списку от начала или конца в зависимости от того, ближе ли индекс к началу или концу списка.
Основные методы LinkedList
Добавление элементов:
add(E e): добавляет элемент в конец списка.
add(int index, E element): вставляет элемент по указанному индексу.
Удаление элементов:
remove(int index): удаляет элемент по указанному индексу.
remove(Object o): удаляет первое вхождение указанного элемента.
Получение элементов:
get(int index): возвращает элемент по указанному индексу.
getFirst(), getLast(): возвращают первый и последний элементы соответственно.
Другие методы:
size(): возвращает количество элементов в списке.
clear(): удаляет все элементы из списка.
contains(Object o): проверяет, содержится ли указанный элемент в списке.
#Java #Training #Medium #LinkedList
LinkedList основан на структуре данных двусвязного списка. Каждый элемент списка представлен узлом (Node), который содержит данные и ссылки на предыдущий и следующий узлы.
Класс Node:
Класс Node — это внутренний класс LinkedList, который представляет элемент списка.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}Узлы:
LinkedList содержит ссылки на первый (first) и последний (last) узлы списка.
transient Node<E> first;
transient Node<E> last;
Добавление элементов:
При добавлении элемента в конец списка создается новый узел, и ссылки next и prev соответствующим образом обновляются.
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++;
}Удаление элементов:
Удаление элемента включает обновление ссылок next и prev соседних узлов.
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}Поиск узла:
Для доступа к элементу по индексу необходимо пройти по списку от начала или конца в зависимости от того, ближе ли индекс к началу или концу списка.
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}Основные методы LinkedList
Добавление элементов:
add(E e): добавляет элемент в конец списка.
add(int index, E element): вставляет элемент по указанному индексу.
linkedList.add("Apple");
linkedList.add(1, "Orange");Удаление элементов:
remove(int index): удаляет элемент по указанному индексу.
remove(Object o): удаляет первое вхождение указанного элемента.
linkedList.remove(1);
linkedList.remove("Apple");
Получение элементов:
get(int index): возвращает элемент по указанному индексу.
getFirst(), getLast(): возвращают первый и последний элементы соответственно.
String first = linkedList.getFirst();
String element = linkedList.get(1);
Другие методы:
size(): возвращает количество элементов в списке.
clear(): удаляет все элементы из списка.
contains(Object o): проверяет, содержится ли указанный элемент в списке.
int size = linkedList.size();
linkedList.clear();
boolean containsApple = linkedList.contains("Apple");
#Java #Training #Medium #LinkedList
🔥2
Раздел 6. Коллекции в Java
Глава 4. Queue и Deque
Реализации: PriorityQueue, LinkedList как очередь. Применение: обработка задач, хранение заявок
Интерфейс Queue<E> имеет несколько реализаций в JCF, каждая оптимизирована под разные сценарии. Сегодня фокус на PriorityQueue и LinkedList (как Queue). Эти реализации демонстрируют разнообразие: от строгого FIFO до приоритетной обработки.
LinkedList<E> как Queue
LinkedList — это двусвязный список (doubly-linked list), который реализует Queue<E> (а также List<E> и Deque<E>). Как очередь, она идеальна для FIFO: добавление в конец, извлечение из начала.
Особенности:
FIFO: Строго соблюдается порядок добавления.
Уникальность: Нет, дубликаты разрешены.
Null: Разрешен (LinkedList позволяет null элементы).
Big O: O(1) для offer (добавление в конец), poll (извлечение из начала), peek (просмотр начала). Contains — O(n), так как перебор списка.
Внутренняя работа: Каждый элемент — узел (node) с ссылками на prev и next. Добавление — создание узла и обновление ссылок. Извлечение — удаление первого узла и сдвиг ссылок.
Нюансы:
Эффективна для частых вставок/удалений в концах (O(1)), но медленная для середины (O(n)).
Память: Выше, чем у ArrayDeque (из-за ссылок на prev/next).
Thread-safety: Нет — для многопоточности используйте BlockingQueue.
Дополнительно: Как Deque, поддерживает добавление/извлечение с обоих концов (об этом в следующем уроке).
Когда использовать: Для простых FIFO-очередей с небольшим размером, или когда нужна универсальность (Queue + List).
Пример кода для LinkedList как Queue:
PriorityQueue<E>
PriorityQueue — это приоритетная очередь на основе кучи (binary heap, min-heap по умолчанию). Она не следует FIFO, а извлекает элементы по приоритету (минимальный первый для натуральных типов).
Особенности:
FIFO: Нет — приоритетный порядок (по Comparable или Comparator).
Уникальность: Нет, дубликаты разрешены.
Null: Не разрешен (NullPointerException).
Big O: O(log n) для offer (вставка в кучу), poll (извлечение минимума с перестройкой), peek — O(1). Contains — O(n), так как перебор.
Внутренняя работа: Хранит элементы в массиве как бинарную кучу. При добавлении/извлечении перестраивает кучу (heapify) для поддержания свойства: родитель <= дети. Приоритет определяется compareTo() или Comparator.
Нюансы:
Порядок итерации: Не гарантирован (куча не sorted list).
Comparator: Передайте при создании: new PriorityQueue<>((a, b) -> b - a) для max-heap.
Размер: Resizable, initial capacity 11.
Thread-safety: Нет — используйте PriorityBlockingQueue для потоков.
Custom объекты: Должны реализовывать Comparable<E> или предоставить Comparator, иначе ClassCastException.
Когда использовать: Для задач с приоритетами (например, планировщик задач, Dijkstra алгоритм).
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
Глава 4. Queue и Deque
Реализации: PriorityQueue, LinkedList как очередь. Применение: обработка задач, хранение заявок
Интерфейс Queue<E> имеет несколько реализаций в JCF, каждая оптимизирована под разные сценарии. Сегодня фокус на PriorityQueue и LinkedList (как Queue). Эти реализации демонстрируют разнообразие: от строгого FIFO до приоритетной обработки.
LinkedList<E> как Queue
LinkedList — это двусвязный список (doubly-linked list), который реализует Queue<E> (а также List<E> и Deque<E>). Как очередь, она идеальна для FIFO: добавление в конец, извлечение из начала.
Особенности:
FIFO: Строго соблюдается порядок добавления.
Уникальность: Нет, дубликаты разрешены.
Null: Разрешен (LinkedList позволяет null элементы).
Big O: O(1) для offer (добавление в конец), poll (извлечение из начала), peek (просмотр начала). Contains — O(n), так как перебор списка.
Внутренняя работа: Каждый элемент — узел (node) с ссылками на prev и next. Добавление — создание узла и обновление ссылок. Извлечение — удаление первого узла и сдвиг ссылок.
Нюансы:
Эффективна для частых вставок/удалений в концах (O(1)), но медленная для середины (O(n)).
Память: Выше, чем у ArrayDeque (из-за ссылок на prev/next).
Thread-safety: Нет — для многопоточности используйте BlockingQueue.
Дополнительно: Как Deque, поддерживает добавление/извлечение с обоих концов (об этом в следующем уроке).
Когда использовать: Для простых FIFO-очередей с небольшим размером, или когда нужна универсальность (Queue + List).
Пример кода для LinkedList как Queue:
javaimport java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.offer("Задача 1"); // Добавление в конец
queue.offer("Задача 2");
queue.offer("Задача 3");
System.out.println(queue); // [Задача 1, Задача 2, Задача 3] — FIFO порядок
System.out.println(queue.peek()); // Задача 1 (просмотр)
System.out.println(queue.poll()); // Задача 1 (извлечение)
System.out.println(queue); // [Задача 2, Задача 3]
queue.offer(null); // Разрешен null
System.out.println(queue.poll()); // Задача 2
}
}
Вывод: Показывает FIFO — элементы извлекаются в порядке добавления, null разрешен.
PriorityQueue<E>
PriorityQueue — это приоритетная очередь на основе кучи (binary heap, min-heap по умолчанию). Она не следует FIFO, а извлекает элементы по приоритету (минимальный первый для натуральных типов).
Особенности:
FIFO: Нет — приоритетный порядок (по Comparable или Comparator).
Уникальность: Нет, дубликаты разрешены.
Null: Не разрешен (NullPointerException).
Big O: O(log n) для offer (вставка в кучу), poll (извлечение минимума с перестройкой), peek — O(1). Contains — O(n), так как перебор.
Внутренняя работа: Хранит элементы в массиве как бинарную кучу. При добавлении/извлечении перестраивает кучу (heapify) для поддержания свойства: родитель <= дети. Приоритет определяется compareTo() или Comparator.
Нюансы:
Порядок итерации: Не гарантирован (куча не sorted list).
Comparator: Передайте при создании: new PriorityQueue<>((a, b) -> b - a) для max-heap.
Размер: Resizable, initial capacity 11.
Thread-safety: Нет — используйте PriorityBlockingQueue для потоков.
Custom объекты: Должны реализовывать Comparable<E> или предоставить Comparator, иначе ClassCastException.
Когда использовать: Для задач с приоритетами (например, планировщик задач, Dijkstra алгоритм).
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
👍1
Пример кода для PriorityQueue:
Применение очередей: Обработка задач, хранение заявок
Очереди идеальны для сценариев последовательной обработки.
Обработка задач (Task Processing):
Пример: Планировщик задач, где задачи добавляются в очередь и обрабатываются по порядку (FIFO с LinkedList) или по приоритету (PriorityQueue).
Нюанс: В многопоточных системах (например, Thread pool) используйте BlockingQueue для безопасного poll.
Пример кода (простой обработчик):
Хранение заявок (Request Storage):
Пример: Сервер хранит входящие заявки в очередь для последовательной обработки (например, HTTP requests).
С PriorityQueue: Заявки по срочности (high-priority first).
Нюанс: Для реальных систем используйте BlockingQueue (offer/poll с блокировкой при пустой/полной).
Пример кода (приоритетные заявки):
Полезные советы для новичков
LinkedList для простоты: Универсальна для FIFO, легко добавить Deque-функции.
PriorityQueue для приоритетов: Передавайте Comparator для custom порядка (например, max-heap).
Custom классы: Реализуйте Comparable для PriorityQueue, или используйте Comparator.
Пустая очередь: Проверяйте isEmpty() перед poll, или используйте null от poll.
Итерация: For-each для просмотра, но не модифицируйте.
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
javaimport java.util.PriorityQueue;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.offer(1);
queue.offer(2);
System.out.println(queue); // [1, 3, 2] — min в начале, но итерация не sorted
System.out.println(queue.peek()); // 1 (минимальный)
System.out.println(queue.poll()); // 1
System.out.println(queue); // [2, 3]
// Max-heap с Comparator
Queue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);
maxQueue.offer(3);
maxQueue.offer(1);
maxQueue.offer(2);
System.out.println(maxQueue.poll()); // 3 (максимальный)
// queue.offer(null); // NPE
}
}
Вывод: Элементы извлекаются по приоритету, не по порядку добавления.
Применение очередей: Обработка задач, хранение заявок
Очереди идеальны для сценариев последовательной обработки.
Обработка задач (Task Processing):
Пример: Планировщик задач, где задачи добавляются в очередь и обрабатываются по порядку (FIFO с LinkedList) или по приоритету (PriorityQueue).
Нюанс: В многопоточных системах (например, Thread pool) используйте BlockingQueue для безопасного poll.
Пример кода (простой обработчик):
javaimport java.util.LinkedList;
import java.util.Queue;
public class TaskProcessor {
private Queue<String> tasks = new LinkedList<>();
public void addTask(String task) {
tasks.offer(task);
}
public void processTasks() {
while (!tasks.isEmpty()) {
String task = tasks.poll();
System.out.println("Обработка: " + task);
}
}
}
public class Main {
public static void main(String[] args) {
TaskProcessor processor = new TaskProcessor();
processor.addTask("Задача 1");
processor.addTask("Задача 2");
processor.processTasks(); // Обработка: Задача 1\nОбработка: Задача 2
}
}
Вывод: Задачи обрабатываются FIFO.
Хранение заявок (Request Storage):
Пример: Сервер хранит входящие заявки в очередь для последовательной обработки (например, HTTP requests).
С PriorityQueue: Заявки по срочности (high-priority first).
Нюанс: Для реальных систем используйте BlockingQueue (offer/poll с блокировкой при пустой/полной).
Пример кода (приоритетные заявки):
javaimport java.util.PriorityQueue;
import java.util.Queue;
class Request implements Comparable<Request> {
private String name;
private int priority; // 1 - высокий, 10 - низкий
public Request(String name, int priority) {
this.name = name;
this.priority = priority;
}
@Override
public int compareTo(Request other) {
return Integer.compare(this.priority, other.priority); // Min-heap по приоритету
}
public String getName() {
return name;
}
}
public class Main {
public static void main(String[] args) {
Queue<Request> requests = new PriorityQueue<>();
requests.offer(new Request("Заявка A", 5));
requests.offer(new Request("Заявка B", 1)); // Высокий приоритет
requests.offer(new Request("Заявка C", 3));
while (!requests.isEmpty()) {
System.out.println("Обработка: " + requests.poll().getName()); // Заявка B, Заявка C, Заявка A
}
}
}
Вывод: Заявки обрабатываются по приоритету.
Полезные советы для новичков
LinkedList для простоты: Универсальна для FIFO, легко добавить Deque-функции.
PriorityQueue для приоритетов: Передавайте Comparator для custom порядка (например, max-heap).
Custom классы: Реализуйте Comparable для PriorityQueue, или используйте Comparator.
Пустая очередь: Проверяйте isEmpty() перед poll, или используйте null от poll.
Итерация: For-each для просмотра, но не модифицируйте.
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
👍1
Раздел 6. Коллекции в Java
Глава 4. Queue и Deque
Интерфейс Deque. Двусторонняя очередь (FIFO и LIFO). Реализации: ArrayDeque, LinkedList
Интерфейс Deque<E> — это расширение Queue из пакета java.util, который представляет двустороннюю очередь (double-ended queue). Deque позволяет добавлять, удалять и просматривать элементы как с начала (head), так и с конца (tail) очереди. Это делает Deque универсальной структурой, способной моделировать как обычную очередь (FIFO), так и стек (LIFO), а также комбинированные сценарии.
Ключевые особенности Deque
Двусторонний доступ: Операции с first (начало) и last (конец).
FIFO и LIFO:
FIFO: Добавляйте в конец (addLast), извлекайте из начала (removeFirst) — как стандартная очередь.
LIFO: Добавляйте в начало (addFirst), извлекайте из начала (removeFirst) — как стек.
Уникальность элементов: Не гарантируется — дубликаты разрешены (зависит от реализации).
Null элементы: Зависит от реализации (ArrayDeque позволяет, но не рекомендуется; LinkedList позволяет).
Big O: Зависит от реализации, но обычно O(1) для операций на концах.
Итерация: Поддерживает Iterator для перебора от начала к концу, и descendingIterator() для обратного порядка.
Deque расширяет Queue, добавляя методы для работы с концом. Основные реализации: ArrayDeque (на массиве) и LinkedList (на связном списке). Deque можно использовать как Queue или Stack (вместо устаревшего Stack класса).
Когда использовать Deque:
Для стеков (LIFO, например, undo/redo).
Для очередей с доступом к концу (например, sliding window в алгоритмах).
Для двусторонних операций (например, палиндромы, где проверка с обоих концов).
FIFO и LIFO в Deque: Двусторонняя очередь
Deque поддерживает два основных режима:
FIFO (First-In-First-Out): "Первым вошел — первым вышел".
Добавление: addLast(E e) или offerLast(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Очередь в банке — первый пришел, первый ушел.
LIFO (Last-In-First-Out): "Последним вошел — первым вышел".
Добавление: addFirst(E e) или offerFirst(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Стопка тарелок — последняя сверху первой берется.
Методы Deque (основные, аналогично Queue, но с first/last)
Добавление:
addFirst(E e)/addLast(E e): Добавляет или кидает исключение, если переполнено.
offerFirst(E e)/offerLast(E e): Добавляет, возвращает boolean (false, если переполнено).
Извлечение:
removeFirst()/removeLast(): Извлекает или кидает NoSuchElementException, если пусто.
pollFirst()/pollLast(): Извлекает или возвращает null, если пусто.
Просмотр:
getFirst()/getLast(): Возвращает или кидает NoSuchElementException, если пусто.
peekFirst()/peekLast(): Возвращает или null, если пусто.
Другие: size(), isEmpty(), clear(), iterator(), descendingIterator().
Нюанс: Методы Queue (offer, poll, peek) в Deque эквивалентны offerLast, pollFirst, peekFirst (для FIFO).
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
Глава 4. Queue и Deque
Интерфейс Deque. Двусторонняя очередь (FIFO и LIFO). Реализации: ArrayDeque, LinkedList
Интерфейс Deque<E> — это расширение Queue из пакета java.util, который представляет двустороннюю очередь (double-ended queue). Deque позволяет добавлять, удалять и просматривать элементы как с начала (head), так и с конца (tail) очереди. Это делает Deque универсальной структурой, способной моделировать как обычную очередь (FIFO), так и стек (LIFO), а также комбинированные сценарии.
Ключевые особенности Deque
Двусторонний доступ: Операции с first (начало) и last (конец).
FIFO и LIFO:
FIFO: Добавляйте в конец (addLast), извлекайте из начала (removeFirst) — как стандартная очередь.
LIFO: Добавляйте в начало (addFirst), извлекайте из начала (removeFirst) — как стек.
Уникальность элементов: Не гарантируется — дубликаты разрешены (зависит от реализации).
Null элементы: Зависит от реализации (ArrayDeque позволяет, но не рекомендуется; LinkedList позволяет).
Big O: Зависит от реализации, но обычно O(1) для операций на концах.
Итерация: Поддерживает Iterator для перебора от начала к концу, и descendingIterator() для обратного порядка.
Deque расширяет Queue, добавляя методы для работы с концом. Основные реализации: ArrayDeque (на массиве) и LinkedList (на связном списке). Deque можно использовать как Queue или Stack (вместо устаревшего Stack класса).
Когда использовать Deque:
Для стеков (LIFO, например, undo/redo).
Для очередей с доступом к концу (например, sliding window в алгоритмах).
Для двусторонних операций (например, палиндромы, где проверка с обоих концов).
FIFO и LIFO в Deque: Двусторонняя очередь
Deque поддерживает два основных режима:
FIFO (First-In-First-Out): "Первым вошел — первым вышел".
Добавление: addLast(E e) или offerLast(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Очередь в банке — первый пришел, первый ушел.
LIFO (Last-In-First-Out): "Последним вошел — первым вышел".
Добавление: addFirst(E e) или offerFirst(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Стопка тарелок — последняя сверху первой берется.
Методы Deque (основные, аналогично Queue, но с first/last)
Добавление:
addFirst(E e)/addLast(E e): Добавляет или кидает исключение, если переполнено.
offerFirst(E e)/offerLast(E e): Добавляет, возвращает boolean (false, если переполнено).
Извлечение:
removeFirst()/removeLast(): Извлекает или кидает NoSuchElementException, если пусто.
pollFirst()/pollLast(): Извлекает или возвращает null, если пусто.
Просмотр:
getFirst()/getLast(): Возвращает или кидает NoSuchElementException, если пусто.
peekFirst()/peekLast(): Возвращает или null, если пусто.
Другие: size(), isEmpty(), clear(), iterator(), descendingIterator().
Нюанс: Методы Queue (offer, poll, peek) в Deque эквивалентны offerLast, pollFirst, peekFirst (для FIFO).
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
👍3
Реализации Deque: ArrayDeque и LinkedList
ArrayDeque
Описание: ArrayDeque — эффективная реализация Deque на основе кругового массива (circular array), который resizable. Она оптимизирована для операций на концах и рекомендуется как стандартная Deque в Java.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) amortized для addFirst/addLast, removeFirst/removeLast, peek (постоянное время). Contains — O(n).
Внутренняя работа: Массив с head и tail индексами. При добавлении/удалении индексы циклически сдвигаются. При заполнении массив удваивается (resizing O(n) rarely).
Нюансы:
Память: Эффективнее LinkedList (нет ссылок на узлы).
Initial capacity: Конструктор с int для начального размера (default 16).
Thread-safety: Нет — используйте для single-thread.
Когда использовать: Для большинства Deque-задач (быстрее LinkedList для концов).
Ограничение: Не реализует List, нет доступа по индексу.
Пример кода для ArrayDeque:
LinkedList
Описание: LinkedList — двусвязный список, который реализует Deque (и Queue, List). Как Deque, она позволяет операции на обоих концах.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) для addFirst/addLast, removeFirst/removeLast, peek (ссылки на first/last узлы). Contains — O(n).
Внутренняя работа: Узлы с prev/next ссылками. Добавление — создание узла и обновление ссылок first/last. Удаление — сдвиг ссылок.
Нюансы:
Память: Выше, чем ArrayDeque (каждый узел — объект с ссылками).
Универсальность: Реализует List, так что доступ по индексу (но O(n)).
Thread-safety: Нет.
Когда использовать: Для Deque с дополнительными List-функциями или частых вставок в середину (но для концов ArrayDeque быстрее).
Ограничение: Медленнее ArrayDeque для больших размеров из-за overhead узлов.
Пример кода для LinkedList как Deque (аналогичен ArrayDeque):
Полезные советы для новичков
ArrayDeque по умолчанию: Для большинства Deque-задач — эффективнее.
LinkedList для универсальности: Если нужно List API (get(index)), используйте её.
FIFO vs LIFO: Выбирайте методы (First/Last) по нуждам.
Null: Избегайте, чтобы не путаться.
Итераторы: descendingIterator() для обратного перебора — полезно для LIFO.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
ArrayDeque
Описание: ArrayDeque — эффективная реализация Deque на основе кругового массива (circular array), который resizable. Она оптимизирована для операций на концах и рекомендуется как стандартная Deque в Java.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) amortized для addFirst/addLast, removeFirst/removeLast, peek (постоянное время). Contains — O(n).
Внутренняя работа: Массив с head и tail индексами. При добавлении/удалении индексы циклически сдвигаются. При заполнении массив удваивается (resizing O(n) rarely).
Нюансы:
Память: Эффективнее LinkedList (нет ссылок на узлы).
Initial capacity: Конструктор с int для начального размера (default 16).
Thread-safety: Нет — используйте для single-thread.
Когда использовать: Для большинства Deque-задач (быстрее LinkedList для концов).
Ограничение: Не реализует List, нет доступа по индексу.
Пример кода для ArrayDeque:
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
// FIFO: Очередь
deque.offerLast("Элемент 1"); // Добавление в конец
deque.offerLast("Элемент 2");
System.out.println(deque.pollFirst()); // Элемент 1 (извлечение из начала)
System.out.println(deque.peekFirst()); // Элемент 2 (просмотр)
// LIFO: Стек
deque.offerFirst("Элемент 3"); // Добавление в начало
deque.offerFirst("Элемент 4");
System.out.println(deque.pollFirst()); // Элемент 4 (LIFO)
// Обратный итератор
for (String elem : deque.descendingIterator()) {
System.out.println(elem); // С конца к началу
}
}
}
Вывод: Показывает FIFO и LIFO, операции O(1).
LinkedList
Описание: LinkedList — двусвязный список, который реализует Deque (и Queue, List). Как Deque, она позволяет операции на обоих концах.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) для addFirst/addLast, removeFirst/removeLast, peek (ссылки на first/last узлы). Contains — O(n).
Внутренняя работа: Узлы с prev/next ссылками. Добавление — создание узла и обновление ссылок first/last. Удаление — сдвиг ссылок.
Нюансы:
Память: Выше, чем ArrayDeque (каждый узел — объект с ссылками).
Универсальность: Реализует List, так что доступ по индексу (но O(n)).
Thread-safety: Нет.
Когда использовать: Для Deque с дополнительными List-функциями или частых вставок в середину (но для концов ArrayDeque быстрее).
Ограничение: Медленнее ArrayDeque для больших размеров из-за overhead узлов.
Пример кода для LinkedList как Deque (аналогичен ArrayDeque):
import java.util.LinkedList;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.addLast("Элемент 1");
deque.addLast("Элемент 2");
System.out.println(deque.removeFirst()); // Элемент 1
deque.addFirst("Элемент 3");
System.out.println(deque.removeFirst()); // Элемент 3 (LIFO)
}
}
Вывод: То же, что и ArrayDeque, но с List-возможностями.
Полезные советы для новичков
ArrayDeque по умолчанию: Для большинства Deque-задач — эффективнее.
LinkedList для универсальности: Если нужно List API (get(index)), используйте её.
FIFO vs LIFO: Выбирайте методы (First/Last) по нуждам.
Null: Избегайте, чтобы не путаться.
Итераторы: descendingIterator() для обратного перебора — полезно для LIFO.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
👍2