P-Programowanie

Lista jednokierunkowa C++

3 stycznia 2013, kategoria: C++

Lista jednokierunkowa jest strukturą o dynamicznie zmieniającej się wielkości. Listę można opisać jako uszeregowany zbiór elementów. Każdy element zawiera jakieś dane oraz wskazuje na swojego następcę. Cechą listy jednokierunkowej jest to, że można przeglądać ją tylko w jedną stronę, od początku do końca.

Jak napisać listę jednokierunkową?

Lista jednokierunkowa w odróżnieniu od tablicy jest rozrzucona po pamięci aplikacji. Jej elementy nie występują kolejno po sobie. Element poprzedni wskazuje na element następny. Dlatego tak ważne jest przypisywanie odpowiednich wskaźników do nowych elementów.

Nie ma jednego rozwiązania dotyczącego zaimplementowania listy. Każda lista może być zbudowana w inny sposób, zależy to od programisty oraz programu.

Ja tworząc listę posługuję się taką metodą:

  • tworzę strukturę odpowiadającą jednemu elementowi listy – element zawiera różne informacje np: imię, nazwisko, wiek oraz wskaźnik do następnego elementu.
  • tworzę strukturę główną – jest to struktura bazowa dla wszystkich elementów listy. Zawiera on adres początku listy czyli pierwszego elementu. Oprócz tego może zawierać różne metody typu np. dodawanie, sortowanie i usuwanie elementów.

Tak wygląda zobrazowanie mojej koncepcji:

lista jednokierunkowa C++

Wszystkie ważne metody związane z listą umieszczam w strukturze głównej, zaznaczonej kolorem żółtym na rysunku. Inny popularny sposób tworzenia list jednokierunkowych w C++ mówi, aby funkcje związane z listą umieszczać całkiem poza strukturami związanymi z listą. Wtedy najważniejszym argumentem każdej funkcji operującej na liście jest wskaźnik do jej pierwszego elementu.

Nie będę zajmował się drugą metodą, uważam że nie jest tak wygodna jak metoda zaprezentowana na obrazku wyżej. W mojej osobistej opinii: trzymając się zasad programowania obiektowego powinniśmy wszystkie metody odpowiedzialne za listę zgrupować w jednej strukturze/klasie a nie rozrzucać po całym programie.

Żadne rozwiązanie nie jest błędne ani nie jest złe. Obydwa rozwiązania przedstawiają listy jednokierunkowe, różnią się tylko implementacją oraz w następstwie sposobem inicjacji i budowy listy, co jest logiczne. Gdy nabierzesz wprawy nie będziesz się nawet nad nimi zastanawiał, przyjmiesz własną koncepcję i będziesz się jej trzymał.

Jeżeli w programie będziesz używał kilku list, wtedy wygodnie trzymać się powyższej metody. Jeżeli natomiast Twój program będzie korzystał z dziesiątek, setek list, wtedy warto operacje dotyczące list zaimplementować osobno, przekazując im jako argument wskaźnik na tę listę, na jakiej chcemy operować. Oszczędzi to miejsce w kodzie.

Deklaracja struktury elementów oraz listy

Stworzę listę służącą jako baza danych, będzie ona przechowywać imiona, nazwiska oraz wiek osób. Będę posługiwał się moją metodą przedstawioną na pierwszym rysunku w artykule. Pierwszym krokiem będzie utworzenie struktury elementu listy na dane i wskaźnik do kolejnego elementu. Druga struktura będzie odpowiedzialna za początek listy oraz metody.

Dodawanie elementów do listy

Posiadamy potrzebne struktury. Do struktury lista, dodałem metodę dodaj_osobe, dzięki niej będziemy mogli dodawać osoby do naszej bazy.

Co się dzieje gdy dodamy nową osobę (nowy element listy)? Ostatniemu elementowi listy przypisujemy wskaźnik na nasz nowo utworzony element i wypełniamy go danymi. Szczególną sytuacją jest moment kiedy dodajemy pierwszy element, wtedy nie można poprzednikowi ustawić wskaźnika, ponieważ poprzednika jeszcze nie ma. Przeanalizuj dokładnie poniższy kod ponieważ jego zrozumienie jest kluczowe:

Używanie listy jednokierunkowej czy nawet listy dwukierunkowej to tak naprawdę dobre zrozumienie wskaźników. Nie mamy iteratora aby odwoływać się do poszczególnych elementach tak jak w tablicy, do każdej operacji musimy znaleźć wskaźnik. Kiedy chciałem dodać nową osobę do bazy danych, musiałem za pomocą pętli while znaleźć wskaźnik do ostatniego elementu listy i dopiero wtedy dodać nowy element.

Aby przyśpieszyć niektóre operacje na liście, można zapisywać wskaźnik do jej ostatniego elementu w głównej strukturze odpowiedzialnej za hierarchie listy (teraz zapisujemy tylko początek).

Wyświetlanie elementów listy

Aby wyświetlić dowolny element  listy musimy znaleźć wskaźnik.  Wędrówkę zaczynamy zawsze od początku listy.

Po uruchomieniu kodu strumień wyjścia wygląda następująco:

lista5

Powyższy kod to tylko demonstracja, w jaki sposób poruszając się wskaźnikami po elementach listy wydobywamy informacje. Nie powinno się wyświetlać elementów listy w ten sposób, powinna być od tego osobna metoda a wskaźniki najlepiej przewijać w pętli while tak jak jest to pokazane w załączonej metodzie wyżej.

Napiszmy proste ciało metody wyswietl_liste(). Sprawa jest trywialna, po wywołaniu metody, wyświetlamy w pętli wszystkie elementy listy przewijając wskaźnik w pętli:

Usuwanie elementów listy

Usuwając elementy listy jednokierunkowej należy pamiętać o porządku we wskaźnikach:

  • jeżeli usuwasz pierwszy element (głowa/head) – wystarczy ustawić nowy początek listy z elementu n na n+1
  • jeżeli usuwasz środkowy element – usuwając n-ty element trzeba uzyskać sytuację aby element n-1 wskazywał na element n+1. Element n-ty można także usunąć z pamięci free lub delete
  • jeżeli usuwasz ostatni element (ogon/tail) – przyjmując że n-ty element znajduje się na końcu listy, usuwając go wystarczy wyzerować wskaźnik elementu n-1.

Zależnie od rodzaju aplikacji programista decyduje co jest kryterium w usuwaniu elementów listy, może być to unikalny id lub inny atrybut np. imie. Przykładowy kod odpowiedzialny za usuwanie elementu listy jednokierunkowej może wyglądać następująco:

Kryterium według którego usuwamy elementy jest ich numer na liście (numerując od 1..n a nie od 0 tak jak tablice).

Co sądzisz o tej metodzie? Wydaje się lekko skomplikowana, szczególnie przewijanie wskaźników dla elementów środkowych. Można to uprościć. Swego czasu pisząc rozbudowany projekt z listą jednokierunkową stworzyłem specjalną metodę, która zwracała mi wskaźnik na element n-1. Kod znacząco się skrócił piszcząc poszczególne funkcjonalności listy, ponieważ nie musiałem przewijać wszystkich elementów w poszukiwaniu wskaźnika n-1 – dostawałem go od razu po wywołaniu metody.

Podsumowanie

Lista jednokierunkowa z prawdziwego zdarzenia powinna posiadać jeszcze inne metody np.  dodawanie elementów na początek/koniec, sortowanie, wyszukiwanie.. Reszta funkcji zależy od aplikacji jaką piszemy. W internecie jest wiele gotowych list z dołączonymi metodami. Ten artykuł miał pokazać na jakiej zasadzie tworzyć i budować listę dlatego przedstawiłem tylko podstawowe metody.

Uwaga! W artykule podczas usuwania elementów listy, po prostu pozbywałem się wskaźników natomiast nie usuwałem obiektów w pamięci na które wskazywały wskaźniki. Może to powodować błędy memory-leak w rozbudowanych aplikacjach. Pisząc projekt na zaliczenie, przypuszczam że nie ma to żadnego znaczenia. Nie usuwałem wskaźników z pamięci, ponieważ kod został by znacznie zaśmiecony.

Jeżeli chcesz skompilować plik dołączony przeze mnie na samym dole strony, rozważ na jakim środowisku go uruchamiasz. Na poszczególnych kompilatorach różnią się nieco biblioteki dyrektywy #include.

Microsoft Visual Studio:

Pozostałe (np. Code::Blocks):

Kompletny kod można pobrać pod adresem: http://www.p-programowanie.pl/pliki/lista_jednokierunkowa.cpp

Komentarze:

Użytkownik xxx napisał/a:

07 stycznia 2013


Moim zdaniem, jest tutaj drobny błąd.
Zamiast: while (pierwsza->nastepna) powinno być while (temp->nastepna).
A ogólnie całkiem fajnie napisane ;)

Użytkownik Karol napisał/a:

07 stycznia 2013


Oczywiście, że tak – poprawione. Dzięki za informacje o błędzie :)

Użytkownik aser napisał/a:

23 czerwca 2013


osoba *pierwsza = 0; <- tu mam blad ;]

Użytkownik Karol napisał/a:

24 czerwca 2013


Napisz więc NULL zamiast 0, zależy od kompilatora.

Użytkownik Mike napisał/a:

09 sierpnia 2013


Wyrzuca ci blad aser, bo w struct nie mozesz przypisac wartosci. Trzeba to zrobic konstruktorem.
struct lista {
osoba *pierwsza; // wskaźnik na początek listy
(…)
};
Powinien byc jeszcze wewnatrz konstruktor:
lista(){osoba* pierwsza=NULL;}
Pozdrawiam : )

Użytkownik Karol napisał/a:

10 sierpnia 2013


Prawda to. Uzupełnię kod o konstruktor dla drugiej struktury. Co ciekawe błąd wkradł się przez to, że został normalnie przepuszczony przez GCC, bez jakiegokolwiek błędu czy ostrzeżenia.

MVC 2010 już nie pozwala na kompilację.

Użytkownik Syriusz napisał/a:

19 września 2013


Świetny artykuł, dzięki Karol.

Użytkownik Jaaa napisał/a:

03 listopada 2013


Siema, pomógłbyś mi z usuwaniem?

Użytkownik Karol napisał/a:

06 grudnia 2013


Artykuł został rozbudowany także o usuwanie elementów.

Użytkownik student napisał/a:

05 stycznia 2014


Nieusuwanie elementów z pamięci ma bardzo duże znaczenie podczas oddawania pracy na zaliczenie i jest to dosyć poważny błąd.

Użytkownik Karol napisał/a:

09 stycznia 2014


@student
To zależy od wykładowcy, u nas nie miało to znaczenia. Tak, pamięć trzeba zwalniać i jest to napisane w artykule.

Użytkownik Milosz napisał/a:

24 stycznia 2014


A jak bedzie z zapisem/odczytem z pliku? Z odczytem sobie poradziłem ale zapisz z pliku do bazy stwarza mi problemy, będę wdzięczny za wskazówkę

Użytkownik Karol napisał/a:

24 stycznia 2014


„Zapis z pliku do bazy” to raczej po prostu „odczyt z pliku”? Odwróciłeś pojęcia :D

Nie ma uniwersalnej koncepcji. Musisz podzielić plik na linie, a linie według określonego sepatora. Możesz także zapisywać informacje w formacie binarnym.

Użytkownik damian napisał/a:

28 lutego 2014


cześć. dzięki za artykuł. pytanie – w metodzie usun_osobe() nie musimy dawać ustawienia „nowa->nastepna = 0;” ponieważ jest to powtórzenie deklaracji zawartej w konstruktorze struktury osoba?

Użytkownik Karol napisał/a:

28 lutego 2014


Tak, zgadza się – ale tylko w metodzie Dodaj_osobę(). Konstruktor lepiej zostawić, linijkę o której napisałeś można usunąć.

Użytkownik wojtek napisał/a:

18 marca 2014


Mam pytanie, tworząc listę, zapisuje dane w określonej kolejności, czyli teoretycznie ostatni element jest pierwszym przy odczytywaniu ? Bo w moim przypadku wyświetlam tak jak wpisałem. Czy coś robie źle, lub źle zrozumiałem ?

Użytkownik Karol napisał/a:

20 marca 2014


„Ostatni element jest pierwszy przy odczytywaniu” ale w „stosie”! Stos można sobie wyobrazić jako stertę talerzy położonych jeden na drugi. Aby wyciągnąć jakikolwiek talerz trzeba zdejmować po jednym talerzu od góry, a więc od „najnowszego” elementu.

Lista to po prostu lista. Dodajesz elementy i są one dopisywane do końca listy. Podczas odczytywania listy korzystasz z wskaźnika na początek listy, jest on kluczowy. Co za tym idzie przeglądasz listę od początku do końca (od elementu najstarszego do ostatnio dodanego).

Oczywiście można zaimplementować listę, aby dodawać nowe pozycje na jej początek, lub aby wyświetlać ją od końca, kombinacji jest dużo.

Lista opisana w tym artykule jest wyświetlana od początku do końca. Nowe elementy „dodawane” są na jej koniec (a wiec nie do końca dobrze zrozumiałeś artykuł).

PS. Nie wiem co oznacza u Ciebie „ostatni element”. Dodany na końcu listy? Czy dodany najdawniej a więc na początku? Do artykułu dołączony jest kod źródłowy. Pobierz > skompiluj > przeanalizuj.

Użytkownik wojtek napisał/a:

21 marca 2014


A jak zmodyfikować kod żeby dodawać za element ? Żeby działanie listy przypominało stos ?

Użytkownik Jarek napisał/a:

04 czerwca 2014


czy jest możliwość zmiany wartości np. pola wiek?, dla istniejącego już elementu w liście. Jak uzyskać dostęp do tego pola.

Użytkownik Karol napisał/a:

04 czerwca 2014


Musisz napisać metodę, modyfikującą dany element listy według jakiegoś kryterium. Jeżeli chcesz zmienić wiek osoby o imieniu „Karol” to metoda musi przewijać wskaźniki aż do znalezienia elementu o takiej wartości. Można też do każdego elementu dodać jego unikatowy ID i edytować pola listy według ID.

To wszystko zależy od tego, jaki program piszesz.

Użytkownik Mateusz napisał/a:

16 listopada 2014


Jak powinno wyglądać usuwanie obiektów z pamięci w tym kodzie? Mam trochę z tym problem…

Użytkownik Kamyk napisał/a:

08 lutego 2015


Bardzo pomógł mi ten blog w uczeniu się list, jednak jest jedno ale…Jeżeli spróbuje się usunąć z listy element, którego tam nie ma (np. element 7 z 3 elementowej listy itp.), to jest naruszenie ochrony pamięci. Można się przed tym zabezpieczyć np. dodatkową funkcją
list::void ile(); która poda ile mamy elementów na liście i jeśli jest ich zero lub jeśli próbuje się usunąć nieistniejący element zapobiegnie błędom
Nie jestem ekspertem z programowania i nie próbuję się wymądrzać, to tylko taka obserwacja, jeśli nie mam racji poprawcie mnie. Pozdrawiam

Użytkownik Łukasz napisał/a:

31 sierpnia 2015


Czesc
chciałbym się upewnić czy dobrze rozumiem ten fragment kodu:
osoba *temp = pierwsza;

while (temp->nastepna)
{
// znajdujemy wskaźnik na ostatni element
temp = temp->nastepna;
}

temp->nastepna = nowa;
Rozumiem że, wskażnik ”temp” jest ustawiony tymczasowo na ”pierwszy” element i jest przewijany w petli, az znajdzie ostatni element i w rezultacie wskaznik ”nastepna” wskazuje na nowy element listy? tak

@Karol
Tak, dobrze rozumiesz.

Użytkownik kosiarzyk napisał/a:

21 listopada 2015


Cześć, mam problem z podobnym programem, jak działa lista w przypadku gdy jedna osoba ma np. kilka ocen z danego przedmiotu, chciałbym użyć tylko list ale chyba będzie to wymagało implementacji dodatkowej tablicy.

Użytkownik Kasia napisał/a:

22 stycznia 2016


Nikt jeszcze nigdy nie wytłumaczył mi tak dobrze list jednokierunkowych.
Miałam ćwiczenia na studiach, prowadzone przez 45 minut, w taki sposób, ze nie zrozumiałam wtedy jak mam przewijać listę, oraz jak wędrować po jej kolejnych elementach.

Długo nie potrafiłam znaleźć materiałów w internecie.
Obejrzałam wszystkie tutoriale Miroslawa Zelenta, thenewboston i wiele innych. Jednak tu znalazłam tłumaczenie krok po kroku dla początkujących.

Dziękuje ponownie.

Użytkownik Mariusz napisał/a:

06 marca 2016


Zelent rzeczywiście temat struktur danych nakręcił na odczepnego
chociaż z drugiej strony nie wprowadził wcześniej rekordów (struct)
ani w temacie o wskaźnikach nie wspomniał o referencji więc wprowadzanie list łączonych w tym momencie byłoby wbrew metodyce nauczania

Lista ma mało funkcji wstawianie elementu przed bądź za wybranym elementem, wyszukiwanie elementu o zadanym kluczu
Co do usuwania to lepiej nie numerować węzłów tylko usuwać węzły zawierające dany klucz lub usuwać ten węzeł na którego wskazuje wskaźnik
Przydałoby się jakieś sortowanie np przez scalanie lub szybkie (które może nie być takie szybkie)

Kasia hablas espanol ?
Tu puedes ver un codigo de lista enlazada en Pascal y C sobre youtube

Użytkownik Alex napisał/a:

13 kwietnia 2016


Jak sprawdzić czy lista jest pusta ?

Użytkownik Luk napisał/a:

07 września 2016


może mi to ktoś objaśnić?
załóżmy, że mamy strukturę:

struct lista{
string nazwa;
lista *nast;
}

czy zapisy 1 i 2 są równoważne?

1) lista *nowy = new lista;

2) lista*nowy;
nowy = (Lista*) new lista;

Użytkownik Michał napisał/a:

21 listopada 2016


Up – nie. W pierwszym przypadku uruchomi się konstruktor domyślny. Tworzysz zmienną wskaźnikową typu lista i inicjalizujesz ją adresem nowej struktury. W drugim przypadku tworzysz zmienną ale nie inicjalizujesz jej tylko w kolejnej linijce uruchamia się przeładowany operator przypisania =.

Użytkownik Jełek napisał/a:

09 kwietnia 2017


Super artykuł! Teraz wszystko rozumiem ;)

Zachęcam Cię do zostawienia komentarza!

Ilość znaków: 0

Zachęcam Cię do polubienia bloga na facebooku! Dając lajka wspierasz moją pracę - wszystkie artykuły na blogu są za darmo!