obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Listy

Podstawową zaletą tablic jest to, iż mamy szybki dostęp do każdego z elementów. Elementy tablicy są umieszczane jeden obok drugiego w spójnym bloku pamięci. Jeśli znamy adres początku tego bloku, indeks elementu oraz rozmiar elementu (liczbę zajętych komórek), to adres elementu tablicy oblicza się wg wzoru:

adres elementu = (adres obszaru) + indeks × (rozmiar elementu)

Tak właśnie wygląda w języku C++ dostęp do elementu za pomocą wskaźnika, który przechowuje adres początku tablicy w pamięci. Wskaźniki posiadają typy. Mówimy, że wskaźnik p jest wskaźnikiem np. na daną typu int. Ponieważ taka dana zajmuje w pamięci 4 bajty, to dodanie 1 do wskaźnika w rzeczywistości skutkuje dodaniem 4, gdyż musi on wskazywać następny obiekt typu int. Zatem arytmetyka wskaźników w języku C++ jest bardzo konsekwentna.

Tablice posiadają również wady. Jeśli chcemy wstawić jakiś element do tablicy, to musimy przestawiać inne elementy tablicy, aby zrobić w niej miejsce na nowy element. To kosztuje i spowalnia działanie algorytmów, które często muszą coś wstawiać lub usuwać ze zbioru danych.

Drugą wadą tablic jest to, iż wymagają one ciągłego obszaru pamięci na wszystkie dane. Jeśli komputer nie ma pod ręką tak dużego obszaru, to tablica nie zostanie utworzona - chociaż pamięć może być dostępna, lecz w kilku mniejszych kawałkach - np. w klasie vector dodanie elementu do tablicy może spowodować jej relokację w pamięci, jeśli w starym obszarze brak było już miejsca na dodatkowy element.

Aby rozwiązać te problemy, wymyślono dynamiczną strukturę danych, zwaną listą (ang. list). Lista jest ciągiem powiązanych ze sobą elementów. Z danego elementu listy można przejść do elementu następnego (następnika - ang. successor) lub do elementu poprzedniego (poprzednika - ang. predecessor). Każdy element listy posiada następującą strukturę:

struct list_elemenet
{
    list_element * succ;  // wskaźnik elementu następnego
    list_element * pred;  // wskaźnik elementu poprzedzającego
    typ  dane;            // dowolne dane, które są przechowywane w elemencie listy
};

Pierwszy element listy nazywamy głową (ang. head), a ostatni ogonem (ang. tail). Głowa listy nie ma poprzednika i jej pole pred zawiera wartość NULL. Ogon listy nie ma następnika i jego pole succ również zawiera wartość NULL.

obrazek

Taka lista nazywa się listą dwukierunkową (ang. doubly-linked list). Pozwala ona poruszać się po elementach listy w obu kierunkach. W przeciwieństwie do tablicy elementy listy nie posiadają indeksów i mogą znajdować się w różnych miejscach pamięci. Połączone są ze sobą za pomocą pól succ i pred, zawartych w każdym elemencie.

Jeśli pola pred są niewykorzystywane, to lista staje się listą jednokierunkową (ang. single-linked list). Po takiej liście można przesuwać się tylko w jednym kierunku:

obrazek

Prosta klasa listy dwukierunkowej

W ramach ćwiczeń zaprogramujemy prostą klasę listy dla liczb int. Klasa będzie przechowywała wewnętrznie trzy dane - wskaźnik głowy, wskaźnik ogona oraz liczbę elementów listy. Na początek wpiszmy program szablonowy, który następnie będziemy uzupełniać o kolejne elementy.

// Klasa listy int
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>

using namespace std;

// element listy
//--------------

struct list_el
{
    list_el * succ, * pred;
    int value;
};

// klasa listy
//------------

class list
{
  public:
    list();     // konstruktor
    int size();
    bool empty();

  private:
    list_el * head, * tail;
    int count;
};

// funkcje składowe klasy list
//----------------------------

// konstruktor
//------------
list::list()
{
    head = tail = NULL;
    count = 0;
    cout << "KONSTRUKTOR: PUSTA LISTA UTWORZONA" << endl << endl;
}

// zwraca liczbę elementów listy
//------------------------------

int list::size()
{
    return count;
}

// zwraca true, jeśli lista jest pusta
//------------------------------------

bool list::empty()
{
    return !count;
}


int main()
{
  list L;  // tworzymy pustą listę

  cout << L.size() << endl;

  return 0;
}

KONSTRUKTOR: PUSTA LISTA UTWORZONA

0

Program tworzy pustą listę - czyli taką, która nie zawiera żadnego elementu. Elementy możemy dodawać do listy na kilka sposobów - z przodu, z tyłu lub w środku. Zajmijmy się na początek dwoma pierwszymi przypadkami.

Dodanie elementu na koniec listy - push_back():

Najpierw przygotowujemy element do wstawienia na listę:

Tworzymy go dynamicznie
W polu value umieszczamy dane
W polu succ umieszczamy NULL, ponieważ ma to być ogon listy, zatem nie posiada on następnika
W polu pred umieszczamy adres obecnego ogona listy, pobrany z pola tail klasy list.

Element jest gotowy do umieszczenia na liście. Teraz musimy zmodyfikować listę, tak aby nowy element stał się jej ogonem. W tym celu wystarczy sprawdzić, czy istnieje ogon listy i, jeśli tak, to do jego pola succ należy wpisać adres wstawianego elementu.

Ostatnią czynnością jest odnotowanie w klasie faktu wstawienia na listę nowego elementu:

Zwiększamy o 1 licznik elementów count
Do pola tail wstawiamy adres dodanego elementu
Jeśli pole head jest puste (zawiera NULL), to przed wstawieniem ogona lista była pusta - należy zatem wpisać do tego pola adres dodanego elementu.

// Klasa listy int
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>

using namespace std;

// element listy
//--------------

struct list_el
{
    list_el * succ, * pred;
    int value;
};

// klasa listy
//------------

class list
{
  public:
    list();     // konstruktor
    ~list();    // destruktor
    int size();
    bool empty();
    void clear();
    void push_back(int v);
    void show();

  private:
    list_el * head, * tail;
    int count;
};

// funkcje składowe klasy list
//----------------------------

// konstruktor
//------------
list::list()
{
    head = tail = NULL;
    count = 0;
    cout << "KONSTRUKTOR: PUSTA LISTA UTWORZONA" << endl << endl;
}

// destruktor
//-----------

list::~list()
{
  clear(); // usuwamy listę z pamięci

  cout << endl << "DESTRUKTOR: LISTA ZNISZCZONA" << endl << endl;
}

// zwraca liczbę elementów listy
//------------------------------

int list::size()
{
    return count;
}

// zwraca true, jeśli lista jest pusta
//------------------------------------

bool list::empty()
{
    return !count;
}

// Wyświetla po kolei wszystkie elementy listy
// Zaznacza głowę i ogon listy
//--------------------------------------------

void list::show()
{
    list_el * p;

    for(p = head; p; p = p->succ)
    {
        if(p == head)      cout << "HEAD : ";
        else if(p -> succ) cout << "     : ";
        else               cout << "TAIL : ";

        cout << p -> value << endl;
    }
}

// Usuwa listę z pamięci
//----------------------

void list::clear()
{
  list_el * p;

  while(tail)               // dopóki lista coś zawiera
  {
     p = tail;              // bierzemy ogon
     tail = p -> pred;      // jako ogon ustawiamy poprzednik
     delete p;              // ogon usuwamy z pamięci
  }
  head = NULL;              // zerujemy głowę
  count = 0;                // zerujemy licznik
}

// Wstawia v na koniec listy
//--------------------------

void list::push_back(int v)
{
  // przygotowujemy element do wstawienia na listę

  list_el * e = new list_el;    // tworzymy dynamicznie nowy element
  e -> value = v;               // umieszczamy w nim dane
  e -> succ = NULL;             // ogon nie posiada następnika
  e -> pred = tail;             // poprzednikiem jest obecny ogon

  // modyfikujemy listę, aby zawierała wstawiany element

  if(tail) tail -> succ = e;    // dopisujemy element jako następnik ogona

  // modyfikujemy klasę po wstawieniu elementu

  count++;                      // zwiększamy licznik elementów
  tail = e;                     // nowy ogon to dodany element
  if(!head) head = e;           // jeśli lista była pusta, to element jest również głową
}


int main()
{
  list L;  // tworzymy pustą listę

  // dodajemy na koniec 10 kolejnych liczb

  for(int i = 1; i <= 10; i++) L.push_back(i);

  // wyświetlamy zawartość listy

  cout << "ROZMIAR LISTY : " << L.size() << endl << endl;

  L.show();

  return 0;
}

KONSTRUKTOR: PUSTA LISTA UTWORZONA

ROZMIAR LISTY : 10

HEAD : 1
     : 2
     : 3
     : 4
     : 5
     : 6
     : 7
     : 8
     : 9
TAIL : 10

DESTRUKTOR: LISTA ZNISZCZONA

Dodanie elementu na początek listy - push_front():

Najpierw przygotowujemy element do wstawienia na listę:

Tworzymy go dynamicznie
W polu value umieszczamy dane
W polu pred umieszczamy NULL, ponieważ ma to być głowa listy, zatem nie posiada on poprzednika
W polu succ umieszczamy adres obecnej głowy listy, pobrany z pola head klasy list.

Teraz musimy zmodyfikować listę, tak aby nowy element stał się jej ogonem. Sprawdzamy, czy istnieje głowa listy i, jeśli tak, to do jej pola pred należy wpisać adres wstawianego elementu.

Odnotowujemy w klasie fakt wstawienia na listę nowego elementu:

Zwiększamy o 1 licznik elementów count
Do pola head wstawiamy adres dodanego elementu
Jeśli pole tail jest puste (zawiera NULL), to przed wstawieniem głowy lista była pusta - należy zatem wpisać do tego pola adres dodanego elementu.

Zwróć uwagę, iż jest to dokładnie lustrzane odbicie operacji przy wstawianiu elementu na koniec listy. Wstawiane elementy będą później odczytywane w kierunku odwrotnym.

// Klasa listy int
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>

using namespace std;

// element listy
//--------------

struct list_el
{
    list_el * succ, * pred;
    int value;
};

// klasa listy
//------------

class list
{
  public:
    list();     // konstruktor
    ~list();    // destruktor
    int size();
    bool empty();
    void push_back(int v);
    void push_front(int v);
    void clear();
    void show();

  private:
    list_el * head, * tail;
    int count;
};

// funkcje składowe klasy list
//----------------------------

// konstruktor
//------------
list::list()
{
    head = tail = NULL;
    count = 0;
    cout << "KONSTRUKTOR: PUSTA LISTA UTWORZONA" << endl << endl;
}

// destruktor
//-----------

list::~list()
{
 
  clear(); // usuwamy listę z pamięci
  
  cout << endl << "DESTRUKTOR: LISTA ZNISZCZONA" << endl << endl;
}

// zwraca liczbę elementów listy
//------------------------------

int list::size()
{
    return count;
}

// zwraca true, jeśli lista jest pusta
//------------------------------------

bool list::empty()
{
    return !count;
}

// Wyświetla po kolei wszystkie elementy listy
// Zaznacza głowę i ogon listy
//--------------------------------------------

void list::show()
{
    list_el * p;

    for(p = head; p; p = p->succ)
    {
        if(p == head)      cout << "HEAD : ";
        else if(p -> succ) cout << "     : ";
        else               cout << "TAIL : ";

        cout << p -> value << endl;
    }
}

// Usuwa listę z pamięci
//----------------------

void list::clear()
{
  list_el * p;

  while(tail)               // dopóki lista coś zawiera
  {
     p = tail;              // bierzemy ogon
     tail = p -> pred;      // jako ogon ustawiamy poprzednik
     delete p;              // ogon usuwamy z pamięci
  }
  head = NULL;              // zerujemy głowę
  count = 0;                // zerujemy licznik
}

// Wstawia v na koniec listy
//--------------------------

void list::push_back(int v)
{
  // przygotowujemy element do wstawienia na listę

  list_el * e = new list_el;    // tworzymy dynamicznie nowy element
  e -> value = v;               // umieszczamy w nim dane
  e -> succ = NULL;             // ogon nie posiada następnika
  e -> pred = tail;             // poprzednikiem jest obecny ogon

  // modyfikujemy listę, aby zawierała wstawiany element

  if(tail) tail -> succ = e;    // dopisujemy element jako następnik ogona

  // modyfikujemy klasę po wstawieniu elementu

  count++;                      // zwiększamy licznik elementów
  tail = e;                     // nowy ogon to dodany element
  if(!head) head = e;           // jeśli lista była pusta, to element jest również głową
}

// Wstawia v na poczatek listy
//--------------------------

void list::push_front(int v)
{
  // przygotowujemy element do wstawienia na listę

  list_el * e = new list_el;    // tworzymy dynamicznie nowy element
  e -> value = v;               // umieszczamy w nim dane
  e -> pred = NULL;             // głowa nie posiada poprzednika
  e -> succ = head;             // następnikiem jest obecna głowa

  // modyfikujemy listę, aby zawierała wstawiany element

  if(head) head -> pred = e;    // dopisujemy element jako poprzednik obecnej głowy

  // modyfikujemy klasę po wstawieniu elementu

  count++;                      // zwiększamy licznik elementów
  head = e;                     // nowa głowa to dodany element
  if(!tail) tail = e;           // jeśli lista była pusta, to element jest również ogonem
}

int main()
{
  list L;  // tworzymy pustą listę

  // dodajemy na poczatek 10 kolejnych liczb

  for(int i = 1; i <= 10; i++) L.push_front(i);

  // wyświetlamy zawartość listy

  cout << "ROZMIAR LISTY : " << L.size() << endl << endl;

  L.show();

  return 0;
}

KONSTRUKTOR: PUSTA LISTA UTWORZONA

ROZMIAR LISTY : 10

HEAD : 10
     : 9
     : 8
     : 7
     : 6
     : 5
     : 4
     : 3
     : 2
TAIL : 1

DESTRUKTOR: LISTA ZNISZCZONA

Dodanie elementu w środku listy

Taka operacja wymaga wskaźnika p, który wskazuje miejsce wstawiania w liście. Umawiamy się, że nowy element zostanie wstawiony na listę przed elementem, który wskazuje wskaźnik. Operacja ta wygląda następująco:

Przygotowujemy element do wstawienia na listę

Tworzymy dynamicznie element listy
W polu value umieszczamy dane
W polu succ umieszczamy wartość wskaźnika p
W polu pred umieszczamy wartość pola pred elementu listy, który wskazuje wskaźnik p, czyli p->pred

Teraz musimy zmodyfikować samą listę, tak aby nowy element stał się jej częścią. W następniku nowego elementu zmieniamy pole pred na adres nowego elementu - następnik zawsze istnieje, ponieważ wskazuje go p.

Jeśli istnieje poprzednik nowego elementu (może nie istnieć, jeśli p wskazywał głowę listy), to ustawiamy jego pole succ na adres nowego elementu.

Na koniec należy zmodyfikować pola klasy:

zwiększamy licznik count o 1
Jeśli poprzednik nowego elementu nie istnieje, to wstawiony element jest głową listy. Zatem w polu head musimy umieścić jego adres.

// Klasa listy int
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>

using namespace std;

// element listy
//--------------

struct list_el
{
    list_el * succ, * pred;
    int value;
};

// klasa listy
//------------

class list
{
  public:
    list();     // konstruktor
    ~list();    // destruktor
    int size();
    bool empty();
    void push_back(int v);
    void push_front(int v);
    list_el * begin();
    void insert(list_el * p, int v);
    void clear();
    void show();

  private:
    list_el * head, * tail;
    int count;
};

// funkcje składowe klasy list
//----------------------------

// konstruktor
//------------
list::list()
{
    head = tail = NULL;
    count = 0;
    cout << "KONSTRUKTOR: PUSTA LISTA UTWORZONA" << endl << endl;
}

// destruktor
//-----------

list::~list()
{

  clear(); // usuwamy listę z pamięci

  cout << endl << "DESTRUKTOR: LISTA ZNISZCZONA" << endl << endl;
}

// zwraca liczbę elementów listy
//------------------------------

int list::size()
{
    return count;
}

// zwraca true, jeśli lista jest pusta
//------------------------------------

bool list::empty()
{
    return !count;
}

// Wyświetla po kolei wszystkie elementy listy
// Zaznacza głowę i ogon listy
//--------------------------------------------

void list::show()
{
    list_el * p;

    for(p = head; p; p = p->succ)
    {
        if(p == head)      cout << "HEAD : ";
        else if(p -> succ) cout << "     : ";
        else               cout << "TAIL : ";

        cout << p -> value << endl;
    }
}

// Usuwa listę z pamięci
//----------------------

void list::clear()
{
  list_el * p;

  while(tail)               // dopóki lista coś zawiera
  {
     p = tail;              // bierzemy ogon
     tail = p -> pred;      // jako ogon ustawiamy poprzednik
     delete p;              // ogon usuwamy z pamięci
  }
  head = NULL;              // zerujemy głowę
  count = 0;                // zerujemy licznik
}

// Wstawia v na koniec listy
//--------------------------

void list::push_back(int v)
{
  // przygotowujemy element do wstawienia na listę

  list_el * e = new list_el;    // tworzymy dynamicznie nowy element
  e -> value = v;               // umieszczamy w nim dane
  e -> succ = NULL;             // ogon nie posiada następnika
  e -> pred = tail;             // poprzednikiem jest obecny ogon

  // modyfikujemy listę, aby zawierała wstawiany element

  if(tail) tail -> succ = e;    // dopisujemy element jako następnik ogona

  // modyfikujemy klasę po wstawieniu elementu

  count++;                      // zwiększamy licznik elementów
  tail = e;                     // nowy ogon to dodany element
  if(!head) head = e;           // jeśli lista była pusta, to element jest również głową
}

// Wstawia v na poczatek listy
//--------------------------

void list::push_front(int v)
{
  // przygotowujemy element do wstawienia na listę

  list_el * e = new list_el;    // tworzymy dynamicznie nowy element
  e -> value = v;               // umieszczamy w nim dane
  e -> pred = NULL;             // głowa nie posiada poprzednika
  e -> succ = head;             // następnikiem jest obecna głowa

  // modyfikujemy listę, aby zawierała wstawiany element

  if(head) head -> pred = e;    // dopisujemy element jako poprzednik obecnej głowy

  // modyfikujemy klasę po wstawieniu elementu

  count++;                      // zwiększamy licznik elementów
  head = e;                     // nowa głowa to dodany element
  if(!tail) tail = e;           // jeśli lista była pusta, to element jest również ogonem
}

// Zwraca wskaźnik głowy listy
//----------------------------

list_el * list::begin()
{
    return head;
}

// wstawia v przed elementem wskazywanym przez p
//----------------------------------------------

void list::insert(list_el * p, int v)
{
    // przygotowujemy element do wstawienia na listę

    list_el * e = new list_el;   // tworzymy dynamicznie elemen listy
    e->value = v;                // umieszczamy w nim dane
    e->succ = p;                 // następnikiem będzie element wskazywany przez p
    e->pred = p->pred;           // poprzednikiem będzie poprzednik elementu wsk. przez p

    // modyfikujemy listę

    p->pred = e;                 // poprzednikiem el. wsk. przez p będzie nowy element
    if(e->pred)                  // jeśli istnieje poprzednik el. wsk. przez p
      e->pred->succ = e;         // to jego następnikiem będzie e

    // modyfikujemy klasę

    count++;                     // zwiększamy licznik elementów
    if(!(e->pred))               // jeśli e nie ma poprzednika
      head = e;                  // to jest głową listy
}

int main()
{
  list L;  // tworzymy pustą listę

  // dodajemy na koniec 10 kolejnych liczb

  for(int i = 1; i <= 10; i++) L.push_back(i);

  // wyświetlamy zawartość listy przed wstawieniem

  cout << "ROZMIAR LISTY : " << L.size() << endl << endl;

  L.show();

  // tworzymy wskaźnik elementów listy i ustawiamy go na głowę listy

  list_el * p = L.begin(); // p wskazuje 1-szy element listy

  p = p->succ;             // p wskazuje 2-gi element
  p = p->succ;             // p wskazuje 3-ci element

  // wstawiamy przed element wskazywany przez p 3 liczby:

  L.insert(p,100);
  L.insert(p,200);
  L.insert(p,300);

  // wyświetlamy zawartość listy po wstawieniu

  cout << "\nROZMIAR LISTY : " << L.size() << endl << endl;

  L.show();

  return 0;
}

KONSTRUKTOR: PUSTA LISTA UTWORZONA

ROZMIAR LISTY : 10

HEAD : 1
     : 2
     : 3
     : 4
     : 5
     : 6
     : 7
     : 8
     : 9
TAIL : 10

ROZMIAR LISTY : 13

HEAD : 1
     : 2
     : 100
     : 200
     : 300
     : 3
     : 4
     : 5
     : 6
     : 7
     : 8
     : 9
TAIL : 10

DESTRUKTOR: LISTA ZNISZCZONA

Usunięcie elementu z końca listy

Jeśli istnieje ogon listy, zapamiętujemy go za pomocą wskaźnika p. Inaczej kończymy.
Do pola tail wprowadzamy adres poprzednika, czyli tail->pred.
Jeśli poprzednikiem jest NULL, to usuwany element był jedynym elementem listy, zatem do pola head należy wpisać NULL. W przeciwnym razie w polu succ poprzednika umieszczamy NULL.
Zmniejszamy o jeden licznik elementów count.
Po tych operacjach zwalniamy pamięć przydzieloną elementowi, który wskazuje p.

Usunięcie elementu z początku listy

Jest to lustrzana kopia operacji usuwania z końca listy:

Jeśli istnieje głowa listy, zapamiętujemy ją we wskaźniku p. Inaczej kończymy.
Do pola head wprowadzamy adres następnika, czyli head->succ.
Jeśli następnikiem jest NULL, to zerujemy również pole tail, ponieważ usuwany element był jedynym na liście. Inaczej w polu pred następnika wpisujemy NULL.
Zmniejszamy o 1 count.
Na koniec zwalniamy pamięć przydzieloną elementowi wskazywanemu przez p.

Usunięcie dowolnego elementu listy

Usuwany element wskazuje wskaźnik p.

Jeśli p jest równe NULL, kończymy
Jeśli p jest równe head, usuwamy element z początku listy i kończymy
Jeśli p jest równe tail, usuwamy element z końca listy i kończymy
W polu succ poprzednika p umieszczamy adres następnika p.
W polu pred następnika p umieszczamy adres poprzednika p.
Zmniejszamy o 1 licznik count
Usuwamy z pamięci element wskazywany przez p.

// Klasa listy int
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>

using namespace std;

// element listy
//--------------

struct list_el
{
    list_el * succ, * pred;
    int value;
};

// klasa listy
//------------

class list
{
  public:
    list();     // konstruktor
    ~list();    // destruktor
    int size();
    bool empty();
    void push_back(int v);
    void push_front(int v);
    list_el * begin();
    void insert(list_el * p, int v);
    void pop_back();
    void pop_front();
    void erase(list_el * p);
    void clear();
    void show();

  private:
    list_el * head, * tail;
    int count;
};

// funkcje składowe klasy list
//----------------------------

// konstruktor
//------------
list::list()
{
    head = tail = NULL;
    count = 0;
    cout << "KONSTRUKTOR: PUSTA LISTA UTWORZONA" << endl << endl;
}

// destruktor
//-----------

list::~list()
{

  clear(); // usuwamy listę z pamięci

  cout << endl << "DESTRUKTOR: LISTA ZNISZCZONA" << endl << endl;
}

// zwraca liczbę elementów listy
//------------------------------

int list::size()
{
    return count;
}

// zwraca true, jeśli lista jest pusta
//------------------------------------

bool list::empty()
{
    return !count;
}

// Wyświetla po kolei wszystkie elementy listy
// Zaznacza głowę i ogon listy
//--------------------------------------------

void list::show()
{
    list_el * p;

    for(p = head; p; p = p->succ)
    {
        if(p == head)      cout << "HEAD : ";
        else if(p -> succ) cout << "     : ";
        else               cout << "TAIL : ";

        cout << p -> value << endl;
    }
}

// Usuwa listę z pamięci
//----------------------

void list::clear()
{
  list_el * p;

  while(tail)               // dopóki lista coś zawiera
  {
     p = tail;              // bierzemy ogon
     tail = p -> pred;      // jako ogon ustawiamy poprzednik
     delete p;              // ogon usuwamy z pamięci
  }
  head = NULL;              // zerujemy głowę
  count = 0;                // zerujemy licznik
}

// Wstawia v na koniec listy
//--------------------------

void list::push_back(int v)
{
  // przygotowujemy element do wstawienia na listę

  list_el * e = new list_el;    // tworzymy dynamicznie nowy element
  e -> value = v;               // umieszczamy w nim dane
  e -> succ = NULL;             // ogon nie posiada następnika
  e -> pred = tail;             // poprzednikiem jest obecny ogon

  // modyfikujemy listę, aby zawierała wstawiany element

  if(tail) tail -> succ = e;    // dopisujemy element jako następnik ogona

  // modyfikujemy klasę po wstawieniu elementu

  count++;                      // zwiększamy licznik elementów
  tail = e;                     // nowy ogon to dodany element
  if(!head) head = e;           // jeśli lista była pusta, to element jest również głową
}

// Wstawia v na poczatek listy
//--------------------------

void list::push_front(int v)
{
  // przygotowujemy element do wstawienia na listę

  list_el * e = new list_el;    // tworzymy dynamicznie nowy element
  e -> value = v;               // umieszczamy w nim dane
  e -> pred = NULL;             // głowa nie posiada poprzednika
  e -> succ = head;             // następnikiem jest obecna głowa

  // modyfikujemy listę, aby zawierała wstawiany element

  if(head) head -> pred = e;    // dopisujemy element jako poprzednik obecnej głowy

  // modyfikujemy klasę po wstawieniu elementu

  count++;                      // zwiększamy licznik elementów
  head = e;                     // nowa głowa to dodany element
  if(!tail) tail = e;           // jeśli lista była pusta, to element jest również ogonem
}

// Zwraca wskaźnik głowy listy
//----------------------------

list_el * list::begin()
{
    return head;
}

// wstawia v przed elementem wskazywanym przez p
//----------------------------------------------

void list::insert(list_el * p, int v)
{
    // przygotowujemy element do wstawienia na listę

    list_el * e = new list_el;   // tworzymy dynamicznie elemen listy
    e->value = v;                // umieszczamy w nim dane
    e->succ = p;                 // następnikiem będzie element wskazywany przez p
    e->pred = p->pred;           // poprzednikiem będzie poprzednik elementu wsk. przez p

    // modyfikujemy listę

    p->pred = e;                 // poprzednikiem el. wsk. przez p będzie nowy element
    if(e->pred)                  // jeśli istnieje poprzednik el. wsk. przez p
      e->pred->succ = e;         // to jego następnikiem będzie e

    // modyfikujemy klasę

    count++;                     // zwiększamy licznik elementów
    if(!(e->pred))               // jeśli e nie ma poprzednika
      head = e;                  // to jest głową listy
}

// usuwa element z końca listy
//----------------------------

void list::pop_back()
{
  list_el * p = tail;            // zapamiętujemy ogon

  if(p)                          // jeśli lista zawiera jakiś element
  {
      tail = tail->pred;         // za nowy ogon przyjmujemy poprzednik
      if(!tail) head = NULL;     // jeśli brak poprzednika, to zerujemy również głowę
      else tail->succ = NULL;    // poprzednik staje się ogonem listy
      count--;                   // w liczniku o jeden element mniej
      delete p;                  // zwalniamy pamięć elementu
  }
}

// usuwa element z początku listy
//-------------------------------

void list::pop_front()
{
  list_el * p = head;            // zapamiętujemy głowę

  if(p)                          // jeśli lista zawiera jakiś element
  {
      head = head->succ;         // za nową głowę przyjmujemy następnik
      if(!head) tail = NULL;     // jeśli brak następnika, to zerujemy również ogon
      else head->pred = NULL;    // inaczej następnik staje się głową listy
      count--;                   // zmniejszamy o 1 licznik elementów
      delete p;                  // usuwamy element z pamięci
  }
}

// usuwa z listy element wskazywany przez p
//-----------------------------------------

void list::erase(list_el * p)
{
  if(p)                           // jeśli p wskazuje element
  {
      if(p == head) pop_front();  // jeśli jest to głowa, usuwamy głowę
      if(p == tail) pop_back();   // jeśli jest to ogon, usuwamy ogon
      p->pred->succ = p->succ;    // wyłączamy element z listy
      p->succ->pred = p->pred;
      count--;                    // zmniejszamy licznik o 1
      delete p;                   // usuwamy element z pamięci
  }
}

int main()
{
  list L;  // tworzymy pustą listę

  // dodajemy na koniec 10 kolejnych liczb

  for(int i = 1; i <= 10; i++) L.push_back(i);

  // wyświetlamy zawartość listy przed usuwaniem

  cout << "ROZMIAR LISTY : " << L.size() << endl << endl;

  L.show();

  L.pop_front();       // usuwamy pierwszy element
  L.pop_back();        // oraz dwa ostatnie elementy
  L.pop_back();

  // wyświetlamy zawartość listy po pierwszym usuwaniu

  cout << "\nROZMIAR LISTY : " << L.size() << endl << endl;

  L.show();

  list_el * p = L.begin(); // p wskazuje 1-szy element listy
  p = p->succ;             // p wskazuje 2-gi element
  p = p->succ;             // p wskazuje 3-ci element

  L.erase(p);              // usuwamy trzeci element z listy

  // wyświetlamy zawartość listy po drugim usuwaniu

  cout << "\nROZMIAR LISTY : " << L.size() << endl << endl;

  L.show();

  return 0;
}

KONSTRUKTOR: PUSTA LISTA UTWORZONA

ROZMIAR LISTY : 10

HEAD : 1
     : 2
     : 3
     : 4
     : 5
     : 6
     : 7
     : 8
     : 9
TAIL : 10

ROZMIAR LISTY : 7

HEAD : 2
     : 3
     : 4
     : 5
     : 6
     : 7
TAIL : 8

ROZMIAR LISTY : 6

HEAD : 2
     : 3
     : 5
     : 6
     : 7
TAIL : 8

DESTRUKTOR: LISTA ZNISZCZONA

Klasa szablonowa list

Biblioteka STL udostępnia programiście klasę kontenerów, która obsługuje listy dwukierunkowe. Z klasą list postępujemy bardzo podobnie jak z omawianą na poprzednich zajęciach klasą vector. Również funkcje składowe są bardzo podobne - dzięki temu nie będziemy musieli się wszystkiego uczyć od nowa. Zastosowanie obiektu list znakomicie ułatwia programowanie z wykorzystaniem list. Dostęp do klasy szablonowej list mamy po dołączeniu do programu pliku nagłówkowego list:

#include <list>

Tworzenie nowej listy

Podobnie jak dla w przypadku klasy vector, klasa list zawiera cztery konstruktory, które pozwalają w różny sposób tworzyć nową listę:

list<typ> lista;             // tworzy pustą listę

list<typ> lista(n,v);        // tworzy listę zbudowaną z n elementów o wartości v

list<typ> lista(inna_lista); // tworzy kopię innej listy

list<typ> lista(it1, it2);   // tworzy listę z kopią elementów z innej listy.
                             // Iterator it1 wskazuje pierwszy element do skopiowania
                             // Iterator it2 wskazuje poza ostatni element do skopiowania

Iteratory list tworzymy podobnie jak iteratory tablic:

list<typ>::iterator nazwa;

Dla iteratorów list dostępne są następujące operacje:

it = lista.begin();   // ustawiamy iterator it na pierwszy element listy

it = lista.end();     // ustawia iterator it poza ostatni element listy

it++ lub ++it         // przesuwa iterator it na następny element na liście

it-- lub --it         // przesuwa iterator it na element poprzedni na liście

* it                  // daje dostęp do przechowywanych danych w elemencie listy

// Klasa szablonowa list
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>
#include <list>

using namespace std;

int main()
{
  // tworzymy pustą listę

  list<double> list_1;

  // tworzymy listę 10 liczb pi

  list<double> list_2(10,3.14159265);

  // podwajamy drugi element

  list<double>::iterator it = list_2.begin();
  it++;
  *it *= 2;

  // tworzymy kopię listy_2

  list<double> list_3(list_2);

  // tworzymy kopię 6 początkowych elementów listy_3

  it = list_3.begin();
  for(int i = 1; i <= 6; i++) it++;

  list<double> list_4(list_3.begin(), it);

  // wyświetlamy listy

  cout << "\nlist_1:" << endl;

  for(it = list_1.begin(); it != list_1.end(); it++)
    cout << * it << endl;

  cout << "\nlist_2:" << endl;

  for(it = list_2.begin(); it != list_2.end(); it++)
    cout << * it << endl;

    cout << "\nlist_3:" << endl;

  for(it = list_3.begin(); it != list_3.end(); it++)
    cout << * it << endl;

    cout << "\nlist_4:" << endl;

  for(it = list_4.begin(); it != list_4.end(); it++)
    cout << * it << endl;

return 0;
}

list_1:

list_2:
3.14159
6.28319
3.14159
3.14159
3.14159
3.14159
3.14159
3.14159
3.14159
3.14159

list_3:
3.14159
6.28319
3.14159
3.14159
3.14159
3.14159
3.14159
3.14159
3.14159
3.14159

list_4:
3.14159
6.28319
3.14159
3.14159
3.14159
3.14159

Wstawianie danych na listę

Dane możemy umieszczać na liście na kilka sposobów.

lista.push_back(v);          // dopisuje v na końcu listy

lista.push_front(v);         // dopisuje v na początku listy

lista.front();               // odwołanie do pierwszego elementu listy

lista.back();                // odwołanie do ostatniego elementu listy

lista.insert(it,v);          // wstawienie v przed elementem wskazywanym przez iterator it

lista.insert(it,n,v);        // wstawienie przed element wskazywany przez it n elementów o wartości v

lista.insert(it1, it2, it3); // wstawienie przed element it1 ciągu elementów innej listy od it2 do
                             // elementu poprzedzającego it3

lista.size();                // zwraca liczbę elementów przechowywanych przez listę

lista.empty();               // zwraca true, jeśli lista jest pusta

// Klasa szablonowa list
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>
#include <list>

using namespace std;

int main()
{
  // tworzymy pustą listę

  list<int> lista;
  int i;
  list<int>::iterator it1,it2,it3;

  // wprowadzamy 5 kolejnych liczb na koniec listy

  for(i = 1; i <= 5; i++) lista.push_back(i);

  // wyświetlamy listę

  for(it1 = lista.begin(); it1 != lista.end(); it1++)
    cout << *it1 << endl;

  cout << "-----------------" << endl;

  // wprowadzamy 5 następnych liczb na początek listy

  for(i = 10; i <= 15; i++) lista.push_front(i);

  // wyświetlamy listę

  for(it1 = lista.begin(); it1 != lista.end(); it1++)
    cout << *it1 << endl;

  cout << "-----------------" << endl;

  // pierwszy i ostatni element mnożymy przez 10

  lista.front() *= 10;
  lista.back() *= 10;

  // wyświetlamy listę

  for(it1 = lista.begin(); it1 != lista.end(); it1++)
    cout << *it1 << endl;

  cout << "-----------------" << endl;

  // przed piatym elementem wstawiamy 999

  it1 = lista.begin();
  for(i = 0; i < 5; i++) it1++;  // przesuwamy iterator na 5-ty element
  lista.insert(it1,999);

  // wyświetlamy listę

  for(it1 = lista.begin(); it1 != lista.end(); it1++)
    cout << *it1 << endl;

  cout << "-----------------" << endl;

  // przed 3-cim elementem wstawiamy trzy liczby 1000

  it1 = lista.begin();
  it1++;  // 2-gi element
  it1++;  // 3-ci element
  lista.insert(it1,3,1000);

  // wyświetlamy listę

  for(it1 = lista.begin(); it1 != lista.end(); it1++)
    cout << *it1 << endl;

  cout << "-----------------" << endl;

  // tworzymy nową listę z 5 liczbami 1

  list<int> lista2(5,1);

  // na przed drugim elementem wstawiamy listę bez pierwszego i ostatniego elementu

  it1 = lista2.begin();
  it1++;  // 2-gi element

  it2 = lista.begin();
  it2++;
  it3 = lista.end();
  it3--;

  lista2.insert(it1,it2,it3);

  // wyświetlamy listę nr 2

  for(it1 = lista2.begin(); it1 != lista2.end(); it1++)
    cout << *it1 << endl;

  cout << "-----------------" << endl;

  return 0;
}

1
2
3
4
5
-----------------
15
14
13
12
11
10
1
2
3
4
5
-----------------
150
14
13
12
11
10
1
2
3
4
50
-----------------
150
14
13
12
11
999
10
1
2
3
4
50
-----------------
150
14
1000
1000
1000
13
12
11
999
10
1
2
3
4
50
-----------------
1
14
1000
1000
1000
13
12
11
999
10
1
2
3
4
1
1
1
1
-----------------

Usuwanie danych z listy

Dane można usuwać z list na wiele różnych sposobów:

lista.clear();         // usuwa wszystkie elementy listy

lista.pop_back();      // usuwa ostatni element listy

lista.pop_front();     // usuwa pierwszy element listy

lista.erase(it);       // usuwa element wskazany przez iterator it

lista.erase(it1, it2); // usuwa elementy od it1 do poprzedzającego it2

lista.remove(v);       // usuwa wszystkie elementy o wartości v

// Klasa szablonowa list
//-------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//---------------------------

#include <iostream>
#include <list>

using namespace std;

int main()
{
  list<int> L;
  int i;
  list<int>::iterator it1,it2;

  // wypełniamy listę kolejnymi liczbami od 1 do 9

  for(i = 1; i < 10; i++) L.push_back(i);

  // wyświetlamy listę

  for(it1 = L.begin(); it1 != L.end(); it1++)
    cout << *it1 << endl;
  cout << endl;

  // usuwamy pierwszy i ostatni element

  L.pop_front();
  L.pop_back();

  // wyświetlamy listę

  for(it1 = L.begin(); it1 != L.end(); it1++)
    cout << *it1 << endl;
  cout << endl;

  // usuwamy 2-gi element

  it1 = L.begin();
  it1++;
  L.erase(it1);

  // wyświetlamy listę

  for(it1 = L.begin(); it1 != L.end(); it1++)
    cout << *it1 << endl;
  cout << endl;

  // usuwamy środkowe elementy, za wyjatkiem pierwszego i ostatniego

  it1 = L.begin();
  it1++;
  it2 = L.end();
  it2--;
  L.erase(it1,it2);

  // wyświetlamy listę

  for(it1 = L.begin(); it1 != L.end(); it1++)
    cout << *it1 << endl;
  cout << endl;

  // na poczatek i na koniec listy dodajemy po 5 liczb 999

  for(i = 1; i <= 5; i++)
  {
      L.push_front(999);
      L.push_back(999);
  }

  // wyświetlamy listę

  for(it1 = L.begin(); it1 != L.end(); it1++)
    cout << *it1 << endl;
  cout << endl;

  // usuwamy z listy wszystkie elementy o wartości 999

  L.remove(999);

  // wyświetlamy listę

  for(it1 = L.begin(); it1 != L.end(); it1++)
    cout << *it1 << endl;
  cout << endl;

  return 0;
}

1
2
3
4
5
6
7
8
9

2
3
4
5
6
7
8

2
4
5
6
7
8

2
8

999
999
999
999
999
2
8
999
999
999
999
999

2
8

Podsumowanie

Poniższe podsumowanie nie jest kompletne - zawiera jedynie najpopularniejsze funkcje dla klasy list. Więcej znajdziesz w literaturze.

Tworzenie listy
list <typ> lista;	pusta lista
list<typ> lista(n , v);	lista o n elementach, każdy o wartości v
list<typ> lista(inna_lista);	kopia innej listy o takiej samej zawartości
list<typ> lista(it₁, it₂);	kopia fragmentu innej listy. it₁ - iterator wskazujący pierwszy element do skopiowania it₂ - iterator wskazujący poza ostatni element do skopiowania
Tworzenie zmiennej typu iterator
list<typ> :: iterator nazwa;
Dostęp do elementów listy
* iterator	wskazuje dane przechowywane przez kontener
lista.front()	odwołanie do pierwszego elementu
lista.back()	odwołanie do ostatniego elementu
Rozmiar listy
lista.size()	zwraca liczbę elementów przechowywanych na liście
lista.empty()	jeśli lista nie przechowuje żadnego elementu, zwraca true. Inaczej zwraca false.
lista.max_size()	zwraca maksymalny rozmiar listy - czyli liczbę elementów, którą lista może przechować
Funkcje związane z iteratorami
lista.begin()	zwraca iterator do pierwszego elementu listy
lista.end()	zwraca iterator poza ostatni element na liście. Iterator ten nie wskazuje żadnego elementu.
Wstawianie danych do listy
lista.push_back(v)	dopisuje wartość v na końcu listy.
lista.push_front(v)	wstawia wartość v na początek listy.
lista.insert(it,v)	wstawia na pozycję iteratora it wartość v.
lista.insert(it, n, v)	wstawia od pozycji iteratora it n wartości v.
lista.insert(it₁, it₂, it₃)	wstawia na pozycji iteratora it₁ fragment innej listy, zdefiniowany przez iteratory it₂ i it₃: it₂ - wskazuje pierwszy element do wstawienia it₃ - wskazuje poza ostatni element do wstawienia
Usuwanie danych z listy
lista.clear()	usuwa z listy wszystkie elementy. Lista staje się pusta
lista.pop_back()	usuwa z listy ostatni element.
lista.pop_front()	usuwa z listy pierwszy element.
lista.erase(it)	usuwa element wskazywany przez iterator it.
lista.erase(it₁, it₂)	usuwa ciąg kolejnych elementów. it₁ - wskazuje pierwszy element do usunięcia w tym ciągu. it₂ - wskazuje poza ostatni element do usunięcia.
lista.remove(v)	usuwa z listy wszystkie elementy o wartości v
lista.unique()	usuwa duplikaty elementów z listy. Rozważane są elementy leżące obok siebie na liście.
Wymiana zawartości list
lista₁.swap(lista₂)	wymienia zawartość listy₁ z listą₂. Iteratory pozostają ważne.
Pozostałe funkcje składowe
lista.resize(n)	zmienia rozmiar listy na n komórek. Jeśli lista posiadała wcześniej większy rozmiar, to elementy ponad n są usuwane. Jeśli rozmiar był mniejszy, to na końcu listy zostają wstawione puste elementy do osiągnięcia rozmiaru n.
lista.resize(n,v)	działa jak powyżej, dodatkowe elementy są inicjowane na wartość v.
lista.assign(n,v)	pozwala przypisać liście nową zawartość. Stara zawartość jest usuwana, a na jej miejsce powstaje n elementów o wartości v.
lista.assign(it₁, it₂)	usuwa bieżącą zawartość listy i na jej miejsce kopiuje fragment innej listy zdefiniowany przez iteratory: it₁ - wskazuje pierwszy element do skopiowania it₂ - wskazuje poza ostatni element do skopiowania
lista.sort()	sortuje rosnąco elementy listy

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