Lista

Lista (ang. list) jest dynamiczną strukturą danych, co oznacza, iż jej rozmiar (ilość zawartych na liście elementów) może się dowolnie (z ograniczeniem pamięci komputera) zmieniać w czasie działania programu. Lista składa się z połączonych ze sobą elementów. Ze względu na połączenie elementów rozróżniamy:

Listę jednokierunkową (ang. single conected list) - każdy element listy połączony jest tylko z elementem następnym. Listę jednokierunkową możemy przechodzić tylko w jednym kierunku - od elementu pierwszego do ostatniego.

e1 → e2 → e3 → ... → en-1 → en

Listę dwukierunkową (ang. double conected list) - każdy element listy połączony jest z elementem następnym oraz poprzednim. Listę dwukierunkową możemy przechodzić w obu kierunkach - od pierwszego elementu do ostatniego lub od ostatniego do pierwszego. Co ważniejsze, lista dwukierunkowa pozwala nam się cofać, a jest to bardzo przydatne w wielu algorytmach.

e1 ↔ e2 ↔ e3 ↔ ... ↔ en-1 ↔ en

W celu realizacji struktury listy jej elementy muszą posiadać odpowiednią budowę. Połączenie z elementem następnym i poprzednim (w liście jednokierunkowej tylko z następnym) uzyskuje się zapamiętując w elemencie listy odpowiednie adresy. Dlatego element listy składa się z dwóch części:

adresowej - służącej do obsługi listy
danych - służącej do przechowywania danych związanych z elementem listy.

W części adresowej umieszczamy dwa pola będące wskaźnikami elementów listy:

next - wskazuje następny element na liście. Jeśli zawiera wartość NULL, to dany element nie posiada następnika, czyli jest ostatnim elementem listy.
prev - wskazuje poprzedni element listy dwukierunkowej. Jeśli zawiera NULL, to dany element nie posiada poprzednika, czyli jest pierwszym elementem listy.

Jeśli chcemy wyszukiwać elementy listy, to często dodaje się jeszcze pole:

key - zawiera tzw. klucz, czyli wartość, wg której elementy listy tworzą pewien porządek, ciąg wartości. Zawartość pola key może być wykorzystywana przez algorytmy sortujące listę lub wyszukujące na niej elementy największe lub najmniejsze.

Chcąc utworzyć listę w języku C++ musimy najpierw zadeklarować typ danych elementów listy. W tym celu tworzymy następujące deklaracje:

lista
jednokierunkowa		 lista
dwukierunkowa		 
struct TlistElement
{
  TListElement * next;
  int key;
  ...
};  
struct TlistElement
{
  TListElement * next, * prev;
  int key;
  ...
};

Kropki ... oznaczają część danych, w której programista może sobie umieścić dowolne, potrzebne mu w bieżącej implementacji dane. Ponieważ nie służą one do obsługi listy, nie będziemy się tutaj zajmować częścią danych elementu listy.

Deklaracja typu tworzy plan elementu. Według tego planu będą budowane kolejne elementy listy. Zwróć uwagę, iż wewnątrz deklaracji typu TlistElement powtarza się definiowany typ dla pól next i prev.

Oprócz elementów lista musi posiadać zmienną (u nas zmienna ta nazywa się front), która wskazuje pierwszy element na liście. Jeśli zmienna ta zawiera wartość NULL, to lista jest pusta. Często dla szybkiego wstawiania danych na końcu listy dodaje się jeszcze jedną zmienną (u nas back), wskazującą ostatni element. Dodatkową zmienną jest licznik elementów (u nas counter). Oczywiście elementy listy można zliczyć przechodząc przez nie kolejno od pierwszego do ostatniego, lecz taka operacja jest kosztowna i ma złożoność O(n). Lepszym rozwiązaniem jest dodanie licznika, w którym zliczamy dodawane i usuwane elementy.

Lista jednokierunkowa

Poniżej przedstawiamy przykład implementacji klasy języka C++ z listą jednokierunkową:

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P013-01

#include <iostream>

using namespace std;

// deklaracja typu elementu listy
//-------------------------------

struct TlistElement
{
  TlistElement * next;
  int key;
};


// deklaracja typu klasy listy jednokierunkowej
//---------------------------------------------

class TsingleList
{
  private:

    TlistElement * front, * back;
    unsigned counter;

  public:
           
// konstruktor
//------------

    TsingleList()
    {
      front = back = NULL;
      counter  = 0;
    }
    
// destruktor
//-----------

    ~TsingleList()
    {
      TlistElement * p;
      
      while(front)
      {
        p = front->next;
        delete front;
        front = p;
      }              
    }

// Zwraca długość listy
//---------------------

    unsigned size()
    {
      return counter;
    }

// Dodaje element na początku listy i zwraca jego adres
//-----------------------------------------------------

    TlistElement * push_front(TlistElement * p)
    {
      p->next = front;
      front = p;
      if(!back) back = front;
      counter++;
      return front;
    }
    
// Dodaje element na końcu listy i zwraca jego adres
//--------------------------------------------------

    TlistElement * push_back(TlistElement * p)
    {
      if(back) back->next = p;
      p->next = NULL;
      back = p;
      if(!front) front = back;
      counter++;
      return back;
    }
    
// Dodaje element p1 za elementem p2 i zwraca adres p1
//----------------------------------------------------

    TlistElement * insert(TlistElement * p1, TlistElement * p2)
    {
      p1->next = p2->next;
      p2->next = p1;
      if(!(p1->next)) back = p1;
      counter++;
      return p1;
    }
    
// Usuwa element z początku listy i zwraca adres usuniętego elementu
//------------------------------------------------------------------

    TlistElement * pop_front()
    {
      TlistElement * p;
      
      if(front)
      {
        p = front;
        front = front->next;
        if(!front) back = NULL;
        counter--;
        return p;
      }
      else return NULL;     
    }
    
// Usuwa element z końca listy i zwraca adres usuniętego elementu
//---------------------------------------------------------------

    TlistElement * pop_back()
    {
      TlistElement * p;
      
      if(back)
      {
        p = back;
        if(p == front) front = back = NULL;
        else
        {
          back = front;
          while(back->next != p) back = back->next;
          back->next = NULL;
        }
        counter--;
        return p;
      }
      else return NULL;
    }
    
// usuwa z listy element p i zwraca adres usuniętego elementu

    TlistElement * erase(TlistElement * p)
    {
      TlistElement * p1;

      if(p == front) return pop_front();
      else
      {
        p1 = front;
        while(p1->next != p) p1 = p1->next;
        p1->next = p->next;
        if(!(p1->next)) back = p1;
        counter--;
        return p;
      }
    } 

// zwraca n-ty element listy. Jeśli lista posiada mniej niż n elementów,
// zwraca NULL. Elementy numerujemy od 1.
//----------------------------------------------------------------------

    TlistElement * index(unsigned n)
    {
      TlistElement * p;
      
      if((!n) || (n > counter)) return NULL;
      else if(n == counter) return back;
      else
      {
        p = front;
        while(--n) p = p->next;
        return p;
      }
    }

// wyświetla kolejno klucze wszystkich elementów listy
//----------------------------------------------------

    void showKeys()
    {
      TlistElement * p;
      
      if(!front) cout << "Lista jest pusta." << endl;
      else
      {
        p = front;
        while(p)
        {
          cout << p->key << " ";
          p = p->next;
        }
        cout << endl;
      }
    }
};

//************************************************************************
//**     Przykładowa aplikacja testująca utworzoną klasę TsingleList    **
//************************************************************************

main()
{
  TsingleList    sl;
  TlistElement * p;
  int            i;
  
  cout << "(A) : "; sl.showKeys();
  
// tworzymy pięć elementów dodając je kolejna na początek listy

  for(i = 1; i <= 5; i++)
  {
    p = new TlistElement;
    p->key = i;
    sl.push_front(p);
  }

  cout << "(B) : ";   sl.showKeys();
  
// tworzymy pięć elementów dodając je kolejna na koniec listy

  for(i = 1; i <= 5; i++)
  {
    p = new TlistElement;
    p->key = i;
    sl.push_back(p);
  }

  cout << "(C) : ";   sl.showKeys();

// usuwamy pierwszy element listy

  sl.pop_front();
  
  cout << "(D) : ";   sl.showKeys();

// usuwamy ostatni element listy

  sl.pop_back();
  
  cout << "(E) : ";   sl.showKeys();
 
// usuwamy trzeci element z listy

  delete sl.erase(sl.index(3));
  
  cout << "(F) : ";   sl.showKeys();

// usuwamy przedostatni element z listy

  delete sl.erase(sl.index(sl.size() - 1));
  
  cout << "(G) : ";   sl.showKeys();

// Za czwartym elementem listy wstawiamy nowy element z kluczem 9

  p = new TlistElement;
  p->key = 9;
  sl.insert(p,sl.index(4));
  
  cout << "(H) : ";   sl.showKeys();

// usuwamy wszystkie elementy z listy

  while(sl.size()) sl.pop_front();
  
  cout << "(I) : ";   sl.showKeys();
  
  cout << endl << endl; 
  system("PAUSE");
}

(A) : Lista jest pusta.
(B) : 5 4 3 2 1
(C) : 5 4 3 2 1 1 2 3 4 5
(D) : 4 3 2 1 1 2 3 4 5
(E) : 4 3 2 1 1 2 3 4
(F) : 4 3 1 1 2 3 4
(G) : 4 3 1 1 2 4
(H) : 4 3 1 1 9 2 4
(I) : Lista jest pusta.

       Wyjaśnienia

struct TlistElement
{
  TlistElement * next;
  int key;
};
 Deklaracja typu elementu listy jednokierunkowej. W przykładowym programie elementy listy będą zawierały pole next, wskazujące następny element oraz pole key, zawierające klucz elementu. W rzeczywistych implementacjach z elementami list można kojarzyć dowolne dane, w tym również listy! 
class TsingleList
{
  private:

    TlistElement * front, * back;
    unsigned counter;
 W sekcji prywatnej klasy definiujemy trzy pola:
front - wskazuje pierwszy element listy
back - wskazuje ostatni element listy
counter - zawiera liczbę elementów na liście

Do pól w sekcji prywatnej posiadają dostęp tylko funkcje składowe klasy. Na zewnątrz pola te nie są widoczne.

 
  public:
 W sekcji publicznej deklarujemy interfejs programowy klasy. 
    TsingleList()
    {
      front = back = NULL;
      counter  = 0;
    }
 Konstruktor to specjalna funkcja składowa klasy, która jest wywoływana tuż po utworzeniu zmiennej. Zadaniem konstruktora jest inicjalizacja istotnych dla działania klasy pól.

W tym przypadku zerujemy pola adresów front i back. Również zerujemy licznik elementów listy.

 
    ~TsingleList()
    {
      TlistElement * p;
      
      while(front)
      {
        p = front->next;
        delete front;
        front = p;
      }              
    }
 Destruktor to druga funkcja specjalna w klasie. Jest ona wywoływana tuż przed usunięciem z pamięci zmiennej. Zadaniem destruktora jest zwolnienie zajętych przez klasę zasobów.

W naszym przypadku destruktor usuwa kolejno wszystkie elementy przechowywanej w klasie listy. Usuwanie rozpoczyna się od pierwszego elementu. W zmiennej p zapamiętujemy adres elementu następnego. Następnie usuwamy element wskazywany przez front i do front wprowadzamy adres następnego elementu. W efekcie lista zmniejsza się o jeden element. Działanie to wykonujemy dotąd, aż front przestanie wskazywać jakikolwiek element listy - lista będzie pusta.

 
    unsigned size()
    {
      return counter;
    }
 Funkcja składowa size() zwraca zawartość licznika elementów counter. Licznik counter jest odpowiednio modyfikowany przez procedury dopisujące i usuwające elementy z listy i zawiera on aktualną liczbę elementów, które przechowuje lista. 
    TlistElement * push_front(TlistElement * p)
    {
      p->next = front;
      front = p;
      if(!back) back = front;
      counter++;
      return front;
    }
 Funkcja push_front(p) wstawia nowy element p na początek listy i zwraca jego adres.

Najpierw wpisuje w pole next elementu p adres pierwszego elementu listy. W efekcie pierwszy element listy staje się elementem następnym dla p. W polu front zostaje umieszczony adres elementu p, czyli staje się on pierwszym elementem na liście.

Lista mogła być pusta. Jeśli pole back zawiera NULL, to wstawiony element jest jedynym jak dotąd elementem listy. Zatem jest on zarówno elementem pierwszym jak i ostatnim. Dlatego w polu back umieszczamy w tym przypadku adres pierwszego elementu pobrany z pola front.

Po wstawieniu elementu zwiększamy licznik counter i zwracamy adres pierwszego elementu listy.

 
    TlistElement * push_back(TlistElement * p)
    {
      if(back) back->next = p;
      p->next = NULL;
      back = p;
      if(!front) front = back;
      counter++;
      return back;
    }
 Funkcja push_back(p) wstawia nowy element p na koniec listy i zwraca jego adres.

Jeśli lista zawiera jakieś elementy, to back zawsze wskazuje ostatni element listy. W pole next ostatniego elementu wpisujemy w takim przypadku adres wstawianego elementu. W efekcie zostanie on dołączony do końca listy. W polu next nowego elementu umieszczamy adres zerowy NULL, ponieważ jest on teraz ostatnim elementem i nie posiada następnika.

Lista mogła być pusta. W takim przypadku wstawiony element jest jednocześnie pierwszym i ostatnim. Dlatego do pola front wpisujemy adres pobrany z pola back.

Po wstawieniu elementu zwiększamy licznik counter i zwracamy adres końca listy.

 
    TlistElement * insert(TlistElement * p1, TlistElement * p2)
    {
      p1->next = p2->next;
      p2->next = p1;
      if(!(p1->next)) back = p1;
      counter++;
      return p1;
    }
Funkcja insert(p1,p2) wstawia nowy element p1 za elementem p2. Element p2 musi należeć do listy.

Najpierw następnik p2 staje się następnikiem p1. Następnie jako następnik p2 wprowadzamy p1. Dzięki tym operacjom element p1 zostaje umieszczony na liście za elementem p2.

Jeśli następnik nowego elementu nie istnieje, to p1 stał się nowym końcem listy. W takim przypadku w polu back umieszczamy nowy adres końca listy, czyli adres p1.

Zwiększamy licznik counter i zwracamy adres p1.

 
    TlistElement * pop_front()
    {
      TlistElement * p;
      
      if(front)
      {
        p = front;
        front = front->next;
        if(!front) back = NULL;
        counter--;
        return p;
      }
      else return NULL;     
    }
 Funkcja pop_front() usuwa z listy pierwszy element i zwraca jego adres. Element zostaje jedynie odłączony od listy, lecz wciąż zajmuje swój obszar pamięci. Program główny coś powinien z takim elementem zrobić - np. dołączyć go w innym miejscu listy, odpowiednio przetworzyć lub usunąć.

Na początku sprawdzamy, czy lista zawiera jakiś element. Jeśli nie, zwracamy NULL. W przeciwnym razie zapamiętujemy w zmiennej p adres pierwszego elementu. W polu front umieszczamy adres następnego elementu listy. W ten sposób element p zostaje odłączony logicznie od listy.

Jeśli po odłączeniu pole front zawiera adres NULL, to lista jest obecnie pusta i NULL wpisujemy również do pola back.

Zmniejszamy o jeden licznik counter i zwracamy adres usuniętego z listy elementu.

 
    TlistElement * pop_back()
    {
      TlistElement * p;
      
      if(back)
      {
        p = back;
        if(p == front) front = back = NULL;
        else
        {
          back = front;
          while(back->next != p) back = back->next;
          back->next = NULL;
        }
        counter--;
        return p;
      }
      else return NULL;
    }
 Funkcja pop_back() usuwa z listy ostatni element i zwraca jego adres. Podobnie jak w przypadku funkcji pop_front() element jest jedynie odłączany od listy i wciąż znajduje się w pamięci komputera.

Jeśli lista jest pusta, to pole back zawiera NULL. W takim przypadku zwracamy NULL i kończymy.

W przeciwnym razie zapamiętujemy adres ostatniego elementu listy w p. Jeśli lista zawiera tylko jeden element , to pola front i back zawierają ten sam adres. W takim przypadku lista staje się pusta po odłączeniu ostatniego elementu, dlatego wpisujemy w nie adres pusty NULL.

Jeśli lista zawiera więcej niż jeden element, to przechodzimy kolejno przez wszystkie elementy listy ustawiając pole back na adres poprzednika ostatniego elementu. W poprzedniku zerujemy następnik.

Zmniejszamy licznik i zwracamy zapamiętany w p adres ostatniego elementu.

 
    TlistElement * erase(TlistElement * p)
    {
      TlistElement * p1;

      if(p == front) return pop_front();
      else
      {
        p1 = front;
        while(p1->next != p) p1 = p1->next;
        p1->next = p->next;
        if(!(p1->next)) back = p1;
        counter--;
        return p;
      }
    }
Funkcja erase(p) usuwa element z listy i zwraca jego adres. Usuwany element musi należeć do listy.

Na początku sprawdzamy, czy usuwany element jest pierwszym elementem listy. Jeśli tak, to wykorzystujemy funkcję pop_front().

W przeciwnym razie szukamy poprzednika p wykorzystując p1. Do pola next poprzednika p1 wprowadzamy adres następnika p. W efekcie element p zostaje usunięty z listy. Sprawdzamy, czy p1 jest ostatnim elementem listy. Jeśli tak, to do pola back wprowadzamy jego adres.Zmniejszamy licznik i zwracamy adres p.

 
    TlistElement * index(unsigned n)
    {
      TlistElement * p;
      
      if((!n) || (n > counter)) return NULL;
      else if(n == counter) return back;
      else
      {
        p = front;
        while(--n) p = p->next;
        return p;
      }
    }
 Funkcja index(n) zwraca adres n-tego elementu listy.

Na początku sprawdzamy, czy lista zawiera n-ty element. Jeśli nie, zwracamy NUL.

W przeciwnym razie przechodzimy przez n - 1 elementów. W wyniku w zmiennej p otrzymujemy adres n-tego elementu listy, który zwracamy jako wynik działania funkcji.

 
    void showKeys()
    {
      TlistElement * p;
      
      if(!front) cout << "Lista jest pusta." << endl;
      else
      {
        p = front;
        while(p)
        {
          cout << p->key << " ";
          p = p->next;
        }
        cout << endl;
      }
    }
};
 Funkcję showKeys() utworzono na potrzeby testowania klasy Tlist. Wyświetla ona w jednym wierszu klucze wszystkich elementów listy. Jeśli lista jest pusta, zostaje wyświetlony odpowiedni napis.

Podsumowanie funkcji składowych klasy TsingleList

Funkcja krótki opis
size() Zwraca liczbę elementów przechowywanych na liście.
push_front(p) Umieszcza element p na początku listy i zwraca jego adres.
push_back(p) Umieszcza element p na końcu listy i zwraca jego adres.
insert(p1,p2) Dodaje element p1 za elementem p2 i zwraca adres p1.
pop_front() Pobiera element z początku listy.
pop_back() Pobiera element z końca listy.
erase(p) Usuwa z listy element p i zwraca adres usuniętego elementu.
index(n) Zwraca n-ty element listy. Elementy numerujemy od 1.
showKeys() Wyświetla kolejno klucze wszystkich elementów listy.

 

       Lista dwukierunkowa

Poniżej przedstawiamy przykład klasy obsługującej listę dwukierunkową. W liście dwukierunkowej niektóre operacje wykonujemy zdecydowanie szybciej, ponieważ istnieje możliwość cofnięcia się do poprzednika - operacja taka w przypadku listy jednokierunkowej wymaga przejścia przez wszystkie elementy od początku listy do elementu poprzedzającego.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P013-02

#include <iostream>

using namespace std;

// deklaracja typu elementu listy
//-------------------------------

struct TlistElement
{
  TlistElement * next, * prev;
  int key;
};


// deklaracja typu klasy listy dwukierunkowej
//-------------------------------------------

class TdoubleList
{
  private:

    TlistElement * front, * back;
    unsigned counter;

  public:
           
// konstruktor
//------------

    TdoubleList()
    {
      front = back = NULL;
      counter  = 0;
    }
    
// destruktor
//-----------

    ~TdoubleList()
    {
      TlistElement * p;
      
      while(front)
      {
        p = front->next;
        delete front;
        front = p;
      }              
    }

// Zwraca długość listy
//---------------------

    unsigned size()
    {
      return counter;
    }

// Dodaje element na początku listy i zwraca jego adres
//-----------------------------------------------------

    TlistElement * push_front(TlistElement * p)
    {
      p->next = front; p->prev = NULL;
      if(front) front->prev = p;
      front = p;
      if(!back) back = front;
      counter++;
      return front;
    }
    
// Dodaje element na końcu listy i zwraca jego adres
//--------------------------------------------------

    TlistElement * push_back(TlistElement * p)
    {
      if(back) back->next = p;
      p->next = NULL; p->prev = back;
      back = p;
      if(!front) front = back;
      counter++;
      return back;
    }
    
// Dodaje element p1 za elementem p2 i zwraca adres p1
//----------------------------------------------------

    TlistElement * insert(TlistElement * p1, TlistElement * p2)
    {
      p1->next = p2->next; p1->prev = p2;
      p2->next = p1;
      if(p1->next) p1->next->prev = p1;
      else back = p1;
      counter++;
      return p1;
    }
    
// Usuwa element z początku listy i zwraca adres usuniętego elementu
//------------------------------------------------------------------

    TlistElement * pop_front()
    {
      TlistElement * p;
      
      if(front)
      {
        p = front;
        front = front->next;
        if(!front) back = NULL;
        else front->prev = NULL;
        counter--;
        return p;
      }
      else return NULL;     
    }
    
// Usuwa element z końca listy i zwraca adres usuniętego elementu
//---------------------------------------------------------------

    TlistElement * pop_back()
    {
      TlistElement * p;
      
      if(back)
      {
        p = back;
        if(p == front) front = back = NULL;
        else
        {
          back = back->prev;
          back->next = NULL;
        };
        counter--;
        return p;
      }
      else return NULL;
    }
    
// usuwa z listy element p i zwraca adres usuniętego elementu

    TlistElement * erase(TlistElement * p)
    {
      TlistElement * p1;
      
      if(p->prev) p->prev->next = p->next;
      else front = p->next;
      if(p->next) p->next->prev = p->prev;
      else back = p->prev;
      counter--;
      return p;
    } 

// zwraca n-ty element listy. Jeśli lista posiada mniej niż n elementów,
// zwraca NULL. Elementy numerujemy od 1.
//----------------------------------------------------------------------

    TlistElement * index(unsigned n)
    {
      TlistElement * p;
      
      if((!n) || (n > counter)) return NULL;
      else if(n == counter) return back;
      else if(n < counter / 2)
      {
        p = front;
        while(--n) p = p->next;
        return p;
      }
      else
      {
        p = back;
        while(counter > n++) p = p->prev;
        return p;
      }  
    }

// wyświetla kolejno klucze wszystkich elementów listy
//----------------------------------------------------

    void showKeys()
    {
      TlistElement * p;
      
      if(!front) cout << "Lista jest pusta." << endl;
      else
      {
        p = front;
        while(p)
        {
          cout << p->key << " ";
          p = p->next;
        }
        cout << endl;
      }
    }
};

//************************************************************************
//**     Przykładowa aplikacja testująca utworzoną klasę TsingleList    **
//************************************************************************

main()
{
  TdoubleList    dl;
  TlistElement * p;
  int            i;
  
  cout << "(A) : "; dl.showKeys();
  
// tworzymy pięć elementów dodając je kolejna na początek listy

  for(i = 1; i <= 5; i++)
  {
    p = new TlistElement;
    p->key = i;
    dl.push_front(p);
  }

  cout << "(B) : ";   dl.showKeys();
  
// tworzymy pięć elementów dodając je kolejna na koniec listy

  for(i = 1; i <= 5; i++)
  {
    p = new TlistElement;
    p->key = i;
    dl.push_back(p);
  }

  cout << "(C) : ";   dl.showKeys();

// usuwamy pierwszy element listy

  dl.pop_front();
  
  cout << "(D) : ";   dl.showKeys();

// usuwamy ostatni element listy

  dl.pop_back();
  
  cout << "(E) : ";   dl.showKeys();
 
// usuwamy trzeci element z listy

  delete dl.erase(dl.index(3));
  
  cout << "(F) : ";   dl.showKeys();

// usuwamy przedostatni element z listy

  delete dl.erase(dl.index(dl.size() - 1));
  
  cout << "(G) : ";   dl.showKeys();

// Za czwartym elementem listy wstawiamy nowy element z kluczem 9

  p = new TlistElement;
  p->key = 9;
  dl.insert(p,dl.index(4));
  
  cout << "(H) : ";   dl.showKeys();

// usuwamy wszystkie elementy z listy

  while(dl.size()) dl.pop_front();
  
  cout << "(I) : ";   dl.showKeys();
  
  cout << endl << endl; 
  system("PAUSE");
}

(A) : Lista jest pusta.
(B) : 5 4 3 2 1
(C) : 5 4 3 2 1 1 2 3 4 5
(D) : 4 3 2 1 1 2 3 4 5
(E) : 4 3 2 1 1 2 3 4
(F) : 4 3 1 1 2 3 4
(G) : 4 3 1 1 2 4
(H) : 4 3 1 1 9 2 4
(I) : Lista jest pusta.

       Wyjaśnienia

struct TlistElement
{
  TlistElement * next, * prev;
  int key;
};
 Deklaracja typu elementu listy jednokierunkowej. W przykładowym programie elementy listy będą zawierały pola next i prev, wskazujące następny i poprzedni element oraz pole key, zawierające klucz elementu. 
class TdoubleList
{
  private:

    TlistElement * front, * back;
    unsigned counter;
 Deklaracja klasy obsługującej listę dwukierunkową. Klasa w części prywatnej zawiera identyczne pola jak klasa TsingleList:

front - adres pierwszego elementu listy
back - adres ostatniego elementu listy
counter - licznik elementów umieszczonych na liście

 
  public:
           
// konstruktor
//------------

    TdoubleList()
    {
      front = back = NULL;
      counter  = 0;
    }
    
// destruktor
//-----------

    ~TdoubleList()
    {
      TlistElement * p;
      
      while(front)
      {
        p = front->next;
        delete front;
        front = p;
      }              
    }
 W części publicznej znajduje się interfejs klasy.

Konstruktor inicjuje pola prywatne.

Destruktor usuwa elementy listy.

 
    unsigned size()
    {
      return counter;
    }
 Funkcja size() zwraca liczbę elementów przechowywanych na liście, czyli rozmiar listy. 
    TlistElement * push_front(TlistElement * p)
    {
      p->next = front; p->prev = NULL;
      if(front) front->prev = p;
      front = p;
      if(!back) back = front;
      counter++;
      return front;
    }
 Funkcja push_front(p) umieszcza element p na początku listy.

Następnik p ustawiamy na bieżący pierwszy element listy, a poprzednik zerujemy.

Jeśli lista zawiera pierwszy element, to jako poprzednik pierwszego elementu ustawiamy element p. Jako początek listy określamy element p. Na koniec sprawdzamy jeszcze, czy wprowadzony element jest jedynym elementem listy. Jeśli tak, to również określamy go jako element ostatni. Zwiększamy licznik i zwracamy adres pierwszego elementu.

 
    TlistElement * push_back(TlistElement * p)
    {
      if(back) back->next = p;
      p->next = NULL; p->prev = back;
      back = p;
      if(!front) front = back;
      counter++;
      return back;
    }
 Funkcja push_back(p) umieszcza element p na końcu listy.

Jeśli lista posiada element ostatni, to element p określamy jako następnik ostatniego elementu. Zerujemy następnik p, a jako poprzednik p określamy ostatni element listy.

Ustawiamy element p jako element ostatni na liście. Jeśli jest on jedynym elementem listy, to również określamy go jako pierwszy element.

Zwiększamy licznik counter i zwracamy adres ostatniego elementu.

 
    TlistElement * insert(TlistElement * p1, TlistElement * p2)
    {
      p1->next = p2->next; p1->prev = p2;
      p2->next = p1;
      if(p1->next) p1->next->prev = p1;
      else back = p1;
      counter++;
      return p1;
    }
 Funkcja insert(p1,p2) umieszcza na liście element p1 za elementem p2.

Jako następnik p1 ustawiamy następnik p2. Jako poprzednik p1 ustawiamy p2. Jako następnik p2 ustawiamy p1.

Jeśli istnieje następnik p1, to jego poprzednikiem robimy p1, w przeciwnym razie p1 jest ostatnim elementem listy, zatem ustawiamy na jego adres pole back.

Zwiększamy licznik i zwracamy adres elementu p1.

 
    TlistElement * pop_front()
    {
      TlistElement * p;
      
      if(front)
      {
        p = front;
        front = front->next;
        if(!front) back = NULL;
        else front->prev = NULL;
        counter--;
        return p;
      }
      else return NULL;     
    }
 Funkcja pop_front() pobiera element z początku listy.

Jeśli lista jest pusta, to zwracamy adres pusty NULL. W przeciwnym razie zapamiętujemy w p bieżący początek listy. Jako nowy początek wybieramy następnik pierwszego elementu.

Jeśli ten następnik nie istnieje, lista staje się pusta i w polu back również umieszczamy adres NULL. W przeciwnym razie zerujemy pole prev następnika.

Zwiększamy licznik i zwracamy adres p, czyli adres byłego pierwszego elementu listy.

 
    TlistElement * pop_back()
    {
      TlistElement * p;
      
      if(back)
      {
        p = back;
        if(p == front) front = back = NULL;
        else
        {
          back = back->prev;
          back->next = NULL;
        };
        counter--;
        return p;
      }
      else return NULL;
    }
 Funkcja pop_back() pobiera element z końca listy.

Jeśli lista jest pusta, zwracamy adres pusty NULL. W przeciwnym razie zapamiętujemy w zmiennej p adres ostatniego elementu. Jeśli lista zawiera tylko ten jeden element, to po jego usunięciu stanie się pusta. W takim przyadku zerujemy oba pola front i back.

Jeśli na liście znajduje się więcej niż jeden element, to ostatni posiada poprzednika. Pole back ustawiamy na poprzednika obecnego ostatniego elementu i zerujemy następnik - przedostatni element staje się elementem ostatnim. Zwróć uwagę, iż dla listy dwukierunkowej operacja ta ma stały czas wykonania O(1), podczas gdy dla listy jednokierunkowej posiada czas liniowy O(n), ponieważ znalezienie poprzednika wymaga przejścia przez wszystkie elementy listy od pierwszego do ostatniego. Zatem w algorytmach wymagających pobierania elementu końcowego należy stosować listy dwukierunkowe.

Zmniejszamy licznik i zwracamy zapamiętany adres ostatniego elementu.

 
    TlistElement * erase(TlistElement * p)
    {
      TlistElement * p1;
      
      if(p->prev) p->prev->next = p->next;
      else front = p->next;
      if(p->next) p->next->prev = p->prev;
      else back = p->prev;
      counter--;
      return p;
    }
Funkcja erase(p) usuwa z listy element p.

Jeśli istnieje poprzednik p, to jego następnikiem robimy następnik p. W przeciwnym wypadku element p jest pierwszym elementem listy, dlatego w polu front umieszczamy adres następnika p.

Jeśli istnieje następnik p, to jego poprzednikiem robimy poprzednik p. W przeciwnym razie p jest ostatnim elementem listy, dlatego w polu back umieszczamy adres jego poprzednika.

Zmniejszamy licznik i zwracamy adres p.

 
    TlistElement * index(unsigned n)
    {
      TlistElement * p;
      
      if((!n) || (n > counter)) return NULL;
      else if(n == counter) return back;
      else if(n < counter / 2)
      {
        p = front;
        while(--n) p = p->next;
        return p;
      }
      else
      {
        p = back;
        while(counter > n++) p = p->prev;
        return p;
      }  
    }
 Funkcja index(n) zwraca adres n-tego elementu listy. Elementy są numerowane od 1.

W porównaniu z funkcją index(n) klasy TsingleList dokonaliśmy drobnej modyfikacji wykorzystując własności listy dwukierunkowej. Otóż tutaj sprawdzamy dodatkowy warunek: w której połówce listy leży n-ty element. Jeśli w pierwszej, to dochodzimy do niego od początku listy wykonując maksymalnie n/2 operacji. Jeśli w drugiej, dochodzimy do niego od końca listy również wykonując maksymalnie n/2 operacji. Daje to oczywisty zysk czasowy dla elementów z drugiej połówki listy.

 
   void showKeys()
    {
      TlistElement * p;
      
      if(!front) cout << "Lista jest pusta." << endl;
      else
      {
        p = front;
        while(p)
        {
          cout << p->key << " ";
          p = p->next;
        }
        cout << endl;
      }
    }
};
 Funkcja showKeys() wyświetla klucze wszystkich elementów listy. Jest identyczna z funkcją showKeys() klasy TsingleList.

Podsumowanie funkcji składowych klasy TdoubleList

Funkcja krótki opis
size() Zwraca liczbę elementów przechowywanych na liście.
push_front(p) Umieszcza element p na początku listy i zwraca jego adres.
push_back(p) Umieszcza element p na końcu listy i zwraca jego adres.
insert(p1,p2) Dodaje element p1 za elementem p2 i zwraca adres p1.
pop_front() Pobiera element z początku listy.
pop_back() Pobiera element z końca listy.
erase(p) Usuwa z listy element p i zwraca adres usuniętego elementu.
index(n) Zwraca n-ty element listy. Elementy numerujemy od 1.
showKeys() Wyświetla kolejno klucze wszystkich elementów listy.

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2024 mgr Jerzy Wałaszek
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe