Listy dwukierunkowe - implementacja i zastosowania

1. Czym jest lista dwukierunkowa?

Lista dwukierunkowa (doubly linked list) to struktura danych, gdzie każdy węzeł zawiera: - Dane (wartość) - Wskaźnik do następnego węzła (next) - Wskaźnik do poprzedniego węzła (prev)

Wizualizacja:

       ┌─────┐      ┌─────┐      ┌─────┐      ┌─────┐
None ← │  3  │ ←──→ │  7  │ ←──→ │  1  │ ←──→ │  9  │ → None
       │prev │      │prev │      │prev │      │prev │
       │data │      │data │      │data │      │data │
       │next │      │next │      │next │      │next │
       └─────┘      └─────┘      └─────┘      └─────┘
         HEAD                                    TAIL

Różnice vs lista jednokierunkowa:

Cecha Jednokierunkowa Dwukierunkowa
Wskaźniki w węźle 1 (next) 2 (prev, next)
Przechodzenie wstecz Niemożliwe Możliwe
Usuwanie węzła O(n) O(1) z węzłem
Zużycie pamięci Mniejsze Większe
Implementacja Prostsza Bardziej złożona

2. Implementacja węzła

Tworzenie i łączenie węzłów:

3. Implementacja listy dwukierunkowej

4. Dodawanie elementów

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

Krok po kroku:

1. Przed:  HEAD → [7|↔] ↔ [1|↔] ↔ [9] ← TAIL

2. Nowy węzeł: [3|↔]

3. Łączenie:
   [3] → [7]
   [7] ← [3]
   HEAD = [3]

4. Po:     HEAD → [3|↔] ↔ [7|↔] ↔ [1|↔] ↔ [9] ← TAIL

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

Przykład:

4.3. Wstawianie po określonym węźle – O(1)

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

5. Usuwanie elementów

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

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

Uwaga: W liście jednokierunkowej pop_last() to O(n), tutaj O(1)!

5.3. Usuwanie określonego węzła – O(1)

To jest ogromna zaleta listy dwukierunkowej!

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

6. Wyszukiwanie i dostęp

6.1. Wyszukiwanie węzła – O(n)

6.2. Dostęp po indeksie – O(n)

7. Odwracanie listy

7.1. Iteracyjne odwracanie – O(n)

Przykład:

8. Iterowanie w obu kierunkach

8.1. Iterator do przodu

8.2. Iterator do tyłu

Przykład:

9. Pełna implementacja

10. Złożoność czasowa

Operacja Jednokierunkowa Dwukierunkowa
prepend(data) O(1) O(1)
append(data) O(n)* lub O(1) O(1)
pop_first() O(1) O(1)
pop_last() O(n) O(1)
delete_node(node) O(n) O(1)
insert_after(node) – O(1)
reverse() O(n) O(n)

*bez tail pointer

Kluczowa przewaga: O(1) dla operacji na końcu i usuwania węzła!

11. Praktyczne zastosowania

11.1. Deque (Double-Ended Queue)

11.2. LRU Cache (Least Recently Used)

11.3. Historia przeglądarki (z nawigacją)

11.4. Edytor tekstu (Undo/Redo)

12. Lista cykliczna

Zastosowania: - Odtwarzacz muzyki (zapętlona playlista) - Round-robin scheduling - Bufory cykliczne

13. Porównanie z collections.deque

Python ma wbudowaną implementację deque:

Kiedy używać własnej implementacji? - Nauka struktur danych - Potrzebujesz dostępu do węzłów (LRU cache) - Specyficzne wymagania

Kiedy używać collections.deque? - Większość praktycznych zastosowań - Zoptymalizowana implementacja w C - Prosta i szybka

14. Typowe błędy

Błąd 1: Zapomnienie o aktualizacji prev

Błąd 2: Nieprawidłowa obsługa tail przy usuwaniu

15. Podsumowanie

Lista dwukierunkowa to rozszerzenie listy jednokierunkowej:

  • Dwa wskaźniki w każdym węźle (prev, next)
  • O(1) dla operacji na obu końcach
  • Możliwość przechodzenia w obie strony
  • Idealna do deque, LRU cache, undo/redo

Zalety:

  • O(1) usuwanie z końca
  • O(1) usuwanie dowolnego węzła (jeśli mamy do niego dostęp)
  • Przechodzenie w obie strony
  • Łatwiejsze operacje wstawiania/usuwania

Wady:

  • Więcej pamięci (dodatkowy wskaźnik)
  • Bardziej skomplikowana implementacja
  • Więcej operacji przy modyfikacji

Kiedy używać:

  • Deque (kolejka dwustronna)
  • LRU Cache
  • Historia z nawigacją (undo/redo)
  • Często usuwasz z końca

Co dalej warto poznać:

  • Skip list
  • XOR linked list
  • Sentinel nodes (węzły strażnicze)
  • collections.deque w praktyce
Wróć do spisu lekcji