Lista (C++)
Poniższy artykuł przeznaczony jest przede wszystkim dla osób uczących się programować. Opisuje jedną z najważniejszych struktur danych, zwaną "listą". Artykuł przedstawia problem obrazując go przy pomocy języka C++.
Zakładam, że czytelnik opanował w stopniu bardzo dobrym składnię języka C++, oraz zna podstawowe zasady programowania obiektowego.
Czym jest lista
Najprościej można zdefiniować listę, jako pewien uszeregowany ciąg elementów, o dostępie sekwencyjnym. Oznacza to, że dane zawarte na liście można przeglądać tylko po kolei.
Zacznijmy od zdefiniowania struktury danych, pozwalającej zbudować listę. Na początek zbudujemy listę jednokierunkową, czyli taką, którą można przeglądać tylko w jednym kierunku.
class ElementType; // typ elementu na liście
class ElementListy{
protected:
ElementListy * m_pNext;
ElementType m_Value;
public:
ElementListy(){ m_pNext = NULL; }
~ElementListy();
inline ElementType GetValue(){ return m_Value; }
inline void SetValue(const ElementType& element){ m_Value = element; }
ElementListy * GetNext(){ return m_pNext; }
void SetNext(ElementListy *pNext){ m_pNext = pNext; }
(...)
};
Powyższy kod przedstawia bardzo prostą implementację
podstawowego elementu listy. Przeanalizujmy jego
budowę:
Będzie to lista składająca się z elementów typu
"ElemenetType". Równie dobrze mógłby to być oczywiście
int (liczba całkowita), czy łańcuch tekstowy. Wartość
tego elementu przechowywana jest w zmiennej "m_Value".
Jest to pierwsza z kluczowych wartości tej struktury
danych. Drugą jest zmienna "m_pNext". Jest to wskaźnik do
kolejnego elementu listy.
Ponieważ jeden rysunek jest zwykle łatwiejszy do zrozumienia niż 1000 słów opisu, proszę spojrzeć na schemat:
Powyższy schemat pokazuje sposób organizacji typowej listy jednokierunkowej. Zwykle w programie trzyma się dodatkowo wskaźniki do pierwszego (zwanego zwykle "head") oraz ostatniego ("tail") elementu listy. W przypadku pokazanym na przykładzie, przeglądanie listy odbywa się zwykle rozpoczynając od elementu "head". Może się to odbywać na przykład tak:
ElementListy * pCurr = pHead;
while(pCurr){
Wypisz( pCurr->GetValue() );
pCurr = pCurr->GetNext();
}
Należy zwrócić uwagę, że wskaźnik następnego elementu listy w ostatnim jej elemencie ustawiony jest na NULL. Jest to bardzo cenna informacja o końcu listy, pozwalająca przerwać przeglądanie. Czasami stosuje się jako taki ogranicznik dodatkowy, specjalny element nie zawierający wartości, a będący tylko informacją, że jest to koniec listy. W ten sposób zostało to zaimplementowane np. w bibliotece STL (Standard Template Library) języka C++, co pokażę w dalszej części tego tekstu.
Wstawianie nowego elementu do tak zorganizowanej listy jest bardzo prostą operacją.
void (...)::push_back(const ElementType& element)
{
ElementListy * pNewElem = new ElementListy;
pNewElem->SetValue(element);
m_pTail->SetNext(pNewElem);
m_pTail = pNewElem;
}
Należy jeszcze wziąść pod uwagę wstawianie pierwszego elementu do listy:
void (...)::push_back(const ElementType& element)
{
ElementListy * pNewElem = new ElementListy;
pNewElem->SetValue(element);
if(m_pHead == NULL) // to będzie pierwszy element na liście
m_pHead = pNewElem;
else
m_pTail->SetNext(pNewElem);
m_pTail = pNewElem;
}
Bardzo łatwo można także wstawić nowy element w środku listy:
void (...)::insert_after(ElementListy * pElement, const ElementType& element)
{
ElementListy * pNewElem = new ElementListy;
pNewElem->SetValue(element);
pNewElem->SetNext(pElement->GetNext());
pElement->SetNext(pNewElem);
if(pElement == m_pTail)
m_pTail = pNewElem;
}
Lista dwukierunkowa
Bardziej użyteczna i częściej stosowana jest lista
dwukierunkowa. Jest ona tylko odrobinę bardziej
skomplikowana w implementacji. Od przedstawionej powyżej
listy jednokierunkowej różni się tylko tym, że każdy
element listy zawiera wskaźniki zarówno do następnego,
jak i poprzedniego sąsiada.
Daje to możliwość przeglądania listy w obu kierunkach i
pozwala na znaczną optymalizację działających na niej
algorytmów.
Lista okrężna
Jest to rzadko używany, ale czasami przydatny rodzaj listy. Ostatni element takiej listy jest połączony z pierwszym tworząc koło. Lista okrężna może być zarówno jedno jak i dwukierunkowa.
Gotowa implementacja - STL
Samodzielna implementacja listy jest bardzo dobrym ćwiczeniem programistycznym. Uczy zwłaszcza panowania nad pamięcią, unikania powstawania wycieków, a także pozwala lepiej poznać zasadę działania tej struktury danych. Zwykle nie ma jednak potrzeby implementowania listy samodzielnie. Praktycznie każdy nowoczesny, obiektowy język programowania zawiera implementację listy. Lista zawarta jest także w Standardowej bibliotece C++ - STL. Została ona zaprojektowana w taki sposób, aby można było na niej przechowywać zarówno proste typy danych, takie jak int lub double jak również obiekty klas.
#include <list>
using namespace std;
typedef list<ElementType> mojalista;
mojalista lista;
(...)
// dodawanie nowego elementu na koniec listy
ElementType nowy_element1;
(...) // inicjalizacja elementu
lista.push_back(nowy_element1);
// dodawanie nowego elementu na początku listy
ElementType nowy_element2;
(...)
lista.push_front(nowy_element2);
// przeglądanie listy
mojalista::iterator it;
for(it = lista.begin() ; it != lista.end() ; ++it)
WypiszElement( *it );
// przeglądanie listy wspak
mojalista::reverse_iterator rit;
for(rit = lista.rbegin() ; rit != lista.rend() ; ++rit)
WypiszElement( *rit );
Gotowe implementacje zawierają zwykle wiele dodatkowych optymalizacji i są dobrze przetestowane, dlatego zwykle nie poleca się samodzielnej implementacji list.
Ćwiczenie
Nie ma innego sposobu aby nauczyć się dobrze programować niż nieustanne próby swoich sił. Własnoręczne zaprojektowanie i zaimplementowanie listy jest ważnym momentem w nauce programowania i pozwala wspiąć się na kolejny stopień wtajemniczenia. ;)
Zaprojektuj i zaimplementuj dwukierunkową listę, z operacjami wstawiania, usuwania i wyszukiwania elementów. Zrób to obiektowo. Zwróć uwagę na kapsułalizację. Zamknij całą implementację w jednym obiekcie, pozwalającym zarządzać całą listą bez znajomości szczegółów implementacyjnych.
