Listy (ang. lists) to struktury danych, które umożliwiają przechowywanie danych w liniowym porządku, ale w odróżnieniu od tablic nie ma to odzwierciedlenia w fizycznym ułożeniu w pamięci. Każdy z elementów listy – węzeł (ang. node) posiada powiązanie z innym węzłem.
Typy list
Wyróżniamy dwa podstawowe typy list:
- listy jednokierunkowe – każdy węzeł posiada wskaźnik na kolejny lub poprzedni węzeł,
- listy dwukierunkowe – każdy węzeł posiada wskaźnik na kolejny oraz poprzedni węzeł.
Tutaj może pojawiać się pytanie, jaki adres ma przechowywać wskaźnik next w ostatnim węźle. Może on przechowywać adres pierwszego węzła – mamy wtedy do czynienia z listą cykliczną, ale może także przyjmować wartość NULL. To już zależy od sposobu implementacji. Podobnie jest z wskaźnikiem prev w pierwszym elemencie: albo przyjmuje wartość NULL, albo adres ostatniego węzła.
Zalety
Organizacja danych w listy ma szereg zalet, które są ze sobą powiązane:
- pozwala na dynamiczne tworzenie i usuwanie elementów z listy – wiąże się to jedynie z ustawieniem wartości kilku wskaźników. Dla przykładu, zmiana wielkości tablicy także jest możliwa (korzystając z dynamicznej alokacji pamięci), ale zajmuje to o wiele więcej czasu,
- przy inicjalizacji nie musimy z góry znać ilości elementów,
- nie potrzebujemy ciągłego bloku pamięci – każdy element może być w dowolnym miejscu pamięci, co jest szczególnie przydatne przy dużej ilości przechowywanych danych,
- elementy mogą być dodawane i usuwane z dowolnego miejsca listy.
Jak widać, listy są bardzo elastyczne i stosowanie ich daje duże możliwości, dlatego są one bardzo często wykorzystywane do różnych celów, m.in. implementacji stosów, kolejek. Bufory cykliczne, które opisywałem w artykule Bufor kołowy #1: zasada działania, także są często implementowane w oparciu o listy.
Wady
Równowaga musi być zachowana, nie ma rzeczy idealnych. „Wszystko ma swoje wady, zalety”. Tak jest i tutaj. W większości sytuacji dużo lepiej jest wykorzystać zwykłe tablice, ze względu na to, że:
- w tablicach mamy bezpośredni dostęp do poszczególnych elementów, czego efektem jest szybsze działanie. W przypadku list dostęp do określonego węzła wiąże się z koniecznością przejścia określonej ścieżki węzeł po węźle – szczególnie odczuwalne jest to w przypadku listy jednokierunkowej,
- tablice są gotową strukturą danych, w której mamy prostą nawigację,
- listy zajmują więcej miejsca w pamięci – oprócz danych, konieczne jest przechowywanie wartości zmiennych pomocniczych.
O implementacji
W językach wysokopoziomowych listy są dostępne w standardzie dla programisty, w języku C zaimplementować musimy je sami. Ma to swoją drogą jakiś plus, bo skoro już musimy ją napisać, to możemy ją napisać całkowicie pod siebie, dostosowaną do naszych potrzeb. Skorzystamy z tego i stworzymy listę wyłącznie na potrzebę menu. Zatem nie będzie to czysta implementacja listy jedno lub dwukierunkowej z wszystkimi możliwymi do przeprowadzenia na nich operacjami. Pominięte będą tutaj takie funkcjonalności jak przeszukiwanie listy, zamiana miejscami elementów listy, dynamiczne dodawanie i usuwanie elementów czy jakieś sortowanie, ponieważ nie jest to w tym przypadku potrzebne.
Przed przystąpieniem do implementacji zaznaczę, że zdecydowałem się na zastosowanie listy dwukierunkowej, ponieważ uważam, że dzięki temu kod będzie bardziej czytelny i łatwiejszy do zrozumienia. Wiąże się to jednak z trochę większym zużyciem pamięci, niż w przypadku listy jednokierunkowej, ponieważ zamiast jednego wskaźnika musimy mieć dwa. Dlatego jeżeli korzystasz z mikrokontrolera o niewielkiej ilości pamięci, albo po prostu będzie Ci jej brakowało w danym projekcie warto rozważyć opcję zmiany listy na jednokierunkową. Konieczne będzie wprowadzenie modyfikacji w kodzie, ale nie powinny one stwarzać wielkich problemów.
To tyle w temacie list. Jest to w wielu wypadkach bardzo przydatna struktura danych, dlatego zachęcam do dokładniejszego zgłębienia tego tematu. Poniżej link do następnego artykułu, w którym zajmiemy się już implementacją 🙂