C, Programowanie, Struktury danych

Struktury danych: lista jednokierunkowa

Witam Cię w pierwszej odsłonie cyklu wpisów dotyczących struktur danych.  Założeniem serii jest wprowadzenie adeptów programowania w wszelkie hasła dotyczące struktur danych właśnie. Lista jednokierunkowa jest pierwszą strukturą do omówienia na mojej (nomen omen) liście :D. Przy okazji każdej struktury zaczynać będę od teoretycznego wprowadzenia, a kończąc na implementacji w języku C.

 

Czym jest struktura danych?

W możliwie największym uproszczeniu jest to rodzaj pojemnika na dane. Model przechowywania informacji. Jeśli planujesz zostać programistą, a na twojej liście rzeczy do nauczenia nie ma jeszcze struktur – dopisz je jak najprędzej 😉.

Dokonujemy podziału na struktury statyczne i dynamiczne. Główna różnica polega na sposobie przydzielania pamięci. Statyczne musza mieć z góry ustalony rozmiar. Natomiast przydział pamięci przy strukturach dynamicznych jest wykonywany w czasie realizacji programu. W pierwszej fazie serii zajmować będziemy się strukturami liniowymi, a pierwszą z nich będzie właśnie lista.

Struktura listy jednokierunkowej – koncepcja

Niejeden wczasowicz przed wyjazdem na urlop do Mielna tworzy spis niezbędnych mu nad morzem artefaktów – listę właśnie. Analogia nie jest przypadkowa. Po prostu powszechnie używane listy zakupów, rzeczy do zrobienia itd. to dobre przykłady do koncepcyjnego zrozumienia idei listy.

Podejrzewam, że każdy spośród moich czytelników zna pojęcie typu tablicowego. Jest to w równym stopniu struktura danych co lista, a skoro każdy potrafi posługiwać się tablicami to spróbujmy listę rzeczy do wzięcia na wakacje zapisać w tablicy.

Co nas ogranicza na samym początku? Ilość elementów. Przy deklarowaniu tablicy należy jawnie podać liczbę jej elementów, a nie zawsze ona jest z góry znana. Skąd mamy wiedzieć, ile rzeczy okaże się przydatnych na wakacjach? Można, by było zadeklarować na starcie dobrych 1000 elementów, ale nie dość, że to horrendalna strata pamięci to na dodatek nie mamy wcale gwarancji, że ktoś nie będzie chciał przekroczyć tej granicy. Więc zadeklarujmy tablicę o 5 elementach – tylu, ile potrzebujemy, aż tu nagle przypomniało nam się o czapce z daszkiem. Jak dodać czapkę do tablicy, skoro nie ma tam dla niej miejsca? A no właśnie! Nie da się tego zrobić w żaden znany mi efektywny sposób.

GIF lista jednokierunkowa

Kolejnym problemem jest kwestia usuwania elementów. Załóżmy, że jednak okazuje się, że w standardowym wyposażeniu pokoju w Mielnie znajdziemy czajnik. Super – nie musimy targać własnego i wykreślamy czajnik z naszej listy. No ale jeżeli element był w środku tablicy to przeszukując tablice po indeksach, bądź z wykorzystaniem wskaźników to próbując odwołać się do komórki pamięci z niegdysiejszym czajnikiem otrzymamy (w najlepszym przypadku) jakieś krzaki, a dodatkowo mamy nieużywaną pamięć.

GIF lista jednokierunkowa

 

Tablica okazuje się, więc wyjątkowo miernym rozwiązaniem. Skorzystamy z listy.

Lista jednokierunkowa – definicja i cechy

Lista jest strukturą danych, która wykorzystujemy, gdy mamy do czynienia z góry nieznaną ilością danych. Oczekuje się, że dane będą tego samego typu, ale wykorzystując unię można ograniczenie to pominąć. Każdy element listy – węzeł (ang. node) zawiera dwa pola. Jedno pole na daną i drugie zawierające wskaźnik na następny element, bez którego po prostu zgubilibyśmy następny element. Pierwszy element listy zwykło nazywać się głową (ang. head), a ostatni ogonem (ang. tail). Bystrzejszy czytelnik spyta: „na co wskazywać ma ogon listy, skoro nie ma po nim kolejnego elementu?”. Otóż wskaźnik ostatniego elementu wskazywać powinien na NULL.

 

Czym się charakteryzuje lista jednokierunkowa? W liście jednokierunkowej poruszamy się po elementach w (jak nazwa wskazuje) jednym kierunku. Od początku listy do jej końca. Co oznacza (i to jest dość istotna wada tego rozwiązania), że aby dostać się do przedostatniego elementu listy będziemy musieli przejść po kolei przez wszystkie węzły.

Lista jednokierunkowa – prosta implementacja w C

Obecnie w większości języków korzysta się z gotowych rozwiązań, dostarczających działające i udokumentowane struktury danych. Sam jestem zdania, że nie warto wymyślać koła od nowa i lepiej korzystać z gotowych i sprawdzonych bibliotek. Celem serii jest jednak pełne zrozumienie każdej struktury, aby móc w późniejszym czasie świadomie korzystać z ich dobrodziejstw. Nasza lista przechowywać będzie dane typu integer.

 

Zdefiniowanie struktury i stworzenie głowy

Każdy element listy przedstawiony będzie za pomocą typu strukturowego z dwoma polami. Pierwszym przechowującym daną i drugim wskazującym na kolejny element listy.

Stwórzmy na samym początku głowę listy, aby zilustrować jak działa alokowanie pamięci i jak dostać się do poszczególnych pól struktury.

Lista jest dynamiczną strukturą danych, więc konieczne jest użycie wskaźników do skutecznego alokowania pamięci. W C w tym celu korzysta się z funkcji malloc(), której parametrem powinien być rozmiar jaki w pamięci komputera zajmuje jeden węzeł, a więc korzystamy z funkcji sizeof(), która zwróci rozmiar typu struktury podanej w argumencie.

Na samym początku lista powinna być pusta, więc head ustawimy na NULL. Równie dobrze moglibyśmy przypisać jakąś daną do głowy (np. 1). Chcąc dobrać się do pola w strukturze poprzez wskaźnik skorzystam z operatora strzałki „->” w sposób jaki widzimy poniżej.

 

Dodawanie elementu na początku listy

Jak będziemy realizować to zagadnienie? Zaalokujemy pamięć dla nowego elementu, przypiszemy mu wartość, a jego pole next ustawimy na head. W końcu nowy węzeł będzie na liście przed głową. Argumentami funkcji będzie głowa oraz liczba, którą do listy będziemy chcieli dopisać.

GIF lista jednokierunkowa
 

Ponieważ nowy element staje się automatycznie nową głową listy to musimy działać na oryginale heada. W tym celu skorzystam z podwójnego wskaźnika w argumencie.

Dodawanie elementy na końcu listy

Tutaj rozważymy dwa przypadki.

  1. Gdy head jest NULLem. Wtedy dodawany element będzie właściwie jedynym na naszej liście, a więc to head’a będziemy edytować.
  2. W przeciwnym razie tak jak poprzednio zaalokujemy pamięć, a następnie przejdziemy po całej liście, aby dostać się na jej koniec i tam dodać nasz element.

Tak jak wspominałem w liście jednokierunkowej musimy za każdym razem przechodzić od jej początku do końca. Problem ten rozwiewa lista dwukierunkowa, ale o niej opowiem wkrótce.

GIF lista jednokierunkowa
 

Dostęp do elementów listy – na przykładzie wyświetlania zawartości i zliczania elementów

Wykorzystamy trik z poprzedniej funkcji. Funkcja będzie przechodzić po kolejnych elementach listy dopóki dany węzeł nie będzie wskazywać na NULL, czyli nie będzie to ostatni element – ogon.

 

 

Dodawanie elementu za pomocą indeksu

W tym momencie zaimplementowanie wymaganej funkcji może stanowić mały problem. Do rozpatrzenia mamy trzy przypadki:

  1. Gdy indeks wynosi 0 – wtedy skorzystamy z wcześniej zdefiniowanej przez nas funkcji push_front(),
  2. Gdy indeks równy jest liczbie elementów na liście – to tak jakbyśmy po prostu dodawali element na koniec listy. Użyjmy zatem push_back(),
  3. Gdy indeks znajduje się w środku listy. Wtedy, aby nie pogubić wskaźników skorzystać należy z dodatkowego elementu tymczasowego.
 

Usuwanie pierwszego elementu

Chcąc usunąć pierwszy element dokonujemy podmiany głowy. Element o indeksie zerowym – nasz head – zostanie usunięty, zwolnimy pamięć, którą zajmował, a element o dotychczasowym indeksie 1 zostanie nową głową listy.

 

Usuwanie ostatniego elementu

Jeżeli lista jest jednoelementowa – mamy tylko głowę – to po prostu zwalniamy pamięć, którą zajmował head i lista jest pusta. W przeciwnym razie zwalniamy pamięć, którą zajmował ostatni element, a przedostatni od tego momentu powinien wskazywać na NULL. Staje się nowym ogonem.

 

Usuwanie elementu o wybranym indeksie

W sytuacji, gdy będziemy chcieli usunąć element o indeksie skorzystam z funkcji pop_front(). W pozostałych przypadkach postępować będziemy według poniższej listy kroków:

  1. Poruszaj się po liście, aż do elementu poprzedzającego węzeł, który chcesz usunąć,
  2. Przechowaj element, który chcesz usunąć za pomocą tymczasowego elementu,
  3. Ustaw nastepnik elementu poprzedzającego węzeł, który chcesz usunąć, następnikiem tego elementu (z wykorzystaniem tymczasowego elementu),
  4. Zwolnij pamięć używająć tymczasowego elementu.
 

Podsumowanie

Z pewnością wkrótce na blogu pojawią się kolejne wpisy nawiązujące do tematyki struktur danych. Na liście jednokierunkowej się nie skończy, oj nie 😉 Temat dość łatwy do pojęcia, a w zawodzie nieoceniony.

 

 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *