Ответ
Двусвязный список — это линейная структура данных, в которой каждый узел содержит:
- Данные.
- Указатель (ссылку) на следующий узел (
next). - Указатель на предыдущий узел (
prev).
Это позволяет эффективно перемещаться по списку в обоих направлениях.
Реализация на Java:
class DoublyLinkedList<T> {
class Node {
T data;
Node prev;
Node next;
Node(T data) { this.data = data; }
}
private Node head;
private Node tail;
// Вставка в конец за O(1)
public void append(T data) {
Node newNode = new Node(data);
if (tail == null) { // Список пуст
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// Удаление с конца за O(1)
public void removeLast() {
if (tail != null) {
tail = tail.prev;
if (tail != null) tail.next = null;
else head = null; // Список стал пустым
}
}
}| Сравнение с односвязным списком: | Операция | Односвязный список | Двусвязный список |
|---|---|---|---|
| Вставка/удаление в начале | O(1) | O(1) | |
| Вставка/удаление в конце | O(n) | O(1) | |
| Удаление произвольного узла (при известной ссылке) | O(n) | O(1) | |
| Обход назад | Невозможен | O(n) | |
| Потребление памяти | Меньше | Больше (доп. указатель) |
Применение: Реализация деков (Deque), кэшей (LRU Cache), систем отмены действий (undo/redo).
Ответ 18+ 🔞
А, двусвязный список! Ну это ж классика, блядь, как та самая история про Герасима и Муму, только с указателями, а не с собаками. Слушай сюда, сейчас разжую.
Представь себе цепочку, где каждый чувак — это узел. Но он не просто тупой, как в односвязном списке, где знает только про следующего мудака в очереди. Этот — хитрая жопа! Он держит в одной руке данные (ну, там, число, строку, объект — похуй), а в другой — две ссылки. Одну на пацана перед ним (prev), другую — на пацана после него (next). Вот и вся магия, ёпта!
class DoublyLinkedList<T> {
class Node {
T data; // Сами данные, что храним
Node prev; // Ссылка на предыдущий узел
Node next; // Ссылка на следующий узел
Node(T data) { this.data = data; }
}
private Node head; // Голова списка, первый элемент
private Node tail; // Хвост списка, последний элемент
// ... дальше методы
}И вот в чём, блядь, его сила, в рот меня чих-пых! В обычном, односвязном списке, чтобы удалить последний элемент, надо пройти от головы до самого конца, как Герасим искал Муму, блядь. А тут — охуенно просто! У тебя же есть tail — прямая ссылка на конец!
Добавить в конец (append):
Смотри, если список пустой — голова и хвост это новый узел. Если нет — берём текущий хвост, говорим ему: «Слушай, старик, теперь твой next — это этот новенький». А новенькому шепчем: «А твой prev — это вот этот старик». И переставляем хвост на новенького. Всё, O(1), нихуя не O(n)!
Удалить с конца (removeLast):
Ещё проще, ёбана! Берём хвост, откатываем его на одного пацана назад (tail = tail.prev). Если после этого хвост не null (то есть список не опустел), то этому новому хвосту говорим: «Бро, забудь про следующего, его больше нет» (tail.next = null). А если список опустел — обнуляем и голову тоже. И опять O(1), а не беготня через весь список!
Сравнительная таблица, блядь (чтоб совсем охуеть):
| Что делаем | Односвязный список (туповатый) | Двусвязный список (хитрый) |
|---|---|---|
| Впихнуть/выпихнуть в начале | O(1) (норм) | O(1) (тоже норм) |
| Впихнуть/выпихнуть в конце | O(n) (надо бежать от начала, пиздец!) | O(1) (а вот это уже охуенно!) |
| Удалить конкретный узел (если знаешь на него ссылку) | O(n) (надо искать его предка) | O(1) (знаешь предка через prev!) |
| Пройтись задом наперёд | Невозможно, нихуя! | O(n) (запросто, через prev) |
| Жрёт памяти | Меньше (только next) |
Больше (ещё и prev) |
Где это, сука, применяется? Да везде, где нужно туда-сюда бегать и быстро с концами работать!
- Дек (Deque) — двусторонняя очередь. Добавил в начало, добавил в конец — всё быстро.
- LRU-кэш — когда нужно выкидывать самый старый элемент и быстро переставлять часто используемый в начало. Тут без двусвязности — просто пиздец и ручной управляемый занос.
- Система «Отмена/Повтор» (undo/redo) в редакторах. Перемещаешься по истории действий туда-сюда, как по списку. Удобно, блядь!
Короче, двусвязный список — это как иметь не только глаза спереди, но и затылок с радаром. Удобно, но памяти жрёт больше. Выбирай по задаче, чувак.