Struktury Danych: Kształty Decydujące o Szybkości Twojego Programu”,

Kształt decyduje o operacji, a nie na odwrót

Struktura danych to umowa między sposobem ułożenia danych w pamięci a tym, jak te ułożenie sprawia, że określone operacje są tanie lub drogie. Nie ma struktury bezpłatnej – każdy projekt wymienia prędkość jednej operacji na prędkość innej, a wybór odpowiedniej struktury to w zasadzie wybór, które operacje najczęściej wykonuje program i umożliwienie mu ponoszenia najmniejszej możliwej ceny za te operacje, kosztem tych, których rzadko potrzebuje.

Stosy i kolejki: dwie dyscypliny na tej samej sekwencji

Stos dodaje lub usuwa elementy tylko z jednego końca — ostatni wchodzi, pierwszy wychodzi (LIFO). Jest to naturalna struktura dla wszystkiego zagnieżdżonego zakresu: stos wywołań, który śledzi, która funkcja zwraca się do której, historia cofania, dopasowywanie nawiasów i przeszukiwanie w głąb (depth-first traversal). Kolejka dodaje do jednego końca i usuwa z drugiego — pierwszy wchodzi, pierwszy wychodzi (FIFO) — co jest pożądane dla wszystkiego przetwarzanego w kolejności przybycia: planowanie zadań, kolejki druku i przeszukiwanie w szerokość (breadth-first search), gdzie granicę należy badać w kolejności odkrycia.

stack: push(x), pop()      → both O(1), always at the same end (top)
queue: enqueue(x), dequeue() → both O(1), at opposite ends (back, front)

Both are typically built on an array (with a moving head/tail index,
or a ring buffer) or a linked list — either backing store gives O(1)
push/pop as long as you never need to reach into the middle.

Tablice versus listy powiązane: ciągłe przechowywanie danych versus wskaźniki

Tablica przechowuje elementy w sposób ciągły, więc dowolny indeks można bezpośrednio uzyskać przez arytmetyczne obliczenia – O(1) losowy dostęp – jednak wstawianie lub usuwanie elementu w środku oznacza przesunięcie wszystkich kolejnych elementów, O(n). Lista powiązana przechowuje każdy element w oddzielnym węźle z wskaźnikiem do następnego elementu, więc wstawianie lub usuwanie jest O(1) pod warunkiem posiadania już odniesienia do właściwego miejsca, ale dostęp do dowolnego danego elementu oznacza przejście łańcucha od głowy, O(n), a każdy węzeł stanowi oddzielne przydzielenie pamięci, rozproszone w RAM zamiast ułożone razem. To rozproszenie ma większe znaczenie w praktyce niż sugeruje złożoność asymptotyczna – nowoczesne procesory pobierają bloki pamięci o rozmiarze linii buforowej, więc ciągłe ułożenie elementów tablicy oznacza, że wiele elementów jest pobieranych „za darmo” w jednym dostępie, podczas gdy podążanie za wskaźnikami listy powiązanej wywołuje świeży, wolny dostęp do pamięci niemal na każdym kroku – dlatego tablice zwyciężają w rzeczywistych benchmarkach nawet wtedy, gdy lista powiązana ma tę samą złożoność asymptotyczną.

Tablice Hashujące: Przekształcanie Wyszukiwania w Arytmetykę

Wyszukiwanie w niezsortowanej tablicy za wartość ma złożoność O(n) — musisz sprawdzić każdy element w najgorszym przypadku. Tablica Hashująca niemal całkowicie omija wyszukiwanie: funkcja hash przekształca klucz w liczbę, ta liczba jest redukowana modulo wielkości tabeli, aby wybrać koszyk, a wartość jest przechowywana (lub odczytywana) bezpośrednio w tym koszyku. Przy dobrej funkcji hash rozpraszającej klucze równomiernie, wstawianie, wyszukiwanie i usuwanie są wszystkie O(1) średnio. Kolizje — dwa różne klucze lądujące w tym samym koszyku — są obsługiwane albo przez łańcuchowanie (każdy koszyk przechowuje małą listę powiązaną), albo przez otwarte adresowanie (przeszukuj do następnej wolnej komórki); w każdym przypadku wydajność pogarsza się do O(n) tylko wtedy, gdy tabela staje się zbyt pełna, co jest spowodowane automatycznym skalowaniem i ponownym haszowaniem tabeli, gdy jej współczynnik obciążenia przekroczy próg, zazwyczaj około 0.7.

Wybór między nimi

Praktyczna zasada mówi, aby nazwać dominującą operację w programie i wybrać strukturę, która sprawia, że jest ona O(1) lub bardzo bliska temu: potrzebujesz zachowania kolejności w cofaniu — stos; potrzebujesz przetwarzania w kolejności przybycia — kolejka; potrzebujesz częstego wstawiania w środku z odniesieniem do miejsca — lista powiązana; potrzebujesz szybkiego wyszukiwania klucza bez wymaganej kolejności — tabela hashowa; potrzebujesz zarówno szybkiego wyszukiwania, jak i posortowanej kolejności — sięgnij po zbalansowane drzewo, tracąc O(1) wyszukiwanie na rzecz O(log n) w zamian za utrzymanie wszystkiego w uporządkowanym stanie.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Data Structures i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.