Tworzenie Listy

Question

Cześć, Mógłby mi ktoś wytłumaczyć jak tworzyć liste jednokierunkową żeby można było dodawać elementy na początku, na końcu, usuwać itd. Szukałem w necie ale wszystko to jakieś nie jasne dla mnie?Może dlatego że większość tych list pisana jest obiektowo a ja znam dopiero podstawy?

Z góry dziękuje

Answer 1

Lista to struktura danych, gdzie każdy element ma wskaźnik do kolejnego elementu lub NULL jak kolejnego już nie ma (opiszę jak się robi z funkcjami globalnymi żeby było łatwiej zrozumieć). Mamy w mainie zadeklarowany wskaźnik do klasy/struktury np. lista i wysyłamy ten wskaźnik do funkcji add_end. Musimy sprawdzić czy jest to NULL czy nie. Pierwszy musi być zainicjalizowany jako NULL więc tworzymy pierwszy element (new/malloc) ustawiamy w nim wskaźnik na NULL i dodajemy jakąś wartość. Teraz twożymy kolejny więcy wysyłamy znów ten sam wskaźnik do tej funkcji i sprawdzamy czy jest NULL a nie jest bo pokazuje na pierwszy element listy. Więc musimy znaleźć element listy, który nie pokazuje na nic(NULL) czyli pętlą

 while(wsk->next != NULL) // dopóki istnieje kolejny element
{
    wsk = wsk->next;  //przechodzimy do kolejnego
}

teraz jesteśmy w ostatnim elemencie więc robimy to co dla pierwszego tylko nie jako wsk = ... tylko wsk->next = new... wsk->next->next=NULL  i to już jest dodawanie na koniec.

Dodając na początek sprawdzamy czy są już jakieś elementy listy czyli czy wsk != NULL jeśli nie to tworzymy zwykły pierwszy element jeśli nie to twożymy tymczasowy wskaźnik na element listy i ustawiamy go na pierwszy element teraz dla wskaźnika z maina tworzymy nowy obiekt i dla jego pola next ustawiamy ten wskaźnik tymczasowy.

Usuwanie to znajdujemy element przed tym elementem, który chcemy usunąć i tworzymy wskaźnik tymczasowy który przechowa element następny po tym do usunięcia. Usówamy wks->next;(usuwamy kolejny) i wsk->next = tmp;(zamiast na kolejny pokazuje na jeden dalszy bo tmp= wsk->next->next) i to by było na tyle.