Как называется наличие у объекта ссылки на предыдущий и следующий объект

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

Наличие у объекта ссылки на предыдущий и следующий объект называется структурой данных Двусвязный список (Doubly Linked List) или двунаправленный список.

Определение и характеристики

Двусвязный список - это линейная структура данных, в которой каждый узел (элемент) содержит:

• Данные (значение)
• Ссылку на следующий узел (next)
• Ссылку на предыдущий узел (previous)

В отличие от односвязного списка, где каждый узел имеет только ссылку на следующий элемент.

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

public class Node<T> {
    private T data;
    private Node<T> next;
    private Node<T> previous;
    
    public Node(T data) {
        this.data = data;
        this.next = null;
        this.previous = null;
    }
    
    // Getters and setters
    public T getData() { return data; }
    public Node<T> getNext() { return next; }
    public void setNext(Node<T> next) { this.next = next; }
    public Node<T> getPrevious() { return previous; }
    public void setPrevious(Node<T> previous) { this.previous = previous; }
}

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

public class DoublyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;
    
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    // Вставка в начало
    public void insertAtBeginning(T data) {
        Node<T> newNode = new Node<>(data);
        
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.setNext(head);
            head.setPrevious(newNode);
            head = newNode;
        }
        size++;
    }
    
    // Вставка в конец
    public void insertAtEnd(T data) {
        Node<T> newNode = new Node<>(data);
        
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.setNext(newNode);
            newNode.setPrevious(tail);
            tail = newNode;
        }
        size++;
    }
    
    // Вставка в позицию
    public void insertAtPosition(int position, T data) {
        if (position < 0 || position > size) {
            throw new IndexOutOfBoundsException();
        }
        
        if (position == 0) {
            insertAtBeginning(data);
            return;
        }
        
        if (position == size) {
            insertAtEnd(data);
            return;
        }
        
        Node<T> newNode = new Node<>(data);
        Node<T> current = getNode(position - 1);
        
        newNode.setNext(current.getNext());
        newNode.setPrevious(current);
        current.getNext().setPrevious(newNode);
        current.setNext(newNode);
        size++;
    }
    
    // Удаление элемента
    public void remove(int position) {
        if (position < 0 || position >= size) {
            throw new IndexOutOfBoundsException();
        }
        
        Node<T> current = getNode(position);
        
        if (current.getPrevious() != null) {
            current.getPrevious().setNext(current.getNext());
        } else {
            head = current.getNext();
        }
        
        if (current.getNext() != null) {
            current.getNext().setPrevious(current.getPrevious());
        } else {
            tail = current.getPrevious();
        }
        
        size--;
    }
    
    // Получение элемента
    public T get(int position) {
        if (position < 0 || position >= size) {
            throw new IndexOutOfBoundsException();
        }
        return getNode(position).getData();
    }
    
    private Node<T> getNode(int position) {
        Node<T> current;
        
        // Оптимизация: начинаем с конца, если элемент ближе
        if (position < size / 2) {
            current = head;
            for (int i = 0; i < position; i++) {
                current = current.getNext();
            }
        } else {
            current = tail;
            for (int i = size - 1; i > position; i--) {
                current = current.getPrevious();
            }
        }
        
        return current;
    }
    
    // Обход в прямом направлении
    public void displayForward() {
        Node<T> current = head;
        System.out.print("Forward: ");
        while (current != null) {
            System.out.print(current.getData() + " <-> ");
            current = current.getNext();
        }
        System.out.println("null");
    }
    
    // Обход в обратном направлении
    public void displayBackward() {
        Node<T> current = tail;
        System.out.print("Backward: ");
        while (current != null) {
            System.out.print(current.getData() + " <-> ");
            current = current.getPrevious();
        }
        System.out.println("null");
    }
}

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

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtBeginning(5);
        list.insertAtPosition(2, 15);
        
        list.displayForward();   // Forward: 5 <-> 10 <-> 15 <-> 20 <-> 30
        list.displayBackward();  // Backward: 30 <-> 20 <-> 15 <-> 10 <-> 5
        
        System.out.println("Element at position 2: " + list.get(2));  // 15
        
        list.remove(2);
        list.displayForward();   // Forward: 5 <-> 10 <-> 20 <-> 30
    }
}

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

• Можно перемещаться в обе стороны
• Удаление элемента эффективнее, если известна позиция
• Полезен для реализации LRU кешей
• Удобен для операций, требующих доступа к соседним элементам

Недостатки

• Требует больше памяти (две ссылки вместо одной)
• Сложнее в реализации и отладке
• Медленнее при работе с элементами (сравнено с массивом)

Применение в Java

В Java класс LinkedList реализует двусвязный список:

List<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(30);
list.remove(1);
Iterator<Integer> iterator = list.iterator();

Взаимосвязь с похожими структурами

Однозвязный список (Singly Linked List) - имеет только ссылку на следующий элемент. Циклический двусвязный список - tail указывает на head, head.previous указывает на tail.