[C] Listy dwukierunkowe, pomoc w wyjaśnieniu

Dla specjalistów Programowanie
#1

Witam,

staram się przyswoić jak działają listy dwukierunkowe, w teorii wszystko spoko, gorzej z praktyką.

W większości opracowań list dwukierunkowych w c pojawia się następujący algorytm:

 

void add(struct city *element)
2.
{
3.
if(first == NULL)
4.
{
5.
// wyzerowanie wskaźnika _previous_ naszego elementu
6.
element->previous = NULL;
7.
first = element; // ustawienie wskaźnika początku listy na nasz element
8.
}
9.
else
10.
{
11.
// ustawienie wskaźnika _next_ poprzedniego elementu na nasz nowy
12.
last->next = element;
13.
// ustawienie wskaźnika _previous_ naszego elementu na poprzedni
14.
element->previous = last;
15.
 
16.
}
17.
 
18.
last = element;
19.
element->next = NULL;
20.
}

 

źródło: binboy.org

Moje pytanie jest następujące: w jakim celu przypisujemy elementy previous i next (element->previous=last; last->next=element) skoro i tak na końcu przypisujemy wskaźnikowi last nasz element? 

 

Zdaję sobie sprawę, że ten post może przyprawić odpowiedzi hejtu, że to nie tu itp itd, jednak ciężko znaleźć jakieś dobre opracowanie.

Proszę o pomoc.

#2

Ogólnie na początku masz jakiegoś if’a co sprawdza czy lista nie jest pusta (wskaźnik first wskazujący na null), jeśli lista jest pusta to wstawiasz pierwszy element.

#3

Lista dwukierunkowa ma dwa wskaźniki (tutaj implementowane jako pola struktury). Wskaźniki pokazują na wcześniejszy element listy i następny element listy. Jeśli element jest pierwszy to wskażnik previous ustawiony jest na NULL, a odwrotnie jest gdy element jest ostatni.

W przykładzie kodu wstawiamy element na końcu listy. Końcowy wskaźnik (u Ciebie last) musi wskazywać na wstawiany element co jest realizowane na końcu przez przypisanie last = element. Jednak najpierw należy wskaźnik next ostatniego istniejącego wcześniej elementu listy przypisać do wstawianego elementu, aby zachować ciągłość łańcucha.  Zaś nowy element w polu previous musi pokazywać na ten wcześniejszy. Czyli dodajesz dwie strzałki z rysunku powyżej.  Stąd się biorą wspomniane przez Ciebie przypisania.

 

Gdybyś wstawiał element w środku musiałbyś przypisać aż cztery wskaźniki:

#4

@fufus, @mikolaj_s dziękuję serdecznie za wyjaśnienie. 

 

Mam jedną wątpliwość, że skoro przypiszę last=element, to element który był ostatni (last) po prostu przepadnie (jego składowe: last->next), bo zostanie przypisany do elementu element. 

 

@fufus, szykuję się do studiowania :smiley:

#5

W podanym kodzie tego nie widać, ale raczej struktura, do której przyłączasz nową była tworzona dynamicznie za pomocą malloc. Dopóki jej nie zwolnisz to będzie istniała w pamięci, zaś możesz ją znaleźć poprzez wskaźnik previous we wstawionym elemencie. Na tym polega właśnie lista, że nie możesz od razu dostać się do danego elementu, tylko musisz przejść po łańcuszku od struktury do struktury aby ją znaleźć.

#6

Tak jak pisze kolega wyżej, tracisz do niej tylko bezpośredni wskaźnik, ale możesz się “przewinąć” przy pomocy wskaźników previous/next do interesującego cię elementu. Głowa i ogon dają ci to że możesz pierwszy i ostatni element uzyskać przy złożoności O(1), każdy inny element w przypadku pesymistycznym uzyskasz w czasie O(n) gdzie n jest liczbą elementów.

#7

Dziękuję serdecznie Panowie, zrozumiałem :slight_smile: