Lista jednokierunkowa

Małgorzata Piekarska

Wstęp

Listy są ważnymi strukturami danych. Służą do reprezentacji między innymi grafów, stosów, kolejek. Dzięki swoim własnościom pozwalają na efektywne wykorzystanie pamięci oraz minimalizują czas usuwania i dodawania elementów.

Organizacja listy jednokierunkowej

Niech dana będzie definicja struktury o nazwie skladnik:

struct skladnik
{
  skladnik * next;
  typ_danych val;
};

Struktura skladnik zawiera dwa pola: pole val, które przechowuje dane (dowolnego typu) oraz pole wskaźnikowe next, które może przechować wskaźnik na taką samą strukturę skladnik.
Załóżmy, że w programie zadeklarowana została zmienna start typu wskaźnik na skladnik, czyli:

skladnik * start;
start=NULL;

Tak powstała pusta lista jednokierunkowa. Teraz możemy utworzyć dowolną strukturę skladnik i wpisać w pole val dowolną wartość, a jej adres przypisać zmiennej wskaźnikowej start:
skladnik * p = new skladnik;
p->val = v;    
start = p;

Ponieważ pole next struktury p może zawierać adres dowolnej struktury typu skladnik można utworzyć kolejną strukturę zapisując jej adres w polu next struktury p.
Powstająca w ten sposób struktura danych zawierająca (jak na razie) dwa skladniki, przy czym adres pierwszej zapamiętany jest w zmiennej wskaźnikowej start, a adres drugiej w polu next pierwszej struktury. Proces ten można powtórzyć po raz kolejny i kolejny itd..
Tak utworzoną strukturę nazywamy listą jednokierunkową (liniową).
Bardzo ważnym elementem listy jest pole next. Pamiętając adres pierwszego składnika listy mamy dostęp do wszystkich jej składników, musimy jednak zaznaczyć w którym miejscu lista się kończy. Koniec ten jest wyznaczany właśnie przez pole next. Ostatni składnik listy powinien mieć w polu next wartość NULL, podczas gdy wszystkie poprzednie składniki przechowują w tym polu adres składnika następnego.

Nazwa lista jednokierunkowa wynika ze sposobu łączenia poszczególnych składników listy: mając adres n-tego składnika można ustalić adres każdego ze składników o numerach n+1, n+2, n+3, itd., nie jest natomiast możliwe ustalenie adresu składnika wcześniejszego np. n-1.
Po takiej liście możemy zatem poruszać się tylko w jednym kierunku - od początku do końca listy, przejście w drugą stroną nie jest możliwe.

Podstawowe operacje wykonywane na liście jednokierunkowej

Poniższe przykłady zawierają definicje kilku podstawowych funkcji służących do zarządzania listą jednokierunkową. Za składnik listy przyjęto zdefiniowaną powyżej strukturę typu skladnik. Wskaźnik do początku listy start jest zmienną globalną.

Przykład 1

Zdefiniować funkcję LSize, której wartością będzie ilość składników listy.

unsigned LSize()
{ 
  skladnik * p;
  unsigned c = 0; // zerujemy licznik
  p = start;
  while(p)   // dopóki lista nie jest pusta
  { 
    c++;     // zwiększamy licznik o 1
    p = p->next; // p staje się kolejnym z listy 
  }
  return c;
}

Przykład 2

Zdefiniować funkcję LPushFront, która umożliwia dołączanie nowego elementu (z wartością typu int) na początku listy.

void LPushFront(int v)
{
  skladnik * p = new skladnik; 
  p->val = v;    
  p->next = start; 
  start = p;  // nowy początek listy
}

Przykład 3

Zdefiniować funkcję LPopFront, która umożliwia usunięcie elementu z początku listy.

void LPopFront()
{
  skladnik * p;
  p = start;   
  if(p!= NULL) // jeśli lista nie jest pusta
  {
    start = p->next; // nowy początek
    delete p;    // usuń element z pamięci
  }
}

Przykład 4

Zdefiniować funkcję LPushBack, która umożliwia dołączanie nowego elementu (wartość typu int) na końcu listy.

void LPushBack(int v)
{
  skladnik * p, * n;
  n = new skladnik;  // tworzymy nowy element
  n->next = NULL;   // będzie wyznaczał koniec listy
  n->val = v;       //I przechowywał podaną wartość
  p = start;
  if(p!=NULL) //jeśli lista nie jest pusta
  {
     while(p->next) p = p->next; //szukamy końca listy
     p->next = n; //wstawiamy na końcowy zamiast NULL
  }
  else start = n; //lista była pusta
}

Przykład 5

Zdefiniować funkcję LPopBack, która umożliwia usunięcie elementu z tyłu listy.

void LPopBack()
{
  skladnik * p = start;
  if(p!=NULL)
  {
    if(p->next) //usuwanie jeśli jest więcej elementów niż tylko startowy
    {
      while(p->next->next) p = p->next; // szukamy przedostatniego z listy
      delete p->next; //usuwamy ostatniego
      p->next = NULL; //oznaczamy nowy koniec listy
    }
    else //był na liście tylko startowy
    {
      delete p;  
      start = NULL; // lista staje się listą pustą
    }
  }
}

Przykład 6

Zdefiniować funkcję LPush, która umożliwia dodanie nowego elementu przed dowolnym innym (t).

void LPush(skladnik * t, int v)
{
  skladnik * p = start;

  if(p == t) LDodaj(start,v); //zwykłe dodawnie na początku
  else
  {
    while(p->next != t) p = p->next; //szukamy t
    p->next = new skladnik;
    p->next->next = t;
    p->next->val = v;
  }
}
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License