{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "k00",
   "metadata": {},
   "source": [
    "# Lista z dowiązaniami (linked list)\n",
    "\n",
    "*Wersja notatnika: 2026-10-08 · na bazie wersji z 2025-10-11 · przygotowanie: dr inż. Szczepan Górtowski*\n",
    "\n",
    "Na zajęciach 5 pisałeś klasy. Teraz zbudujesz z nich **strukturę danych**: listę z dowiązaniami, złożoną z węzłów\n",
    "(`Node`), z których każdy wskazuje następny. Zobaczysz, kiedy jest szybsza od listy Pythona, ile kosztuje w pamięci\n",
    "i gdzie Python sam z niej korzysta.\n",
    "\n",
    "### Jak korzystać\n",
    "1. Uruchamiaj komórki po kolei: `Ctrl + Enter` albo `Shift + Enter`.\n",
    "2. Przy ramkach **Przewidź, zanim uruchomisz** najpierw zgadnij, potem uruchom, na końcu rozwiń odpowiedź.\n",
    "3. Zadania 6.0–6.5 budują **jedną** klasę `LinkedList` krok po kroku: każde kolejne dziedziczy po poprzednim\n",
    "   (`class LinkedList(LinkedList)`), więc metody z wcześniejszych zadań zostają. Rób je po kolei."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k01",
   "metadata": {},
   "source": [
    "## Spis treści\n",
    "1. Czym jest lista z dowiązaniami?\n",
    "2. Węzeł (`Node`) — definicja i rola\n",
    "3. Klasa `LinkedList` — głowa (`head`) i ogon (`tail`)\n",
    "4. Podstawowe operacje i ich złożoność (**poprawione**)\n",
    "5. Reprezentacja tekstowa listy — `__str__`\n",
    "6. **Nowe:** kiedy lista z dowiązaniami wygrywa — pomiar czasu i pamięci\n",
    "7. **Nowe:** gdzie Python sam używa list z dowiązaniami\n",
    "8. Zadania 6.0–6.4 i zadanie 6.5 dla chętnych\n",
    "9. Co dalej?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k02",
   "metadata": {},
   "source": [
    "## 1) Czym jest lista z dowiązaniami?\n",
    "\n",
    "**Lista z dowiązaniami** to sekwencja **węzłów**: każdy przechowuje wartość i **wskaźnik na następny** węzeł\n",
    "(w wersji dwukierunkowej — także na poprzedni). Pierwszy węzeł to **głowa** (*head*), ostatni — **ogon** (*tail*).\n",
    "Głowa nie ma poprzednika, ogon nie ma następnika (`next = None`).\n",
    "\n",
    "```\n",
    "head                                   tail\n",
    " │                                      │\n",
    " ▼                                      ▼\n",
    "[10 | •]──►[20 | •]──►[30 | •]──►[40 | None]\n",
    "```\n",
    "\n",
    "W odróżnieniu od listy Pythona (tablicy z zajęć 2) węzły **nie leżą obok siebie** w pamięci. Do elementu nr `i`\n",
    "dojdziesz tylko, przechodząc po strzałkach od głowy."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k03",
   "metadata": {},
   "source": [
    "## 2) Węzeł (`Node`) — definicja i rola\n",
    "\n",
    "Węzeł przechowuje **wartość** (`value`) i **wskaźnik na następny węzeł** (`next`). To klocek, z którego składa się lista."
   ]
  },
  {
   "cell_type": "code",
   "id": "k04",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.value = data\n",
    "        self.next = None\n",
    "\n",
    "n = Node(10)\n",
    "print(n.value, n.next)  # 10 None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k05",
   "metadata": {},
   "source": [
    "## 3) Klasa `LinkedList` — głowa (`head`) i ogon (`tail`)\n",
    "\n",
    "Klasa `LinkedList` pamięta tylko dwa węzły: **początek** i **koniec**. Reszta listy to łańcuch wskaźników `next`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k06",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "\n",
    "ll = LinkedList()\n",
    "print(ll.head, ll.tail)  # None None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k07",
   "metadata": {},
   "source": [
    "> **Przewidź, zanim uruchomisz:** łączymy ręcznie trzy węzły. Ile kroków wykona pętla, żeby dojść do ostatniego węzła?\n",
    ">\n",
    "> <details><summary>Odpowiedź</summary>\n",
    ">\n",
    "> Dwa przejścia po `next` (z 10 do 20 i z 20 do 30). Do elementu nr `i` potrzebujesz `i` kroków — to O(n), a nie O(1) jak w liście Pythona.\n",
    ">\n",
    "> </details>"
   ]
  },
  {
   "cell_type": "code",
   "id": "k08",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "a = Node(10)\n",
    "b = Node(20)\n",
    "c = Node(30)\n",
    "a.next = b\n",
    "b.next = c\n",
    "\n",
    "kroki = 0\n",
    "current = a\n",
    "while current.next is not None:\n",
    "    current = current.next\n",
    "    kroki += 1\n",
    "print(\"ostatni:\", current.value, \"| kroków:\", kroki)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k09",
   "metadata": {},
   "source": [
    "## 4) Podstawowe operacje i ich złożoność\n",
    "\n",
    "| Operacja | Lista jednokierunkowa | Lista dwukierunkowa | Lista Pythona |\n",
    "|---|---|---|---|\n",
    "| wstaw na początku | **O(1)** | O(1) | O(n) |\n",
    "| wstaw na końcu (z `tail`) | **O(1)** | O(1) | O(1) |\n",
    "| usuń z początku | **O(1)** | O(1) | O(n) |\n",
    "| usuń z końca | **O(n)** — trzeba znaleźć przedostatni | O(1) | O(1) |\n",
    "| element nr `i`, szukanie | O(n) | O(n) | O(1) / O(n) |\n",
    "\n",
    "*Poprawka do wersji z 2025 r.:* usuwanie z końca listy **jednokierunkowej** nie jest O(1). Ogon nie wie,\n",
    "kto go poprzedza, więc trzeba przejść całą listę od głowy, żeby znaleźć przedostatni węzeł.\n",
    "\n",
    "**Wstawianie na początku** (`insert_at_beginning`): nowy węzeł, `new.next = head`, `head = new`;\n",
    "jeśli lista była pusta — także `tail = new`.\n",
    "\n",
    "**Wstawianie na końcu** (`insert_at_end`): nowy węzeł; jeśli lista nie jest pusta — `tail.next = new`;\n",
    "na końcu `tail = new` (a dla pustej listy także `head = new`).\n",
    "\n",
    "**Usuwanie**: z początku — `head = head.next` (pusta lista po usunięciu → `tail = None`);\n",
    "z końca — znajdź przedostatni węzeł, ustaw w nim `next = None` i zrób go ogonem.\n",
    "**Pamiętaj o przypadkach brzegowych:** lista pusta i lista z jednym węzłem."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k10",
   "metadata": {},
   "source": [
    "## 5) Reprezentacja tekstowa listy — `__str__`\n",
    "\n",
    "`__str__` z zajęć 5 przyda się do podglądu: zacznij od `current = self.head`, dopóki `current is not None`\n",
    "dopisuj `str(current.value)` do listy pomocniczej i przechodź do `current.next`; na końcu połącz spacją."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k11",
   "metadata": {},
   "source": [
    "## 6) Nowe: kiedy lista z dowiązaniami wygrywa — pomiar czasu i pamięci\n",
    "\n",
    "Wstawiamy `n` liczb **na początek**: do listy Pythona (`insert(0, x)` — przesuwa wszystko, O(n)),\n",
    "do listy z dowiązaniami (O(1)) i do `deque` (`appendleft`, O(1), napisana w C)."
   ]
  },
  {
   "cell_type": "code",
   "id": "k12",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import time\n",
    "from collections import deque\n",
    "\n",
    "def na_poczatek_lista(n):\n",
    "    lista = []\n",
    "    for i in range(n):\n",
    "        lista.insert(0, i)\n",
    "\n",
    "def na_poczatek_wezly(n):\n",
    "    head = None\n",
    "    for i in range(n):\n",
    "        wezel = Node(i)\n",
    "        wezel.next = head\n",
    "        head = wezel\n",
    "\n",
    "def na_poczatek_deque(n):\n",
    "    d = deque()\n",
    "    for i in range(n):\n",
    "        d.appendleft(i)\n",
    "\n",
    "def zmierz(funkcja, n):\n",
    "    start = time.perf_counter()\n",
    "    funkcja(n)\n",
    "    return (time.perf_counter() - start) * 1000   # ms\n",
    "\n",
    "rozmiary = [1_000, 5_000, 20_000, 50_000]\n",
    "czasy = {\"list.insert(0)\": [], \"węzły\": [], \"deque\": []}\n",
    "for n in rozmiary:\n",
    "    czasy[\"list.insert(0)\"].append(zmierz(na_poczatek_lista, n))\n",
    "    czasy[\"węzły\"].append(zmierz(na_poczatek_wezly, n))\n",
    "    czasy[\"deque\"].append(zmierz(na_poczatek_deque, n))\n",
    "for nazwa, wyniki in czasy.items():\n",
    "    opis = \"  \".join(f\"{t:8.1f}\" for t in wyniki)\n",
    "    print(f\"{nazwa:<15} {opis}  ms dla n = {rozmiary}\")"
   ]
  },
  {
   "cell_type": "code",
   "id": "k13",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.figure(figsize=(8, 4))\n",
    "for nazwa, wyniki in czasy.items():\n",
    "    plt.plot(rozmiary, wyniki, marker=\"o\", label=nazwa)\n",
    "plt.xlabel(\"n — ile liczb wstawiamy na początek\")\n",
    "plt.ylabel(\"czas [ms]\")\n",
    "plt.title(\"list.insert(0) rośnie jak n², węzły i deque — jak n\")\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k14",
   "metadata": {},
   "source": [
    "Szybkość ma swoją cenę: każdy węzeł to osobny obiekt z wartością, wskaźnikiem i słownikiem atrybutów.\n",
    "`tracemalloc` zmierzy, ile pamięci zajmuje 10 000 liczb w każdej strukturze. `__slots__` (z dokumentacji Pythona:\n",
    "*„The space saved over using __dict__ can be significant”*) zabiera węzłom słownik atrybutów."
   ]
  },
  {
   "cell_type": "code",
   "id": "k15",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import tracemalloc\n",
    "\n",
    "class NodeSlots:\n",
    "    __slots__ = (\"value\", \"next\")\n",
    "\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "def pamiec(budowa):\n",
    "    tracemalloc.start()\n",
    "    obiekt = budowa()\n",
    "    zajete, _ = tracemalloc.get_traced_memory()\n",
    "    tracemalloc.stop()\n",
    "    return zajete / N\n",
    "\n",
    "def wezly(klasa):\n",
    "    head = None\n",
    "    for i in range(N):\n",
    "        wezel = klasa(i)\n",
    "        wezel.next = head\n",
    "        head = wezel\n",
    "    return head\n",
    "\n",
    "N = 10_000\n",
    "print(f\"lista Pythona: {pamiec(lambda: list(range(N))):6.1f} B na liczbę\")\n",
    "print(f\"węzły:         {pamiec(lambda: wezly(Node)):6.1f} B na liczbę\")\n",
    "print(f\"__slots__:     {pamiec(lambda: wezly(NodeSlots)):6.1f} B na liczbę\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k16",
   "metadata": {},
   "source": [
    "## 7) Nowe: gdzie Python sam używa list z dowiązaniami\n",
    "\n",
    "- **`collections.deque`** (zajęcia 2 i 4) — komentarz w kodzie CPython: *„Data for deque objects is stored in\n",
    "  a doubly-linked list of fixed length blocks.”* Bloki mają po 64 elementy: to lista dwukierunkowa, ale bez\n",
    "  osobnego obiektu na każdą liczbę — dlatego `deque` wygrała pomiar.\n",
    "- **`collections.OrderedDict`** — *„The circular doubly linked list starts and ends with a sentinel element.”*\n",
    "  Słownik znajduje węzeł w O(1), a lista pamięta kolejność i pozwala przenieść element na koniec w O(1).\n",
    "  Tak działa pamięć podręczna LRU: najdawniej używany element czeka na początku listy.\n",
    "\n",
    "### Lista dwukierunkowa\n",
    "\n",
    "Każdy węzeł zna **następny** i **poprzedni**. Usunięcie ogona to wtedy O(1): `tail = tail.prev`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k17",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Node2:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.prev = None\n",
    "        self.next = None\n",
    "\n",
    "a, b, c = Node2(1), Node2(2), Node2(3)\n",
    "a.next, b.prev = b, a\n",
    "b.next, c.prev = c, b\n",
    "tail = c\n",
    "tail = tail.prev          # usunięcie ogona: O(1), bez szukania\n",
    "tail.next = None\n",
    "print(\"nowy ogon:\", tail.value, \"| poprzednik ogona:\", tail.prev.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k18",
   "metadata": {},
   "source": [
    "## 8) Zadanie 6.0 — szkielety `Node` i `LinkedList`\n",
    "\n",
    "Uzupełnij `__str__` w `LinkedList`: zwraca wartości węzłów oddzielone **pojedynczą spacją**, a dla pustej listy —\n",
    "pusty napis `\"\"`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k19",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "\n",
    "    def __str__(self):\n",
    "        return \"\"  # TODO: przejdź od head po next i zbierz wartości"
   ]
  },
  {
   "cell_type": "code",
   "id": "k20",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    ll = LinkedList()\n",
    "    assert str(ll) == \"\"\n",
    "    a, b, c = Node(1), Node(2), Node(3)\n",
    "    ll.head, a.next, b.next, ll.tail = a, b, c, c\n",
    "    assert str(ll) == \"1 2 3\"\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 6.0 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k21",
   "metadata": {},
   "source": [
    "## Zadanie 6.1 — wstawianie na początku i na końcu\n",
    "\n",
    "Dopisz metody `insert_at_beginning(self, value)` i `insert_at_end(self, value)`. Pamiętaj o aktualizacji\n",
    "`head` i `tail` oraz o pustej liście. Klasa **dziedziczy** po `LinkedList` z zadania 6.0 — `__str__` już ma."
   ]
  },
  {
   "cell_type": "code",
   "id": "k22",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class LinkedList(LinkedList):   # dziedziczy __init__ i __str__ z zadania 6.0\n",
    "    def insert_at_beginning(self, value):\n",
    "        pass  # TODO\n",
    "\n",
    "    def insert_at_end(self, value):\n",
    "        pass  # TODO"
   ]
  },
  {
   "cell_type": "code",
   "id": "k23",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    ll = LinkedList()\n",
    "    for v in [2, 3]:\n",
    "        ll.insert_at_end(v)\n",
    "    ll.insert_at_beginning(1)\n",
    "    ll.insert_at_end(4)\n",
    "    assert str(ll) == \"1 2 3 4\"\n",
    "    assert ll.head.value == 1 and ll.tail.value == 4\n",
    "    jeden = LinkedList()\n",
    "    jeden.insert_at_beginning(7)\n",
    "    assert jeden.head is jeden.tail, 'jeden węzeł: head is tail'\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 6.1 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k24",
   "metadata": {},
   "source": [
    "## Zadanie 6.2 — wyszukiwanie `search`\n",
    "\n",
    "Dopisz metodę `search(self, value) -> bool`: `True`, jeśli wartość jest w liście, inaczej `False`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k25",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class LinkedList(LinkedList):   # dziedziczy wszystko z 6.0–6.1\n",
    "    def search(self, value) -> bool:\n",
    "        return False  # TODO: przejdź po węzłach od head"
   ]
  },
  {
   "cell_type": "code",
   "id": "k26",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    ll = LinkedList()\n",
    "    for v in [10, 20, 30]:\n",
    "        ll.insert_at_end(v)\n",
    "    assert ll.search(10) and ll.search(20) and ll.search(30)\n",
    "    assert not ll.search(40)\n",
    "    assert not LinkedList().search(1)\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 6.2 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k27",
   "metadata": {},
   "source": [
    "## Zadanie 6.3 — usuwanie na początku i na końcu\n",
    "\n",
    "*Tego zadania brakowało w oryginalnej wersji, choć było w spisie treści.*\n",
    "\n",
    "Dopisz `delete_at_beginning()` i `delete_at_end()`. Obie **zwracają** usuniętą wartość, a dla pustej listy podnoszą\n",
    "`IndexError` (tak jak `list.pop()`). Po usunięciu ostatniego węzła `head` i `tail` mają być `None`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k28",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class LinkedList(LinkedList):\n",
    "    def delete_at_beginning(self):\n",
    "        pass  # TODO\n",
    "\n",
    "    def delete_at_end(self):\n",
    "        pass  # TODO: znajdź przedostatni węzeł"
   ]
  },
  {
   "cell_type": "code",
   "id": "k29",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    ll = LinkedList()\n",
    "    for v in [1, 2, 3]:\n",
    "        ll.insert_at_end(v)\n",
    "    assert ll.delete_at_beginning() == 1\n",
    "    assert ll.delete_at_end() == 3\n",
    "    assert str(ll) == \"2\" and ll.head is ll.tail\n",
    "    assert ll.delete_at_end() == 2\n",
    "    assert ll.head is None and ll.tail is None\n",
    "    try:\n",
    "        ll.delete_at_beginning()\n",
    "        pusta = False\n",
    "    except IndexError:\n",
    "        pusta = True\n",
    "    assert pusta, 'pusta lista powinna dać IndexError'\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 6.3 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k30",
   "metadata": {},
   "source": [
    "## Zadanie 6.4 — odwracanie listy `reverse`\n",
    "\n",
    "*Tego zadania też brakowało w oryginalnej wersji.*\n",
    "\n",
    "Odwróć listę **w miejscu**, bez tworzenia nowych węzłów: `1 2 3 4` → `4 3 2 1`. Klasyczny sposób to trzy\n",
    "wskaźniki: `prev`, `current` i `nxt`. W każdym kroku: zapamiętaj `nxt = current.next`, odwróć strzałkę\n",
    "`current.next = prev`, przesuń `prev` i `current` o jeden węzeł. Nie zapomnij o `head` i `tail`."
   ]
  },
  {
   "cell_type": "code",
   "id": "k31",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class LinkedList(LinkedList):\n",
    "    def reverse(self):\n",
    "        pass  # TODO: prev, current, nxt"
   ]
  },
  {
   "cell_type": "code",
   "id": "k32",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    ll = LinkedList()\n",
    "    for v in [1, 2, 3, 4]:\n",
    "        ll.insert_at_end(v)\n",
    "    ll.reverse()\n",
    "    assert str(ll) == \"4 3 2 1\"\n",
    "    assert ll.head.value == 4 and ll.tail.value == 1 and ll.tail.next is None\n",
    "    pusta = LinkedList()\n",
    "    pusta.reverse()\n",
    "    assert str(pusta) == \"\"\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 6.4 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k33",
   "metadata": {},
   "source": [
    "## Zadanie 6.5 dla chętnych — `len()` i `in` dla twojej listy\n",
    "\n",
    "Metody specjalne z zajęć 5: dopisz `__len__` (liczba węzłów) i `__contains__` (użyj `search`). Wtedy\n",
    "`len(ll)` i `20 in ll` działają jak dla listy Pythona."
   ]
  },
  {
   "cell_type": "code",
   "id": "k34",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "class LinkedList(LinkedList):\n",
    "    pass  # TODO: __len__ i __contains__"
   ]
  },
  {
   "cell_type": "code",
   "id": "k35",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Sprawdź\n",
    "try:\n",
    "    ll = LinkedList()\n",
    "    for v in [10, 20, 30]:\n",
    "        ll.insert_at_end(v)\n",
    "    assert len(ll) == 3 and len(LinkedList()) == 0\n",
    "    assert 20 in ll and 40 not in ll\n",
    "except AssertionError:\n",
    "    print(\"❌ Testy nie przeszły — popraw rozwiązanie.\")\n",
    "except Exception as e:\n",
    "    print(\"❌ Kod kończy się błędem:\", type(e).__name__, e)\n",
    "else:\n",
    "    print(\"✅ Zadanie 6.5 zaliczone!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "k36",
   "metadata": {},
   "source": [
    "## Co dalej?\n",
    "\n",
    "- Rozszerz listę o `insert_after(node, value)`, `delete(value)` (pierwsze wystąpienie) i `__iter__`, żeby działało\n",
    "  `for x in ll`.\n",
    "- Zbuduj listę **dwukierunkową** z sekcji 7 i porównaj `delete_at_end` w obu wersjach.\n",
    "- Zobacz, jak Python Tutor (pythontutor.com) rysuje węzły i strzałki dla zadania 6.4.\n",
    "\n",
    "## Zadania dodatkowe\n",
    "\n",
    "1. Dlaczego `delete_at_end` w liście jednokierunkowej jest O(n), a `insert_at_end` — O(1)?\n",
    "2. Pomiar z sekcji 6: dlaczego `deque` jest szybsza od twoich węzłów, choć obie mają O(1)?\n",
    "3. Kiedy wybrałbyś listę z dowiązaniami zamiast listy Pythona? Podaj jeden przykład."
   ]
  }
 ],
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  }
 }
}