← Назад к вопросам
Является ли список двунаправленным или однонаправленным?
1.0 Junior🔥 191 комментариев
#Soft Skills и карьера
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Является ли список двунаправленным или однонаправленным?
Это вопрос про структуры данных в Java. Ответ: это зависит от конкретной реализации List, и в Java встроены обе версии. Давайте разберём разницу и конкретные примеры.
Что такое однонаправленный список (Singly Linked List)?
Структура однонаправленного списка:
Однонаправленный связный список (Singly Linked List):
Node1 → Node2 → Node3 → Node4 → null
|
Value1
Каждый узел содержит:
- Значение (value)
- Ссылка на следующий узел (next)
- НЕ содержит ссылку на предыдущий узел
Реализация однонаправленного списка:
public class SinglyLinkedListNode<T> {
T value;
SinglyLinkedListNode<T> next; // Ссылка только на следующий узел
public SinglyLinkedListNode(T value) {
this.value = value;
this.next = null;
}
}
public class SimpleSinglyLinkedList<T> {
private SinglyLinkedListNode<T> head;
public void add(T value) {
SinglyLinkedListNode<T> newNode = new SinglyLinkedListNode<>(value);
if (head == null) {
head = newNode;
} else {
SinglyLinkedListNode<T> current = head;
while (current.next != null) {
current = current.next; // Идём вперёд по next
}
current.next = newNode;
}
}
// Проблема: поиск предыдущего узла требует O(n) времени
public void remove(T value) {
if (head == null) return;
if (head.value.equals(value)) {
head = head.next;
return;
}
SinglyLinkedListNode<T> current = head;
while (current.next != null) {
if (current.next.value.equals(value)) {
current.next = current.next.next; // Пропускаем узел
return;
}
current = current.next;
}
}
}
Характеристики однонаправленного списка:
┌──────────────────────────────────────┐
│ Однонаправленный список │
├──────────────────────────────────────┤
│ Память: O(n) │
│ Добавление: O(n) (нужно найти end)│
│ Удаление: O(n) (нужен prev) │
│ Поиск: O(n) │
│ Доступ к i-му: O(n) │
└──────────────────────────────────────┘
Что такое двунаправленный список (Doubly Linked List)?
Структура двунаправленного списка:
Двунаправленный связный список (Doubly Linked List):
node1 ←→ node2 ←→ node3 ←→ node4
↑ ↓
head tail
Каждый узел содержит:
- Значение (value)
- Ссылка на следующий узел (next)
- Ссылка на предыдущий узел (prev) ← ВОТ РАЗНИЦА!
Реализация двунаправленного списка:
public class DoublyLinkedListNode<T> {
T value;
DoublyLinkedListNode<T> next; // Ссылка на следующий
DoublyLinkedListNode<T> prev; // Ссылка на предыдущий
public DoublyLinkedListNode(T value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
public class SimpleDoublyLinkedList<T> {
private DoublyLinkedListNode<T> head;
private DoublyLinkedListNode<T> tail;
public void add(T value) {
DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(value);
if (head == null) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail; // Связываем в обе стороны
tail = newNode;
}
}
// Удаление проще благодаря prev ссылке
public void remove(T value) {
DoublyLinkedListNode<T> current = head;
while (current != null) {
if (current.value.equals(value)) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
return;
}
current = current.next;
}
}
// Бонус: можем итерировать в обе стороны
public void iterateForward() {
DoublyLinkedListNode<T> current = head;
while (current != null) {
System.out.println(current.value);
current = current.next;
}
}
public void iterateBackward() {
DoublyLinkedListNode<T> current = tail;
while (current != null) {
System.out.println(current.value);
current = current.prev; // Идём в обратном направлении!
}
}
}
Характеристики двунаправленного списка:
┌──────────────────────────────────────┐
│ Двунаправленный список │
├──────────────────────────────────────┤
│ Память: O(n) + больше памяти │
│ Добавление: O(1) (если есть tail) │
│ Удаление: O(1) (если есть узел) │
│ Поиск: O(n) │
│ Доступ к i-му: O(n) │
│ Обратный ход: ✓ Возможен │
└──────────────────────────────────────┘
Что в Java?
ArrayList — это НЕ связный список, это динамический массив:
// ArrayList
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
// Внутренняя структура: обычный массив
// [A, B, C, null, null]
// 0 1 2 3 4 (индексы)
// Свойства:
list.get(0); // O(1) - прямой доступ к индексу
list.add(1, "X"); // O(n) - нужно сдвинуть элементы
LinkedList — это двунаправленный список:
// LinkedList в Java — это ДВУНАПРАВЛЕННЫЙ связный список
List<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
// Внутренняя структура (двунаправленный список):
// head ← A ← B ← C → tail
// Свойства:
list.get(0); // O(n) - нужно итерировать с начала
list.add(1, "X"); // O(1) - если уже на нужной позиции
// LinkedList имеет дополнительные методы:
list.getFirst(); // Первый элемент
list.getLast(); // Последний элемент
list.removeFirst(); // Удалить первый
list.removeLast(); // Удалить последний
Доказательство: LinkedList в Java — двунаправленный
Из исходного кода Java:
// Из java.util.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;
}
}
Практический пример двунаправленной природы:
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// Итерировать вперед
System.out.println("Forward:");
for (Integer num : list) {
System.out.print(num + " "); // 1 2 3 4 5
}
// Итерировать в обратном направлении
System.out.println("\nBackward:");
ListIterator<Integer> iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
System.out.print(iterator.previous() + " "); // 5 4 3 2 1
}
// Это возможно только потому что LinkedList двунаправленный!
}
}
Сравнение List реализаций в Java
┌──────────────────────────────────────────────────────────┐
│ ArrayList │
├──────────────────────────────────────────────────────────┤
│ Структура: Динамический массив (NOT linked list) │
│ Память: Компактная O(n) │
│ Доступ: O(1) - прямой по индексу ✓ │
│ Вставка: O(n) - нужны сдвиги │
│ Удаление: O(n) - нужны сдвиги │
│ Использование: Когда много чтения и доступа │
└──────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────┐
│ LinkedList │
├──────────────────────────────────────────────────────────┤
│ Структура: Двунаправленный связный список │
│ Память: Больше память (хранит prev, next) │
│ Доступ: O(n) - нужно итерировать │
│ Вставка: O(1) - если известна позиция │
│ Удаление: O(1) - если есть узел │
│ Использование: Когда много вставок/удалений в начало │
│ или середину │
└──────────────────────────────────────────────────────────┘
Когда использовать каждый?
ArrayList:
// Хороший выбор
List<User> users = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
users.get(i); // Много доступов → O(1)
System.out.println(users.get(i).getName());
}
// Плохой выбор для LinkedList
// Была бы O(n) вместо O(1)
LinkedList:
// Хороший выбор
Queue<String> queue = new LinkedList<>();
queue.add("task1"); // Добавить в конец
queue.add("task2");
String task = queue.remove(); // Удалить с начала
// Или для Deque
Deque<String> deque = new LinkedList<>();
deque.addFirst("first"); // O(1)
deque.addLast("last"); // O(1)
deque.removeFirst(); // O(1)
deque.removeLast(); // O(1)
// Плохой выбор для ArrayList
// removeFirst() была бы O(n) вместо O(1)
Практический пример: зачем нужен двунаправленный список
public class CacheWithLRU {
private Map<String, String> cache;
private LinkedList<String> accessOrder; // Очередь доступа
private static final int MAX_SIZE = 100;
public CacheWithLRU() {
this.cache = new HashMap<>();
this.accessOrder = new LinkedList<>();
}
public String get(String key) {
if (cache.containsKey(key)) {
// Перемещаем в конец (most recently used)
accessOrder.remove(key); // Удалить откуда-то в середине
accessOrder.add(key); // Добавить в конец
return cache.get(key);
}
return null;
}
public void put(String key, String value) {
if (cache.size() >= MAX_SIZE && !cache.containsKey(key)) {
// Удалить least recently used (первый элемент)
String lru = accessOrder.removeFirst(); // O(1) благодаря prev ссылке
cache.remove(lru);
}
cache.put(key, value);
accessOrder.remove(key);
accessOrder.add(key);
}
}
// LinkedList идеален для этого потому что:
// 1. removeLast() и removeFirst() - O(1)
// 2. addFirst() и addLast() - O(1)
// 3. Двунаправленность позволяет итерировать в обе стороны
Визуализация производительности
Операция ArrayList LinkedList
─────────────────────────────────────────────
add(item) O(1) O(1)*
add(index, item) O(n) O(n)*
remove(item) O(n) O(n)
remove(index) O(n) O(n)
get(index) O(1) O(n) ✗
contains(item) O(n) O(n)
size() O(1) O(1)
* - амортизированное время (с resizing)
** - если есть iterator, может быть быстрее
Ответ на вопрос
В Java встроены оба типа:
- ArrayList — это НЕ связный список вообще (это динамический массив)
- LinkedList — это ДВУНАПРАВЛЕННЫЙ связный список
- Однонаправленные списки в Java нужно реализовывать самостоятельно
На собеседовании:
Esли вас спрашивают "Является ли список двунаправленным или однонаправленным?", правильный ответ:
"Зависит от реализации List:
- ArrayList: это НЕ связный список, это динамический массив
- LinkedList: это ДВУНАПРАВЛЕННЫЙ связный список
- Однонаправленный список: в стандартной библиотеке нет,
нужно реализовать самостоятельно
Для большинства задач используются ArrayList или LinkedList.
LinkedList полезен когда много операций в начале списка
или нужна итерация в обе стороны."