PrepBro
← Назад к вопросам

Как структурно выглядит двусвязный список по сравнению с односвязным списком

1.0 Junior🔥 141 комментариев
#Коллекции

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Структура двусвязного списка по сравнению с односвязным

Двусвязные и односвязные списки — это фундаментальные структуры данных. Основное отличие в том, как устроены связи между узлами. Давайте подробно разберём структуру и поймём, зачем каждая нужна.

1. Односвязный список (Singly Linked List)

Структура узла:

public class SinglyNode<T> {
  public T data;              // Данные
  public SinglyNode<T> next;  // Ссылка на следующий узел
  
  public SinglyNode(T data) {
    this.data = data;
    this.next = null; // По умолчанию нет следующего
  }
}

Визуализация:

Односвязный список:

head → [10|next] → [20|next] → [30|next] → [40|null]
       ↑              ↑              ↑              ↑
      node1          node2          node3          node4
       data next      data next      data next      data next

Каждый узел знает только о следующем узле

Реализация односвязного списка:

public class SinglyLinkedList<T> {
  private SinglyNode<T> head;
  
  // Добавить в конец
  public void add(T data) {
    SinglyNode<T> newNode = new SinglyNode<>(data);
    
    if (head == null) {
      head = newNode;
      return;
    }
    
    SinglyNode<T> current = head;
    while (current.next != null) {
      current = current.next; // Идём к концу
    }
    current.next = newNode; // Присоединяем новый узел
  }
  
  // Удалить по индексу
  public boolean remove(int index) {
    if (index < 0 || head == null) return false;
    
    if (index == 0) {
      head = head.next; // Удалить первый
      return true;
    }
    
    SinglyNode<T> current = head;
    for (int i = 0; i < index - 1 && current.next != null; i++) {
      current = current.next; // Нужно найти предыдущий узел
    }
    
    if (current.next != null) {
      current.next = current.next.next; // Пропустить удаляемый узел
      return true;
    }
    
    return false;
  }
  
  // Получить элемент
  public T get(int index) {
    SinglyNode<T> current = head;
    for (int i = 0; i < index && current != null; i++) {
      current = current.next;
    }
    return current != null ? current.data : null;
  }
}

Характеристики односвязного списка:

  • Память: каждый узел требует 1 ссылку (8 байт на 64-bit JVM)
  • Добавление в начало: O(1)
  • Добавление в конец: O(n) — нужно найти конец
  • Удаление: O(n) — нужно найти предыдущий узел
  • Поиск: O(n)
  • Обход в обе стороны: ❌ невозможно

2. Двусвязный список (Doubly Linked List)

Структура узла:

public class DoublyNode<T> {
  public T data;              // Данные
  public DoublyNode<T> next;  // Ссылка на следующий узел
  public DoublyNode<T> prev;  // Ссылка на предыдущий узел ← КЛЮЧЕВОЕ ОТЛИЧИЕ
  
  public DoublyNode(T data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

Визуализация:

Двусвязный список:

head ↔ [10|prev|next] ↔ [20|prev|next] ↔ [30|prev|next] ↔ [40|prev|next] ← tail
     ↑                                                                     ↑
   node1                                                                node4
   prev|next                                                           prev|next
   null|                                                                    |null

Каждый узел знает о предыдущем И следующем узле
Лист имеет head AND tail

Реализация двусвязного списка:

public class DoublyLinkedList<T> {
  private DoublyNode<T> head;
  private DoublyNode<T> tail;
  private int size = 0;
  
  // Добавить в конец
  public void add(T data) {
    DoublyNode<T> newNode = new DoublyNode<>(data);
    
    if (head == null) {
      head = tail = newNode;
    } else {
      tail.next = newNode;   // Последний узел указывает на новый
      newNode.prev = tail;   // Новый узел указывает на последний ← ВАЖНО
      tail = newNode;        // Обновляем tail
    }
    
    size++;
  }
  
  // Добавить в начало
  public void addFirst(T data) {
    DoublyNode<T> newNode = new DoublyNode<>(data);
    
    if (head == null) {
      head = tail = newNode;
    } else {
      newNode.next = head;   // Новый узел указывает на голову
      head.prev = newNode;   // Голова указывает на новый
      head = newNode;        // Обновляем head
    }
    
    size++;
  }
  
  // Удалить по индексу (быстро благодаря двусвязности)
  public boolean remove(int index) {
    if (index < 0 || index >= size) return false;
    
    DoublyNode<T> nodeToRemove;
    
    // Оптимизация: идти от ближайшего конца
    if (index < size / 2) {
      nodeToRemove = getNode(index, true);  // Идти с начала
    } else {
      nodeToRemove = getNode(index, false); // Идти с конца
    }
    
    if (nodeToRemove == null) return false;
    
    // Перезвязать узлы
    if (nodeToRemove.prev != null) {
      nodeToRemove.prev.next = nodeToRemove.next; // Предыдущий → следующему
    } else {
      head = nodeToRemove.next; // Это была голова
    }
    
    if (nodeToRemove.next != null) {
      nodeToRemove.next.prev = nodeToRemove.prev; // Следующий → предыдущему
    } else {
      tail = nodeToRemove.prev; // Это был хвост
    }
    
    size--;
    return true;
  }
  
  private DoublyNode<T> getNode(int index, boolean fromStart) {
    if (fromStart) {
      DoublyNode<T> current = head;
      for (int i = 0; i < index && current != null; i++) {
        current = current.next;
      }
      return current;
    } else {
      DoublyNode<T> current = tail;
      for (int i = size - 1; i > index && current != null; i--) {
        current = current.next; // ОПАAA можно идти назад благодаря prev
      }
      return current;
    }
  }
  
  // Обход в обе стороны
  public void forwardTraversal() {
    DoublyNode<T> current = head;
    while (current != null) {
      System.out.print(current.data + " ← forward");
      current = current.next;
    }
  }
  
  public void backwardTraversal() {
    DoublyNode<T> current = tail;
    while (current != null) {
      System.out.print(current.data + " ← backward");
      current = current.prev; // Благодаря prev можем идти назад!
    }
  }
}

Характеристики двусвязного списка:

  • Память: каждый узел требует 2 ссылки (16 байт на 64-bit JVM)
  • Добавление в начало: O(1)
  • Добавление в конец: O(1) ← благодаря tail
  • Удаление: O(n) но с оптимизацией O(n/2)
  • Поиск: O(n) но с оптимизацией O(n/2)
  • Обход в обе стороны: ✅ yes

3. Визуальное сравнение операций

Удаление элемента:

Односвязный список:
a → b → c → d → null

Удалить 'c':
1. Найти 'b' (нужно идти с начала): O(n)
2. Изменить b.next = d

Двусвязный список:
a ↔ b ↔ c ↔ d ↔ null

Удалить 'c':
1. У 'c' есть c.prev, поэтому можно сразу найти 'b': O(1)
2. Изменить b.next = d и d.prev = b

Поиск элемента:

Односвязный список - поиск 'c':
head → a → b → c → d → null
Start from beginning: a → b → c ✓ (3 шага)

Двусвязный список - поиск 'c':
head ↔ a ↔ b ↔ c ↔ d ↔ tail
Start from middle: 
  - от начала: a → b → c ✓ (3 шага)
  - от конца: d ← c ✓ (2 шага)
Выбираем ближайший = 2 шага

4. Java встроенная реализация

import java.util.LinkedList;
import java.util.List;

public class JavaLinkedList {
  public static void main(String[] args) {
    // LinkedList в Java — это на самом деле ДВУСВЯЗНЫЙ список
    List<Integer> list = new LinkedList<>();
    
    list.add(10);      // O(1) — добавить в конец
    list.add(0, 5);    // O(n/2) с оптимизацией
    list.remove(0);    // O(n/2) с оптимизацией
    
    // Это работает эффективно благодаря двусвязной структуре
  }
}

// LinkedList в Java:
// - Двусвязный список
// - Реализует List, Deque, Queue
// - Поддерживает операции с обоих концов

5. Когда использовать какой список

┌──────────────────┬──────────┬────────────────────┐
│ Операция         │ Singly   │ Doubly             │
├──────────────────┼──────────┼────────────────────┤
│ Добавить в конец │ O(n)     │ O(1) with tail     │
│ Добавить в нач.  │ O(1)     │ O(1)               │
│ Удалить из нач.  │ O(1)     │ O(1)               │
│ Удалить из конца │ O(n)     │ O(1) with tail     │
│ Память           │ Меньше   │ Больше             │
│ Простота         │ Проще    │ Сложнее            │
│ Обход назад      │ ❌       │ ✅                 │
└──────────────────┴──────────┴────────────────────┘

Использовать SINGLY, если:
- Часто добавляешь в начало
- Редко удаляешь
- Важна экономия памяти
- Простота реализации

Использовать DOUBLY, если:
- Нужны операции с обоих концов (Deque)
- Часто удаляешь элементы
- Нужна оптимизация поиска (ближайший конец)
- Нужен обход в обе стороны

6. Практический пример: LRU Cache

Двусвязный список идеален для LRU Cache благодаря быстрому удалению:

public class LRUCache<K, V> {
  private static class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev, next;
    
    Node(K key, V value) {
      this.key = key;
      this.value = value;
    }
  }
  
  private final int capacity;
  private final Map<K, Node<K, V>> cache = new HashMap<>();
  private Node<K, V> head = new Node<>(null, null); // Dummy node
  private Node<K, V> tail = new Node<>(null, null); // Dummy node
  
  public LRUCache(int capacity) {
    this.capacity = capacity;
    head.next = tail;
    tail.prev = head;
  }
  
  public V get(K key) {
    if (!cache.containsKey(key)) return null;
    
    Node<K, V> node = cache.get(key);
    moveToEnd(node); // Переместить в конец (самый свежий)
    return node.value;
  }
  
  public void put(K key, V value) {
    if (cache.containsKey(key)) {
      Node<K, V> node = cache.get(key);
      node.value = value;
      moveToEnd(node);
      return;
    }
    
    // Удалить самый старый (из начала) если переполнено
    if (cache.size() == capacity) {
      Node<K, V> oldestNode = head.next;
      removeNode(oldestNode);
      cache.remove(oldestNode.key);
    }
    
    // Добавить новый (в конец)
    Node<K, V> newNode = new Node<>(key, value);
    insertBeforeTail(newNode);
    cache.put(key, newNode);
  }
  
  private void moveToEnd(Node<K, V> node) {
    removeNode(node);
    insertBeforeTail(node);
  }
  
  private void removeNode(Node<K, V> node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  
  private void insertBeforeTail(Node<K, V> node) {
    node.next = tail;
    node.prev = tail.prev;
    tail.prev.next = node;
    tail.prev = node;
  }
}

В итоге: Односвязный список проще и экономнее памяти, но медленнее для удаления. Двусвязный список медленнее в памяти, но быстрее для операций с обоих концов. Java LinkedList использует двусвязный список, потому что он универсальнее и поддерживает операции как Deque, так и List.

Как структурно выглядит двусвязный список по сравнению с односвязным списком | PrepBro