Linked list

push-front O(1) · search O(n)

(Jednosměrný) spojový seznam ukládá každou hodnotu do uzlu, který ukazuje na další, a vepředu je ukazatel na hlavu. Přidání nebo odebrání na začátku je O(1) — jen se přepojí ukazatel — ale není náhodný přístup: najít k-tý prvek nebo hodnotu znamená projít řetěz od hlavy, což je O(n). Spojové seznamy stojí za zásobníky, frontami, seznamy sousednosti a dalším.

Spojový seznam
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. pushFront nechá nový uzel ukazovat na starou hlavu a pak na něj přesune hlavu (O(1)).
  2. pushBack dojde na konec a připojí nový uzel.
  3. search jde od hlavy a porovnává každý uzel, dokud nesedí nebo nenarazí na null.
  4. remove dojde na shodný uzel a přepojí jeho předchůdce za něj.

Pseudokód

1pushFront(v):  node.next ← head; head ← node      # O(1)2pushBack(v):   walk to the tail, link the new node # O(n)34search(v):5  cur ← head6  while cur ≠ null:7    if cur.value = v: return cur8    cur ← cur.next                                  # O(n)910remove(v):  relink the predecessor past the match