Какая временная сложность read в связном списке?

Какая временная сложность read в связном списке?

Ответ: O(n) — линейная временная сложность. Для получения элемента по индексу в связном списке нужно последовательно пройти от головы списка через все предыдущие элементы, пока не достигнете нужного элемента.

Почему O(n)?

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

class Node<T> {
  T value;
  Node<T>? next;
  Node(this.value);
}

// Структура: [Node1] -> [Node2] -> [Node3] -> [Node4] -> null

Чтобы прочитать элемент с индексом 3, нужно:

1. Начать с head (Node1)
2. Перейти к next (Node2)
3. Перейти к next (Node3)
4. Перейти к next (Node4) — нужный элемент

Итого: 3 операции переходов для доступа к 4-му элементу → O(n)

Реализация read операции

class LinkedList<T> {
  Node<T>? head;

  // Read элемента по индексу - O(n)
  T? getAt(int index) {
    if (index < 0) return null;
    
    Node<T>? current = head;
    int count = 0;
    
    // Проходим список пока не найдём нужный индекс
    while (current != null && count < index) {
      current = current.next;
      count++;
    }
    
    return current?.value;
  }
}

void main() {
  var list = LinkedList<int>();
  // Добавляем элементы
  
  // O(n) - читаем элемент с индексом 5
  var value = list.getAt(5);
}

Сравнение со списками (Array vs LinkedList)

Операция         Array   LinkedList
─────────────────────────────────────
Read (по index)  O(1)    O(n)         ← ВОПРОС
Read (по value)  O(n)    O(n)
Insert (начало)  O(n)    O(1)
Insert (конец)   O(1)    O(1)
Insert (середина)O(n)    O(n)
Delete (начало)  O(n)    O(1)
Delete (конец)   O(1)    O(n)
Delete (индекс)  O(n)    O(n)

Практический пример: худший случай

class LinkedList<T> {
  Node<T>? head;
  int length = 0;
  
  void add(T value) {
    var newNode = Node(value);
    if (head == null) {
      head = newNode;
    } else {
      var current = head;
      while (current?.next != null) {
        current = current.next;  // O(n) - проходим весь список
      }
      current?.next = newNode;
    }
    length++;
  }
  
  T? getAt(int index) {
    // Худший случай: O(n) когда индекс в конце
    var current = head;
    for (int i = 0; i < index && current != null; i++) {
      current = current.next;
    }
    return current?.value;
  }
}

void main() {
  var list = LinkedList<int>();
  
  // Добавляем 1000 элементов
  for (int i = 0; i < 1000; i++) {
    list.add(i);
  }
  
  // O(1000) - худший случай
  var lastElement = list.getAt(999);
  
  // O(1) - лучший случай
  var firstElement = list.getAt(0);
}

Анализ сложности разных операций

1. Read первого элемента - O(1)

T? getFirst() => head?.value;  // Прямой доступ

2. Read середины - O(n/2) = O(n)

var middle = list.getAt(500);  // Нужно пройти половину

3. Read последнего - O(n)

var last = list.getAt(length - 1);  // Нужно пройти весь список

Оптимизация: Doubly Linked List

Для больших списков можно использовать двусвязный список:

class DNode<T> {
  T value;
  DNode<T>? next;
  DNode<T>? prev;  // Обратная ссылка
  DNode(this.value);
}

class DoublyLinkedList<T> {
  DNode<T>? head;
  DNode<T>? tail;
  int length = 0;

  T? getAt(int index) {
    if (index < length ~/ 2) {
      // Идём от начала
      var current = head;
      for (int i = 0; i < index; i++) {
        current = current?.next;
      }
      return current?.value;
    } else {
      // Идём с конца - быстрее!
      var current = tail;
      for (int i = length - 1; i > index; i--) {
        current = current?.prev;
      }
      return current?.value;
    }
  }
}

Когда использовать LinkedList

При O(n) read, связные списки обычно НЕ рекомендуются, если нужно много операций чтения:

✓ Используйте LinkedList когда:

• Много операций вставки/удаления в начало
• Нужна динамическая структура
• Память фрагментирована
• Нет доступа по индексу

✗ НЕ используйте LinkedList когда:

• Много операций чтения
• Нужна быстрая случайная выборка
• Размер предсказуем
• Можно использовать List/Array

В Dart используйте List

В реальных проектах Flutter для 99% случаев лучше использовать встроенный List<T> с O(1) доступом:

// ✓ ХОРОШО - O(1) доступ
List<int> numbers = [1, 2, 3, 4, 5];
var element = numbers[3];  // O(1)

// ✗ РЕДКО - O(n) доступ
// LinkedList используется редко и только для специфических случаев

Временная сложность read в связном списке — O(n) — это главный недостаток структуры и основная причина, почему обычные массивы часто предпочтительнее для большинства приложений.