Ինչպե՞ս գնահատել կապակցված ցանկում տարրերի թարմացման գործողության ալգորիթմական բարդությունը։

Մի տարրային փոփոխությունը կապակցված ցանկում սովորաբար պահանջում է նախ գտնել այդ տարրին, ապա փոխել նրա արժեքը:

• Եթե ունեք նշիչ կամ հղում անհրաժեշտ հանգույցին, արժեքի փոփոխությունը O(1) գործողություն է:
• Եթե նախ պետք է գտնել տարրն ըստ ինդեքսի կամ արժեքի, որոնումը տևում է O(n), որտեղ n — ցանկի տարրերի քանակն է:

Dart (Flutter) օրինակով:

class Node {
  int value;
  Node? next;

  Node(this.value);
}

void updateNodeValue(Node head, int index, int newValue) {
  Node? current = head;
  int i = 0;
  while (current != null && i < index) {
    current = current.next;
    i++;
  }
  if (current != null) {
    current.value = newValue; // O(1) թարմացում
  }
}

Ընդհանուր առմամբ, ինդեքսով տարրն թարմացնելու ընդհանուր բարդությունը — O(n), եթե չունեք ուղղակի մուտք հանգույցին։