Klasa Node i tworzenie listy
Zdefiniują Państwo dataclass Node, ręcznie zbudują listy przez łączenie węzłów oraz napiszą funkcje pomocnicze insert/delete/print wizualizujące zmiany wskaźników.
Klasa Node i tworzenie listy to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Czym jest lista wiązana?
Lista wiązana to sekwencja węzłów, z których każdy przechowuje wartość oraz wskaźnik do następnego węzła. W przeciwieństwie do tablic węzły są rozproszone w pamięci — nie ma dostępu O(1) na podstawie indeksu. W zamian można wykonywać wstawianie i usuwanie w czasie O(1) w dowolnym znanym miejscu, bez przesuwania elementów.
W języku Python każdy węzeł reprezentujemy za pomocą niewielkiej klasy przechowującej val i next. Połączenie węzłów tworzy listę, a next ostatniego węzła ma wartość None, sygnalizującą koniec.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Budowanie list z tablic
Podczas rozmów kwalifikacyjnych często otrzymają Państwo listę i prośbę o utworzenie jej odpowiednika w postaci listy wiązanej lub odwrotnie. Warto zapamiętać funkcje pomocnicze build i to_list: build łączy węzły na podstawie tablicy, a to_list przechodzi po liście i zbiera wartości, ułatwiając weryfikację.
Utworzenie listy wiązanej z n elementów zajmuje O(n) czasu i O(n) pamięci. Użycie fikcyjnego pierwszego węzła upraszcza przypadki brzegowe, w których pierwszy węzeł może się zmienić.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Wstawianie na początku i na końcu
Wstawienie nowego węzła na początku zajmuje O(1): należy utworzyć węzeł, ustawić jego next tak, aby wskazywał poprzednią głowę, i zwrócić nowy węzeł jako głowę. Wstawienie na końcu wymaga przejścia do ostatniego węzła (O(n)), a następnie połączenia z nim nowego węzła.
Użycie fikcyjnego pierwszego węzła eliminuje szczególną obsługę pustej listy w obu przypadkach, ponieważ dummy.next zawsze wskazuje rzeczywistą głowę.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneUsuwanie węzła na podstawie wartości
Aby usunąć pierwszy węzeł o danej wartości, należy utrzymywać wskaźnik prev znajdujący się o jeden krok za wskaźnikiem curr. Gdy curr.val == target, należy ustawić prev.next = curr.next, pomijając w ten sposób dany węzeł. Fikcyjny pierwszy węzeł jest tutaj szczególnie pomocny, ponieważ eliminuje szczególny przypadek usuwania rzeczywistej głowy — prev może zawsze rozpoczynać pracę od fikcyjnego węzła.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Wizualizacja zmian wskaźników
Częstym błędem jest utrata dostępu do węzła podczas aktualizowania wskaźników. Przed nadpisaniem zawsze należy zapisać next: saved = curr.next, a dopiero potem wykonać ponowne przypisanie. Przed rozpoczęciem implementacji warto narysować listę jako prostokąty połączone strzałkami i prześledzić na papierze każdą zmianę wskaźnika. Takie wizualne podejście zapobiega przypadkowym błędom związanym z pustymi wskaźnikami podczas rozmów kwalifikacyjnych.
Należy pamiętać, że w Pythonie ponowne przypisanie curr.next nie wpływa na curr, ale utrata referencji do curr.next przed jej zapisaniem oznacza, że nie można już przechodzić dalej po liście.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Listy jedno- i dwukierunkowe
Lista jednokierunkowa przechowuje wyłącznie wskaźnik next, dlatego można ją przeglądać tylko w jednym kierunku. Lista dwukierunkowa przechowuje zarówno prev, jak i next, co umożliwia przechodzenie wstecz w czasie O(1) oraz usuwanie w czasie O(1), jeśli mają Państwo bezpośrednią referencję do węzła (bez konieczności śledzenia wskaźnika prev w pętli).
Pythonowy obiekt collections.deque jest zaimplementowany jako lista dwukierunkowa, dlatego obsługuje appendleft i popleft w czasie O(1). Podczas rozmów kwalifikacyjnych będą Państwo implementować listy jednokierunkowe; listy dwukierunkowe pojawiają się przy projektowaniu pamięci podręcznej LRU.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Funkcje pomocnicze: długość, koniec i wyświetlanie
Podczas każdej rozmowy kwalifikacyjnej dotyczącej list wiązanych warto mieć pod ręką trzy funkcje pomocnicze: length(head) zlicza węzły w czasie O(n), tail(head) zwraca ostatni węzeł w czasie O(n), a print_list(head) formatuje listę na potrzeby debugowania. Dzięki nim mogą się Państwo skupić na głównym algorytmie zamiast ponownie implementować logikę pomocniczą.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Konfiguracja dwóch wskaźników dla list wiązanych
Technika dwóch wskaźników jest równie ważna dla list wiązanych jak dla tablic, ale wskaźniki wskazują węzły listy, a nie indeksy. Typowe konfiguracje obejmują powolny i szybki wskaźnik (szybki porusza się dwa razy szybciej) do znajdowania punktu środkowego i wykrywania cykli oraz parę poprzednik i bieżący element do usuwania i odwracania listy.
Należy zawsze jawnie zainicjalizować oba wskaźniki i ostrożnie obsłużyć sprawdzanie zakończenia listy — fast and fast.next zapobiega błędom związanym z pustymi wskaźnikami, gdy fast znajduje się blisko końca.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)Wzorzec fikcyjnego pierwszego węzła
Wzorzec fikcyjnego pierwszego węzła (węzła wartownika) jest jedną z najbardziej przydatnych technik w zadaniach dotyczących list wiązanych. Dodając przed listą fikcyjny węzeł o wartości 0, nie trzeba osobno obsługiwać pustej listy ani zmiany rzeczywistej głowy. Wynik zawsze znajduje się pod dummy.next. Ten wzorzec pojawia się między innymi przy scalaniu posortowanych list, usuwaniu n-tego elementu od końca oraz partycjonowaniu listy.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Złożoność czasowa i pamięciowa
Większość operacji na listach wiązanych ma następującą złożoność. Dostęp na podstawie indeksu: O(n) — trzeba przejść od głowy listy. Wstawianie/usuwanie przy znanym węźle: O(1) — wystarczy przepiąć wskaźniki. Wstawianie/usuwanie na pozycji k: O(k) — najpierw trzeba przejść odpowiednią liczbę elementów. Wyszukiwanie: O(n) — w najgorszym przypadku trzeba przejść całą listę. Pamięć zajmowana przez wszystkie operacje wykonywane w miejscu wynosi O(1) (z wyłączeniem dodatkowych struktur danych).
Dla porównania: tablice oferują dostęp w czasie O(1), ale wstawianie i usuwanie zajmuje O(n) z powodu przesuwania elementów. Listy wiązane są lepszym wyborem, gdy często wykonuje się wstawianie i usuwanie na dowolnych pozycjach.
Wskazówki dotyczące list wiązanych podczas rozmowy kwalifikacyjnej
Przed napisaniem kodu dotyczącego listy wiązanej należy narysować ją za pomocą prostokątów i strzałek. Warto głośno potwierdzić przypadki brzegowe: pustą listę, pojedynczy węzeł oraz parzystą i nieparzystą długość. Należy użyć fikcyjnego pierwszego węzła, aby uprościć warunki brzegowe. Trzeba też zawsze wcześnie sprawdzać if not head. Po napisaniu kodu warto prześledzić rozwiązanie dla listy złożonej z trzech węzłów, aby wychwycić błędy wskaźników, zanim zrobi to osoba prowadząca rozmowę.
Większość błędów w przypadku list wiązanych pochodzi z jednego z trzech źródeł: niezapisania next przed jego nadpisaniem, błędu o jeden w warunku zakończenia albo nieobsłużenia przypadku zmiany głowy — fikcyjny węzeł całkowicie eliminuje ten trzeci problem.
Szybki test
Sprawdź swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: lista wiązana jest zbudowana z obiektów Node zawierających pola val i next, wzorzec fikcyjnego pierwszego węzła eliminuje przypadki brzegowe związane ze zmianą głowy, a konfiguracja dwóch wskaźników slow-fast jest podstawą znajdowania punktu środkowego i wykrywania cykli. W następnej części zajmiemy się odwracaniem listy wiązanej — jednym z najczęściej spotykanych zadań dotyczących wskaźników.
Często zadawane pytania
Czy lekcja „Klasa Node i tworzenie listy” jest bezpłatna?
Tak — pełny tekst „Klasa Node i tworzenie listy” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Klasa Node i tworzenie listy”?
Zdefiniują Państwo dataclass Node, ręcznie zbudują listy przez łączenie węzłów oraz napiszą funkcje pomocnicze insert/delete/print wizualizujące zmiany wskaźników. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Klasa Node i tworzenie listy”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasa Node i tworzenie listy
- Odwracanie listy jednokierunkowej
- Wykrywanie cyklu algorytmem Floyda
- Scalanie, dzielenie i znajdowanie n-tego elementu od końca