Listy jednokierunkowe

1. Czym jest lista jednokierunkowa?

Lista jednokierunkowa (singly linked list) to dynamiczna struktura danych składająca się z węzłów (nodes), gdzie każdy węzeł zawiera: - Dane (wartość) - Wskaźnik do następnego węzła

Wizualizacja:

HEAD → [3|→] → [7|→] → [1|→] → [9|→] → None
       dane next  dane next  dane next  dane next

Różnice vs lista pythonowa (list):

Cecha Lista pythonowa Lista jednokierunkowa
Dostęp po indeksie O(1) O(n)
Wstawianie na początku O(n) O(1)
Wstawianie na końcu O(1)* O(n) lub O(1) z tail
Usuwanie z początku O(n) O(1)
Zużycie pamięci Ciągły blok Rozproszona

2. Implementacja węzła

Każdy węzeł zawiera dane i referencję do następnego węzła.

Tworzenie węzłów:

3. Implementacja listy jednokierunkowej

Użycie:

4. Dodawanie elementów

4.1. Dodawanie na początku – O(1)

Krok po kroku:

1. Przed:  HEAD → [7|→] → [1|→] → None

2. Tworzenie nowego węzła:
   new_node = [3|→]

3. Połączenie:
   [3|→] → [7|→] → [1|→] → None

4. Po:     HEAD → [3|→] → [7|→] → [1|→] → None

Przykład:

4.2. Dodawanie na końcu – O(n)

Przykład:

4.3. Wstawianie na określonej pozycji – O(n)

Przykład:

5. Usuwanie elementów

5.1. Usuwanie z początku – O(1)

Przykład:

5.2. Usuwanie z końca – O(n)

5.3. Usuwanie przez wartość – O(n)

Przykład:

6. Wyszukiwanie

6.1. Wyszukiwanie przez wartość – O(n)

6.2. Pobieranie przez indeks – O(n)

Przykład:

7. Odwracanie listy

7.1. Iteracyjne odwracanie – O(n)

Wizualizacja:

1. Przed:  HEAD → [1|→] → [2|→] → [3|→] → None

2. Iteracja 1:
   prev = None, current = [1|→]
   [1|→] None ← [1|None]
   prev = [1|None], current = [2|→]

3. Iteracja 2:
   [1|None] ← [2|→] [1|None]
   prev = [2|→] [1|None], current = [3|→]

4. Po:     HEAD → [3|→] → [2|→] → [1|→] → None

Przykład:

7.2. Rekurencyjne odwracanie – O(n)

8. Zaawansowane operacje

8.1. Znajdowanie środkowego elementu – O(n)

Jak to działa: - slow porusza się o 1 krok - fast porusza się o 2 kroki - Gdy fast dojdzie do końca, slow będzie w środku

8.2. Wykrywanie cyklu (pętli) – O(n)

8.3. Usuwanie duplikatów – O(n²) lub O(n) ze zbiorem

Przykład:

9. Pełna implementacja z iter

Użycie z iteracją:

10. Złożoność czasowa i pamięciowa

Złożoność czasowa:

Operacja Złożoność
prepend(data) O(1)
append(data) O(n)
insert(data, index) O(n)
pop_first() O(1)
pop_last() O(n)
remove(data) O(n)
search(data) O(n)
get(index) O(n)
reverse() O(n)

Złożoność pamięciowa:

  • O(n) – każdy węzeł zajmuje pamięć na dane + wskaźnik

11. Optymalizacja – lista z tail pointer

Zalety: - append() teraz O(1) zamiast O(n)

Wady: - Więcej pamięci (dodatkowy wskaźnik) - Bardziej skomplikowana implementacja

12. Praktyczne zastosowania

12.1. Implementacja stosu

12.2. Historia przeglądarki (uproszczona)

13. Lista vs Lista jednokierunkowa

Kiedy używać listy jednokierunkowej?

✅ Częste dodawanie/usuwanie z początku ✅ Nie potrzebujesz dostępu po indeksie ✅ Implementacja innych struktur (stos, kolejka) ✅ Pamięć dynamiczna (rozmiar nieznany z góry)

Kiedy używać listy pythonowej?

✅ Potrzebujesz szybkiego dostępu po indeksie ✅ Często sortujemy lub przeszukujemy ✅ Prostota implementacji ✅ Większość przypadków użycia

14. Typowe błędy i pułapki

Błąd 1: Zapomnienie o None

Błąd 2: Zgubienie referencji

15. Podsumowanie

Lista jednokierunkowa to podstawowa dynamiczna struktura danych:

  • Każdy węzeł wskazuje tylko na następny
  • Doskonała do stosu (LIFO)
  • O(1) dla operacji na początku
  • O(n) dla operacji na końcu (bez tail pointer)
  • Zużywa więcej pamięci niż tablica (wskaźniki)

Zalety:

  • Dynamiczny rozmiar
  • Szybkie wstawianie/usuwanie z początku
  • Brak przepełnienia (jak w tablicach statycznych)

Wady:

  • Brak dostępu po indeksie O(1)
  • Dodatkowa pamięć na wskaźniki
  • Nie cache-friendly (rozproszona w pamięci)

Co dalej warto poznać:

  • Lista dwukierunkowa (prev + next)
  • Lista cykliczna
  • Skip list
  • XOR linked list
Wróć do spisu lekcji