Podręcznik

2. Listy jednokierunkowe

2.2. Przykładowe operacje na listach jednokierunkowych

Dopisywanie elementu na koniec listy

Korzystając z zasad pokazanych w poprzednim rozdziale napiszemy funkcję, która do listy o strukturze Tos dopisuje na jej końcu dodatkowy element.

void dopiszNaKoncu (Tos *&glowa, string ktos) {
//  funkcja dopisuje osobę o imieniu ktos na końcu listy
//  zaczynającej się pod adresem glowa
//  glowa może się zmienić w trakcie działania funkcji, dlatego jest przy niej &
Tos *nowy, *akt;   // wskażniki pomocnicze
//  tworzymy nowy, dodatkowy rekord,
//  wpisujemy do niego imie ktos i adres NULL,
//  bo to ma być rekord końcowy:
    nowy=new Tos;
    nowy->imie=ktos;
    nowy->nast=NULL;
//  jeśli lista była pusta, to  teraz będzie składała się
//  tylko z tego nowego rekordu:
  if (glowa==NULL)
    glowa=nowy;
  else {  // a jeśli nie była pusta, to:
    akt=glowa;   // wracamy na początek listy
    while (akt->nast!=NULL) // wolno napisać taki warunek, bo lista nie jest pusta
        akt = akt->nast;   // dojeżdżamy do elementu, który w polu nast ma NULL
    // teraz akt jest adresem ostatniego elementu listy
    // możemy do niego dołączyć nowy, końcowy element:
    akt->nast=nowy;
   }
}

Za pomocą tej funkcji łatwo można utworzyć całą listę od początku w kolejności zgodnej z wczytywaniem danych - pobierając w pętli kolejne imiona i wywołując dopiszNaKoncu. Zwróćcie tylko uwagę, że za każdym razem, gdy chcemy dopisać coś na końcu listy, musimy przebiec całą listę od początku. Gdybyście uznali, że to bardzo nieoptymalne działanie, można do funkcji dodać dodatkowy parametr, tak by zwracała ona adres ostatniego elementu, aby nie trzeba było tego "ogona" poszukiwać za każdym razem od początku. Oba sposoby tworzenia listy tą metodą pozostawiamy Wam jako ćwiczenie.

Wstawianie i usuwanie elementów

Przyszła teraz pora na pokazanie, jak do istniejącej listy wstawiamy dodatkowe elementy i jak je z niej usuwamy. W zasadzie czynność wstawienia elementu sprowadza się do dwu kroków: po pierwsze musimy wstawiany element utworzyć w pamięci (za pomocą operatora new), a następnie zmodyfikować istniejące powiązania w liście. Podobnie z usuwaniem elementów. Tym razem musimy jedynie odwrócić kolejność działań, czyli najpierw zmienić powiązania, a potem element usunąć przy pomocy operatora delete. Poniżej znajduje się prosta symulacja umożliwiająca wstawianie 4 elementu do listy oraz usuwanie wskazanego elementu z listy.

Symulacja listy jednokierunkowej: Wstawianie oraz Usuwanie

Wstawianie

Element* current = head;
int i = 1;
while (i < 4 - 1) {
    current = current->next;
    i++;
}
Element* newElement = new Element;
newElement->next = current->next;
current->next = newElement;

Usuwanie

Element* current = head;
int i = 1;
while (i < pos - 1) {
    current = current->next;
    i++;
}
Element* temp = current->next;
current->next = temp->next;
delete temp;

Przedstawiona symulacja umożliwia jedynie usuwanie elementów znajdujących się wewnątrz listy. Nie można usuwać elementów znajdujących się na początku listy. W przypadku usuwania pierwszego elementu listy odbywa się ono w inny sposób niż usuwanie elementu znajdującego się wewnątrz listy lub na końcu. Poniżej przedstawiono kod umożliwiający usunięcie pierwszego elementu z listy:

void dopiszNaKoncu (Tos *&glowa, string ktos) {
Tos* do_usunięcia = head;
head = head->next;
delete do_usuniecia;

W przedstawionym kodzie na początku tworzę pomocniczy wskaźnik na pierwszy element listy oraz następnie zmieniam adres pierwszego elementu na następny. Na końcu usuwam tymczasowy element - wskazujący na adres starej head listy. Analogicznie jest w przypadku dodawania listy na poczatek listy:

void dopiszNaKoncu (Tos *&glowa, string ktos) {
Tos* nowy_element = new Tos;
nowy_element->next; = head;
head = nowy_element;