В чем выражается двусвязность списка

# В чем выражается двусвязность списка

Двусвязность списка выражается в том, что каждый элемент списка имеет две ссылки: на предыдущий элемент (previous) и на следующий элемент (next). Это отличает двусвязный список от односвязного списка, где каждый элемент имеет только одну ссылку на следующий элемент.

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

// Структура узла двусвязного списка
class Node<E> {
    E element;           // Данные
    Node<E> prev;       // Ссылка на ПРЕДЫДУЩИЙ узел
    Node<E> next;       // Ссылка на СЛЕДУЮЩИЙ узел
    
    Node(E element) {
        this.element = element;
        this.prev = null;
        this.next = null;
    }
}

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

Односвязный список:
node1 → node2 → node3 → null
(только вперед)

Двусвязный список:
null ← node1 ↔ node2 ↔ node3 → null
(в обе стороны)

Визуализация двусвязного списка

    ┌──────────┐
    │ prev=null│
    │ data=10  │
    │ next ─┐  │
    └──────┼──┘
           │
         ┌─▼──────────────┐
         │ prev ─┐        │
         │ data=20│        │
         │ next ────┐     │
         └────┼────┼─────┘
              │    │
            ┌─┘    └─────────┐
            │                 │
         ┌──▼──────────────┐  │
         │ prev ◄─────┐    │  │
         │ data=30    │    │  │
         │ next=null  │    │  │
         └────────────┘    │  │
                           │  │
                    ┌──────▼──▼─┐
                    │(следующий)│

Пример реализации LinkedList в Java

public class DoublyLinkedList<E> {
    
    // Узел списка
    private class Node {
        E element;
        Node prev;
        Node next;
        
        Node(E element) {
            this.element = element;
        }
    }
    
    private Node head;  // Начало
    private Node tail;  // Конец
    private int size;
    
    // Добавление в конец списка
    public void add(E element) {
        Node newNode = new Node(element);
        
        if (head == null) {
            // Список пуст
            head = tail = newNode;
        } else {
            // Привязать к концу
            newNode.prev = tail;      // новый узел.prev → старый конец
            tail.next = newNode;      // старый конец.next → новый узел
            tail = newNode;           // новый узел становится концом
        }
        size++;
    }
    
    // Добавление в начало
    public void addFirst(E element) {
        Node newNode = new Node(element);
        
        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;      // новый узел.next → старое начало
            head.prev = newNode;      // старое начало.prev → новый узел
            head = newNode;           // новый узел становится началом
        }
        size++;
    }
    
    // Удаление узла
    public void remove(int index) {
        Node node = getNode(index);
        
        if (node.prev != null) {
            node.prev.next = node.next;  // prev.next пропускает этот узел
        } else {
            head = node.next;             // это был head
        }
        
        if (node.next != null) {
            node.next.prev = node.prev;   // next.prev пропускает этот узел
        } else {
            tail = node.prev;             // это был tail
        }
        
        size--;
    }
    
    // Получение элемента по индексу
    public E get(int index) {
        return getNode(index).element;
    }
    
    // Поиск узла с оптимизацией (ищет с ближайшего конца)
    private Node getNode(int index) {
        if (index < size / 2) {
            // Искать от начала
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            // Искать с конца (оптимизация)
            Node node = tail;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
}

Преимущества двусвязного списка

1. Навигация в обе стороны

DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
list.add(10);
list.add(20);
list.add(30);

// В двусвязном списке можно искать с конца
// С использованием prev ссылок это более эффективно
System.out.println(list.get(2)); // 30
System.out.println(list.get(1)); // 20
System.out.println(list.get(0)); // 10

2. Эффективное удаление элемента

// В двусвязном списке удаление узла происходит за O(1)
// если у вас уже есть ссылка на узел
private void removeNode(Node node) {
    if (node.prev != null) {
        node.prev.next = node.next;
    } else {
        head = node.next;
    }
    
    if (node.next != null) {
        node.next.prev = node.prev;
    } else {
        tail = node.prev;
    }
}

3. Обратный обход

// Обход в прямом направлении (как массив)
public void printForward() {
    Node node = head;
    while (node != null) {
        System.out.print(node.element + " → ");
        node = node.next;
    }
    System.out.println("null");
}

// Обратный обход (уникально для двусвязных списков)
public void printBackward() {
    Node node = tail;
    while (node != null) {
        System.out.print(node.element + " ← ");
        node = node.prev;
    }
    System.out.println("null");
}

LinkedList в Java (двусвязный список)

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        
        // Добавление элементов
        list.add(10);      // В конец
        list.add(20);
        list.add(30);
        
        list.addFirst(5);  // В начало
        list.addLast(40);  // В конец
        
        // Обход в прямом направлении
        System.out.println("Forward: " + list);
        // Output: [5, 10, 20, 30, 40]
        
        // LinkedList поддерживает обратный обход
        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.print(list.get(i) + " ");
        }
        // Output: 40 30 20 10 5
        
        // Удаление элементов
        list.removeFirst(); // Удалить 5
        list.removeLast();  // Удалить 40
        
        System.out.println("After removal: " + list);
        // Output: [10, 20, 30]
        
        // Получение итератора (для двусвязного списка очень эффективно)
        var iterator = list.listIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

Сравнение ArrayList и LinkedList

*амортизированно **если известна ссылка на узел

Важные различия

public void differences() {
    LinkedList<String> linkedList = new LinkedList<>();
    ArrayList<String> arrayList = new ArrayList<>();
    
    // LinkedList эффективнее для частого добавления/удаления в начале
    linkedList.addFirst("start");      // O(1)
    arrayList.add(0, "start");         // O(n)
    
    // ArrayList эффективнее для доступа по индексу
    String first = arrayList.get(0);   // O(1)
    String first2 = linkedList.get(0); // O(n)
    
    // LinkedList использует меньше памяти (без empty slots)
    // ArrayList может иметь пустые ячейки для быстрого расширения
}

Двусвязность в контексте Node структуры

Односвязный список:
class Node {
    int data;
    Node next;  // Только одна ссылка
}

Двусвязный список:
class Node {
    int data;
    Node prev;  // ВО ВСЕ СТОРОНЫ
    Node next;  // ДВУСВЯЗНОСТЬ
}

Память и производительность

// Стоимость двусвязности
// Про каждый элемент хранится две ссылки вместо одной

Память:
Односвязный список: element + 1 ссылка = 8 bytes (element) + 8 bytes (next) = 16 bytes на узел
Двусвязный список:  element + 2 ссылки = 8 bytes (element) + 8 bytes (next) + 8 bytes (prev) = 24 bytes на узел

// Это цена за двусвязность — больше памяти, но больше гибкости

Ключевые моменты

1. Двусвязность = две ссылки: prev и next для каждого узла
2. Навигация в обе стороны: можно идти вперед и назад
3. Эффективное добавление/удаление: особенно в начале списка
4. Обратный обход: возможен без дополнительных операций
5. LinkedList в Java — двусвязный список
6. Больше памяти: ссылка prev требует дополнительную память
7. Оптимизация поиска: можно выбирать направление поиска