LISTY

CO trzeba umieć:

-- FUNKCJE 

-- WSKAŹNIKI 

//////////////////////////////////////////////////////////////////

Listy są to rozproszone struktury danych. Możemy je przyrównać do znanych już nam tablic, tylko są bardziej skomplikowane w użyciu i ważne jest to, że kompilator nie potrzebuje bloku spójnej przestrzeni. Wystarczą mu tylko kawałki, w które będzie mógł zmieścić pojedyncze elementy listy.

Ja omówię tylko działanie list jedno i dwukierunkowych, ale zaznaczam, że są jeszcze inne.

Struktura listy: (przykładowa)

struct list{ // struktura o nazwie „list” (może być dowolna nazwa)

   
   int key; // pole struktury o nazwie key i typie int, bo lista
            // będzie przechowywała liczby całkowite

    
   struct list *next; // jest to wskazanie na element następny

   struct list *prev; // jest to wskazanie na element poprzedni

};

Deklaracja pustej listy:

struct list *head=NULL;

head jest wskaźnikiem na pierwszy element, ale że lista jest jeszcze pusta więc head wskazuje na NULL, czyli na takie nic

Lista jednokierunkowa zawiera tylko wskazanie na następny element. Będę podawał kody dla list dwukierunkowych, aby mieć listę tylko jednokierunkową należy pominąć linijki z prev. Zasada działanie obu tych list jest taka sama.

Tej struktury będę używał przy algorytmach na listach.

Jedyną rzeczą, która może dziwić jest to wskazanie na następny/poprzedni element. Więc o co chodzi?

Jak już wspominałem lista jest strukturą rozproszoną, czyli jej elementy nie muszą leżeć obok siebie w pamięci, więc potrzebujemy czegoś co będzie „wiedziało” gdzie jest następny element naszej listy. Czyli pole next/prev wskazuje na adres elementu dlatego używamy gwiazdki(*), czyli wskaźnika.

Na razie wszystko fajnie, pięknie, ale jak się listą posługiwać?

No tu jest większy problem, bo... no właśnie bo co? Bo najpierw trzeba elementy do listy dodać.

1.DODWANAIE ELEMENTU

Ale żeby nie było tak prosto dodawać elementy możemy w różny sposób:

a) do ogona (czyli na koniec)

Dodawanie elementów do ogona (bo mówi się że lista ma głowę(head) i ogon(tail)) to dodawanie na koniec listy.

Na razie nasza lista jest pusta, więc pierwszy element jaki będziemy chcieli dodać, stanie się naszą głową:

 

kolejny element będzie dodany na koniec, czyli za ostatni element, ale należy pamiętać lista prawidłowo wskazywała relacje między elementami:

Z każdym następnym elementem będzie tak samo. Będziemy musieli przejść na koniec i ustawić relacje między elementami. 
 

KOD:

(Wersja ze zwracaniem głowy)

struct list* add_tail(struct list *head, int klucz){

struct list *nowy_element=(struct list*)malloc(sizeof(struct list));

// tworzymy nowy element typu naszej listy

struct list *w=head;

// nasze zmienne pomocnicze

nowy_element->next=NULL; // na razie ustawiamy wskaźniki na NULL

nowy_element->prev=NULL; // dodatkowo dla listy dwukierunkowej

nowy_element->key=klucz; // przypisanie naszego klucza

if(head==NULL){ // jeśli nie ma głowy nasz element staje się głową

      head=nowy_element; // zmieniamy głowę

}else{ // gdy mamy jakieś elementy już w liście

      while(w->next!=NULL){ // pętlą szukamy końca listy

      w=w->next;

      }

      // po wykonaniu się pętli w wskazuje na ostatni element

      // ustawiamy relacje

      w->next = nowy_element;

      nowy_element->prev = w; // dodatkowo dla listy dwukierunkowej

}

 
return head; // zwracamy nową lub starą głowę

}

Mogą zastanawiać Cię te dziwne strzałeczki, bo przecież czytałeś uważnie, więc możesz się oburzać, bo mówiłem, że do pól struktury odwołujemy się przez kropkę(.) a ja tu używam jakiś strzałek. Ale zanim zaczniesz krzyczeć na mnie, dokończ czytanie. To co mówiłem nadal podtrzymuję, ale trzeba zauważyć, że tutaj operujemy nie na samych strukturach, ale na wskazaniu na strukturę. Jednakże nadal możemy używać naszych kropeczek tylko w taki sposób:

(*nowy_element).key=klucz ≡ nowy_element->key=klucz

Są to zapisy równoważne tylko wygodniej się używa stylizowanej strzałki niż tych nawiasów. Dlatego ja dalej, gdy będę operował na wskazaniu na strukturę będę używał strzałek.

Aby dodać teraz element to listy musimy tą funkcję wywołać:

int x=5;

struct list *head=NULL; // inicjacja pustej listy

head=add_tail(head,x); // wywołanie funkcji, należy pamiętać że funkcja zwraca nowy
//adres głowy, więc należy go przypisać

KOD:
(wersja bez zwracanie [wskaźnik na wskaźnik])

void add_tail(struct list **head, int klucz){

struct list *nowy_element=(struct list*)malloc(sizeof(struct list));

// tworzymy nowy element typu naszej listy

struct list *w=*head;

// nasze zmienne pomocnicze

nowy_element->next=NULL; // na razie ustawiamy wskaźniki na NULL

nowy_element->prev=NULL; // dodatkowo dla listy dwukierunkowej

nowy_element->key=klucz; // przypisanie naszego klucza

if(*head==NULL){ // jeśli nie ma głowy nasz element staje się głową

      *head=nowy_element; // zmieniamy głowę

}else{ // gdy mamy jakieś elementy już w liście

      while(w->next!=NULL){ // pętlą szukamy końca listy

      w=w->next;

      }

      // po wykonaniu się pętli w wskazuje na ostatni element

      // ustawiamy relacje

      w->next = nowy_element;

      nowy_element->prev = w; // dodatkowo dla listy dwukierunkowej

}

}

Kod jest bardzo podobny do poprzedniej wersji, różni się tylko sposobem przekazania argumentu, który zawiera głowę naszej listy. Jest to wskazanie na wskaźnik naszej głowy. W kodzie różni się to tym, że przy head dopisujemy gwiazdkę. Dzięki temu mamy możliwość zmieniania naszej głowy w funkcji, tak jak to było z naszą szklaneczką. Przez co nie musimy już zwracać naszej głowy dlatego mamy void. Należy pamiętać tylko, że jak zmienimy head w funkcji to head będzie ZMIENIONY w naszym programie.

Wywołanie też nie zmienia się dużo i jest podobne to tego co było przy wskaźnikach:

int x=5;

struct list *head=NULL;

add_tail(&head,x);

// teraz do funkcji dajemy adres, czyli nie potrzebujemy nic
// funkcją zwracać, więc nie potrzebujemy nic przypisywać

W ten sposób mamy kolejkę FIFO(First In First Out),pierwszy wchodzi to pierwszy wychodzi, czyli po prostu dodawanie do ogona.

b) do głowy (czyli na początek)

Dodawanie elementów do głowy jest podobne do tego do ogona, tylko za każdym razem nasz nowy element ląduje na początku naszej listy.

Początek nawet jest taki sam, bo jak nie mamy listy to nasz element staje się głową naszej listy. 
 

Natomiast kolejny element jest wstawiany przed nasz stary element, czyli na początku naszej listy.

Z każdym kolejnym elementem trzeba zrobić tak samo, czyli dać go na początek naszej listy.

KOD:

(Wersja ze zwracaniem głowy)

struct list* add_head(struct list *head, int klucz){

  struct list *nowy_element=(struct list*)malloc(sizeof(struct list));

  // tworzymy nowy element typu naszej listy

  nowy_element->next=NULL; // na razie ustawiamy wskaźniki na NULL

  nowy_element->prev=NULL; // dodatkowo dla listy dwukierunkowej

  nowy_element->key=klucz; // przypisanie naszego klucza

  if(head==NULL){ // jeśli nie ma głowy nasz element staje się głową

      head=nowy_element; // zmieniamy głowę

  }else{

      head->prev = nowy_element; // dodatkowo dla listy dwukierunkowej

      nowy_element->next = head;

      head=nowy_element;

      // ten zapis może być trochę dziwny, ale trzeba pamiętać, że to są wskaźniki,
      // a my najpierw ustalamy relację, a potem zmieniamy nasze wskazanie, czyli head
      // wskazuje na nowy element

  }

  return head; // zwracamy nową głowę

}

KOD:
(wersja bez zwracanie [wskaźnik na wskaźnik])

void add_head(struct list **head, int klucz){

  struct list *nowy_element=(struct list*)malloc(sizeof(struct list));

  // tworzymy nowy element typu naszej listy

  
  nowy_element->next=NULL; // na razie ustawiamy wskaźniki na NULL

  nowy_element->prev=NULL; // dodatkowo dla listy dwukierunkowej

  nowy_element->key=klucz; // przypisanie naszego klucza

  if(*head==NULL){ // jeśli nie ma głowy nasz element staje się głową

      *head=nowy_element; // zmieniamy głowę

  }else{

      (*head)->prev = nowy_element; // dodatkowo dla listy dwukierunkowej

      nowy_element->next = *head;

      *head=nowy_element;

  }

}

Wywoływanie tych funkcji jest takie samo, jak wywoływanie funkcji, która dodaje elementy do ogona.

W ten sposób mamy kolejkę LIFO (Last In First Out). Ostatni wchodzi, a pierwszy wychodzi. Na tej zasadzie jest zbudowany stos.

c) w określonej kolejności

Dodawanie w kolejności (np. liczby rosnąco lub malejąco) jest bardziej skomplikowane, ponieważ to dodawanie składa się z dodawań już omówionych oraz z dodawanie w środek. Ponieważ liczby możemy podawać w różnej kolejność, a chcemy by cały czas nasza relacja pomiędzy tymi liczbami była zachowana.

Ale żeby umilić życie to dodawanie zaczyna się tak samo jak każde inne dodawanie, czyli pierwszy element staje się naszą głową, bo w sumie to innego wyjścia nie ma.

Na początku dajemy liczbę 5, a liczby chcemy ustawiać rosnąco. 

 

Następnie dajemy liczbę 2 i musimy sprawdzić gdzie ją mamy wstawić (pomiędzy jakie elementy) tu mamy tylko jeden. 2 jest mniejsze od 5 więc wstawiamy przed 5 (czyli zmieniamy głowę).

Teraz chcemy dodać liczbę 4 i sprawdzamy relację za koleją. 4 jest większe od 2, więc idziemy dalej 5 jest większe od 4, więc stop. Musimy dodać element pomiędzy liczbę 2 i 5. A to się wiąże ze zmianą relacji między tymi elementami. Teraz (2)->next musi wskazywać na (4), a (4)->next=(5), tak sama sytuacja jest dla relacji wstecznej: (5)->prev=(4), a (4)->prev=(2).

No to dodajmy sobie jeszcze liczbę 8. Zaczynamy od sprawdzenia relacji 8 jest większe od 2, od 4, od 5, więc należy liczbę 8 dodać na koniec naszej listy czyli do ogona. To można zauważyć, że dodawanie do ogona również można potraktować, jak dodawanie w środek. Tylko dodajemy między element ostatni, a (NULL). Tylko przy ustawianiu relacji trzeba pamiętać, że NULL nie jest elementem struktury, bo to jest takie nic. Więc nie możemy zrobić (NULL)->prev=cos, bo dostaniemy błąd pamięci. 

 

KOD:

(Wersja ze zwracaniem głowy)

struct list* add_prio(struct list *head, int key){

 struct list *new_elem=(struct list*)malloc(sizeof(struct list));
 // tworzymy nasz element

 struct list *w=head,*y=head;

 // zmienne pomocnicze

 // ustawiamy wartości początkowe

 new_elem->key=key;

 new_elem->prev=NULL;

 new_elem->next=NULL;

 //

 if(w==NULL)head=new_elem; // gdy nie ma jeszcze głowy (lista pusta)

 else{ // gdy są elementy

      while(w!=NULL && w->key<key){

      // pętla szuka miejsca, gdzie wstawić nasz nowy element
      // czyli albo na koniec, bo nasz element jest największy,

      // albo gdy napotka klucz o większej wartość wtedy nasz element
      // będzie dodany przed niego

      y=w;

      w=w->next;

      }

 // po wykonaniu dodajemy pomiędzy „y” a „w”, ale należy sprawdzić czy pętla   się w ogóle wykonała

      if(w==head){

// gdy ten warunek spełniony pętla się nie wykonała, bo warunek od razu był nie spełniony czyli dodajemy do głowy

          // ustawienie relacji

          new_elem->next=head;

          head->prev=new_elem;

          head=new_elem;

          //

      }

      else{ // dodajemy w środek lub na koniec

    
          // ustawiamy relacje

         
          y->next=new_elem;

          new_elem->prev=y;

          new_elem->next=w;

     
          if(w!=NULL) w->prev=new_elem; // gdy dodajemy w środek czyli

          // „w” jest różne od NULL

      }

  }

return head; // zwracamy głowę

}

KOD:
(wersja bez zwracanie [wskaźnik na wskaźnik])

void add_prio(struct list **head, int key){

   struct list *new_elem=(struct list*)malloc(sizeof(struct list));
   // tworzymy nasz element

   struct list *w=*head,*y=*head;

   // zmienne pomocnicze

   // ustawiamy wartości początkowe

   new_elem->key=key;

   new_elem->prev=NULL;

   new_elem->next=NULL;

   //

   if(w==NULL)*head=new_elem; // gdy nie ma jeszcze głowy (lista pusta)

   else{ // gdy są elementy

      while(w!=NULL && w->key<key){

      // pętla szuka miejsca, gdzie wstawić nasz nowy element
      // czyli albo na koniec bo nasz element jest największy

      // albo gdy napotka klucz o większej wartość wtedy nasz element będzie dodany przed niego

      y=w;

      w=w->next;

      }

   // po wykonaniu dodajemy pomiędzy y a w, ale należy sprawdzić czy pętla się w ogóle wykonała

       if(w==*head){

// gdy ten warunek spełniony pętla się nie wykonała, bo warunek od razu był nie spełniony czyli dodajemy do głowy

          // ustawienie relacji

          new_elem->next=*head;

          (*head)->prev=new_elem;

          *head=new_elem;

          //

       }

       else{ // dodajemy w środek lub na koniec

          // ustawiamy relacje

          y->next=new_elem;

          new_elem->prev=y;

          new_elem->next=w;

          if(w!=NULL) w->prev=new_elem; // gdy dodajemy w środek czyli

          //„w” jest różne od NULL

       }

    }

}

W ten sposób powstała kolejka priorytetowa.

Wywoływanie funkcji jest takie same jak poprzednio.

2.USUWANIE ELEMENTU

Jak już mamy elementy w naszej liście to czasami zachodzi potrzeba, aby jakiś element z niej skasować. Na szczęście w listach usuwanie elementu jest łatwiejsze niż w tablicach, bo nie naruszamy spójności. Tylko po prostu zwalniamy wcześniej zajęte miejsce w naszej pamięci. Musimy tylko znaleźć nasz element i go usunąć, ale należy pamiętać o ustawieniu nowych relacji w liście, bo w przeciwnym razie nasza lista będzie „ucięta”, a do reszty elementów praktycznie stracimy dostęp.

Do zwalniana pamięci służy funkcja free(), potrzebuje tylko jednego argumentu i wymaga adresu, który mamy zwolnić.

np.:

free(w); // w jest wskazaniem na jakiś adres (np. w naszej liście)

Usuwania z listy tak samo jak dodawania mamy 3 rodzaje:

a) usuwanie głowy

Usunięcie głowy jest po prostu zmienieniem adresu naszej głowy na adres następny po naszej głowie, ale należy pamiętać aby ten adres zwolnić, bo w przeciwnym wypadku adres będzie cały czas zajęty.

Teraz tylko trzeba ustalić nowe relacje naszej listy.

 

Teraz element o kluczy 4 jest naszą nową głową.

KOD:

(Ze zwracanie adresu nowej głowy)

struct list* remove_head(struct list *head){

  if(head!=NULL){ // funkcja ma się wykonywać gdy lista istnieje

      
      struct list *w=head; // zmienna która przechowuje adres głowy

      
      // ustawiamy nowe relacje

      head=head->next; // przestawiamy wskazanie na głowę

      if(head!=NULL) // gdy nowa głowa nie będzie NULL

      head->prev=NULL; // aby wskazanie prev od nowej głowy wskazywało na NULL

      //

      free(w); // zwalniamy adres naszej starej głowy

      w=NULL; // i ustawiamy w na NULL

  }

  return head; // zwracamy adres nowej głowy

}

//////////////////////////////////////////////////////////////

KOD:

(wersja bez zwracanie [wskaźnik na wskaźnik])

void remove_head(struct list **head){

   if(*head!=NULL){ // funkcja ma się wykonywać gdy lista istnieje

       struct list *w=*head; // zmienna która przechowuje adres głowy

       // ustawiamy nowe relacje

       *head=(*head)->next; // przestawiamy wskazanie na głowę

       if(*head!=NULL) // gdy nowa głowa nie będzie NULL

       (*head)->prev=NULL; // aby wskazanie prev od nowej głowy wskazywało na NULL

       //

       free(w); // zwalniamy adres naszej starej głowy

       w=NULL; // i ustawiamy w na NULL

   }

}

Jak widzimy oba te kody nie wiele się różnią i w sumie taki był zamysł pisania przeze mnie tych kodów, aby łatwiej było się przestawić z jednej wersji na drugą. Myślę, że już potrafisz wywołać te funkcje, ale jeśli nie to wywołuje się je tak samo jak w przypadku dodawania tylko teraz celem funkcji jest usunięcie elementu. Możemy się jeszcze zastanowić co się stanie jeśli w liście będzie tylko jeden element. A no nic się nie stanie, znaczy się nic strasznego. Funkcja wykona się i przestawi naszą głowę na następny element, a tym elementem będzie NULL. Czyli nasz head będzie wskazywał teraz na NULL, co będzie oznaczało, że nasza lista jest pusta.

b) usuwanie ogona

Usunięcie ogona listy jest bardzo podobne do usunięcia głowy różnica jest taka, że teraz musimy przejść na koniec naszej listy.

A następnie ustawić nowe relacje dla naszej listy. 
 

KOD:

(Ze zwracanie adresu nowej głowy)

struct list* remove_tail(struct list *head){

   if(head!=NULL){ // funkcja ma się wykonywać gdy lista istnieje

       struct list *w=head, *y=head; // zmienne pomocnicze

       while(w->next != NULL){

          y=w;

          w=w->next;

       }

// pętla while będzie się wykonywało do puki następny element po naszym „w” będzie NULL, czyli będzie się
// wykonywała, aż „w” będzie wskazywał na ostatni element naszej listy, a „y” będzie wskazywał na przedostatni

 
   if(w==head){

      // oznacz to, że w naszej liście jest tylko jeden element, więc kasujemy głowę listy

      free(head); // zwalniamy adres head

      head=NULL; // wskaźnik head ustawiamy na NULL

  
   }else{ // kasujemy ostatni element czyli nasz element w

     
      y->next=NULL; // „y” jest teraz ostatnim elementem

      free(w) // zwalniamy adres „w” (ostatniego elementu)

      w=NULL; // wskaźnik „w” ustawiamy na NULL

   }

return head; // zwaracamy głowę

}

KOD:

(wersja bez zwracanie [wskaźnik na wskaźnik])

void remove_tail(struct list **head){

   if(*head!=NULL){ // funkcja ma się wykonywać gdy lista istnieje

       struct list *w=*head, *y=*head; // zmienne pomocnicze

       while(w->next != NULL){

          y=w;

          w=w->next;

       }

// pętla while będzie się wykonywało do puki następny element po naszym „w” będzie NULL, czyli będzie się
// wykonywała, aż „w” będzie wskazywał na ostatni element naszej listy, a „y” będzie wskazywał na przedostatni

 
     if(w==*head){

         // oznacz to, że w naszej liście jest tylko jeden element, więc kasujemy głowę listy

 
        free(*head); // zwalniamy adres head

        *head=NULL; // wskaźnik head ustawiamy na NULL

     }else{ // kasujemy ostatni element, czyli nasz element „w”

        y->next=NULL; // „y” jest teraz ostatnim elementem

        free(w) // zwalniamy adres „w” (ostatniego elementu)

        w=NULL; // wskaźnik „w” ustawiamy na NULL

     }

}

Naszym kasowanym elementem jest element „w”, który jest ustawiany prze pętle while. I teraz musimy rozważyć dwa przypadki, albo kasujemy głowę (bo mamy tylko jeden element w liście), albo ostatni element. Głowę kasujemy, gdy pętla while w ogóle się nie wykona. Natomiast jeśli się wykona w całości to „w” będzie wskazywał na ostatni element naszej listy, natomiast „y” na przed ostatni (po skasowaniu naszego ogona to właśnie „y” będzie nowym ogonem).

c) usuwanie podanego klucza

To kasowanie jest najbardziej skomplikowane, bo składa się z poprzednich kasowań oraz z usunięcia elementu ze środka listy. Wynika to z tego, że nie wiemy gdzie jest nasz klucz i najpierw musimy go znaleźć, a następnie skasować. Nasz klucz może być w 3 miejscach: na początku, w środku, na końcu i te 3 warianty musimy rozpatrzyć w naszym kodzie.

Nasza lista:

Zakładamy, że chcemy skasować element o kluczy 4. Więc najpierw musimy go znaleźć, a następnie ustalić jego położenie (początek, środek, koniec). Szukając klucza musimy porównywać klucze od początku naszej listy z naszym szukanym. Czyli porównujemy czy 2 równe jest 4 (NIE). Następnie czy 4 równe 4 (TAK). Więc usuwamy element o adresie [Adres 3], bo pod niem jest nasz szukany klucz.

Następnie musimy ustalić nowe relacje między elementami które sąsiadowały z naszym szukanym kluczem. 
 

KOD:

(Ze zwracanie adresu nowej głowy)

struct list * remove_key(struct list *head, int key){

   if(head){

      struct list *w=head,*y=head; // zmienne pomocnicze

      if(w->key==key){ // gdy szukany klucz jest pierwszym elementem

         if(w->next==NULL){ // gdy w liście jest tylko jeden element

            free(head); // kasujemy głowę

            head=NULL;

         }else{ // gdy w liście są jeszcze inne elementy

            head=head->next; // musimy ustalić nowe relacje

            head->prev=NULL;

            free(w); // skasować element

            w=NULL;

         }

      }

      else{

         while(w!=NULL && w->key!=key){ // pętla szuka naszego klucza

            y=w;

            w=w->next;

         }

// po przejściu pętli jeśli w naszej liście był szukany klucz

// „w” będzie wskazywał na adres naszego szukanego klucza

// jeśli w naszej liście nie było podanego klucza „w” będzie NULL

         if(w!=NULL){ // jeśli w naszej liście był szukany klucz

         // ustalamy relacje

         y->next=w->next;

         if(w->next != NULL)(w->next)->prev=y;

         //

         free(w); // kasujemy element

         w=NULL;

         }

      }

      return head; // zwracamy naszą głowę

   }

}

KOD:

(wersja bez zwracanie [wskaźnik na wskaźnik])

void remove_key(struct list **head, int key){

    
  if(*head){

      struct list *w=*head,*y=*head; // zmienne pomocnicze

      if(w->key==key){ // gdy szukany klucz jest pierwszym elementem

      if(w->next==NULL){ // gdy w liście jest tylko jeden element

      free(*head); // kasujemy głowę

      *head=NULL;

  
  }else{ // gdy w liście są jeszcze inne elementy

    
     *head=(*head)->next; // musimy ustalić nowe relacje

     (*head)->prev=NULL;

     free(w); // skasować element

     w=NULL;

  }

  }else{ // gdy nasz klucz nie jest pierwszym elementem

     while(w!=NULL && w->key!=key){ // pętla szuka naszego klucza

        y=w;

        w=w->next;

     }

// po przejściu pętli jeśli w naszej liście był szukany klucz

// „w” będzie wskazywał na adres naszego szukanego klucza

// jeśli w naszej liście nie było podanego klucza „w” będzie NULL

   if(w!=NULL){ // jeśli w naszej liście był szukany klucz

      // ustalamy relacje

      y->next=w->next;

      if(w->next != NULL)(w->next)->prev=y;

      //

      free(w); // kasujemy element

      w=NULL;

      }
    }
  }
}

Jak widać kod usuwania z listy podanego elementu jest bardziej złożony. Ponieważ trzeba rozważyć wiele przypadków, ale jeśli się to zrozumie to napisanie kodu nie jest już takie trudne. Tylko trzeba pamiętać o wszystkich możliwościach.

Na początku rozważamy możliwość, że nasz szukany klucz jest pierwszym elementem listy. Następnie sprawdzamy ile jest elementów w liście. Jeśli tylko jeden to po skasowanie naszego znalezionego nic w niej nie zostanie, natomiast jeśli więcej po prostu kasujemy głowę (tak samo robiliśmy przy kasowanie głowy). Następnie rozważamy możliwość, że nasz klucz nie jest jedynym elementem w liście, więc musimy go znaleźć. Pętla while szuka naszego klucza i jeśli będzie znaleziony to „w” będzie wskazywał właśnie na nasz klucz. Natomiast jeśli nie będzie znaleziony, czyli naszego klucza nie było w liście, „w” będzie wskazywał na NULL. Jak już mamy znaleziony element to musimy ustalić relacje (nasz element znajduje się pomiędzy „y” a „w->next”). Trzeba jeszcze pamiętać o tym, że nasz element może być w środku lub NA KOŃCU, czyli nasz [w->next=NULL], czyli nie możemy sobie zrobić, od tak, odwołanie wstecz, bo nie można zrobić coś takiego (NULL)->prev. Dlatego musimy dać warunek, który sprawdzi, czy następny element istnieje. W listach jednokierunkowych nie ma takiego problemu, bo nie musimy odwoływać się wstecz przy ustalanie relacji.