De standard C++ list

De klasse list<T>, gedefinieerd in namespace std en bibliotheek <list>, is een dubbelgelinkte lijst met elementen van het type T.

Intern wordt elk element opgeslagen in een knoop. Dit is een struct (klasse) met, behalve het dataveld, twee pointervelden: een wijzer naar zijn opvolger en een wijzer naar zijn voorganger (eventueel null aan het einde resp. begin van de lijst).

De lijst zelf is een object dat wijzers bijhoudt naar het eerste en laatste element. Dit zorgt ervoor dat er gemakkelijk en efficient vooraan en achteraan toegevoegd kan worden, met name met de lidfuncties push_back() resp. push_front().

Voorbeeld:

	#include <list>   // geen .h !!
	using namespace std;

	void main() {
		list<double> lst;		// leeg
		lst.push_back(2.0);
		lst.push_front(3.0);
	}

De grootte van wordt gegeven door de lidfunctie size(). Of dit in O(1) dan wel O(N) gebeurt hangt af van de implementatie (het kan namelijk zijn dat het lijstobject het aantal knopen expliciet bijhoudt). In elk geval kun je in O(1) d.m.v. empty() nagaan of de lijst leeg is.

iterator, range

Merk op dat men nooit rechtstreeks met de lijstknopen te maken heeft! Elk lijstoperatie gebeurt via het lijstobject zelf, ofwel via iteratoren die de elementen overlopen.

Het iteratortype voor list wordt binnen de list-klasse gedefinieerd. De volledige typenaam luidt dus std::list<T>::iterator. Omdat de notatie nogal zwaar is, gebruikt men vaak using en/of een typedef.

Om een reeks (range) elementen aan te duiden gebruikt men twee iteratoren: één begin-iterator naar het eerste element, en één end-iterator voorbij het laatste. Men kan dit voorstellen als een "gesloten-open" interval [begin,end[, vaak ook genoteerd als [begin, end).
Dit laatste heeft als voordeel dat ook een "lege range" kan voorgesteld worden, namelijk door (willekeurige) end==begin.

De klasse list voorziet de lidfuncties begin() en end() om een iteratorpaar te bekomen dat de volledige lijst omspant. De begin()-iterator wijst dus naar het eerste element van de lijst, de end()-operator voorbij het laatste element (in het geval van een lijst is dit waarschijnlijk de nulpointer, bij andere containers, zoals vector, niet)

Voorbeeld:

  #include <list>
  ...
  void print(list<double>& l) {
    list<double>::iterator b = l.begin(), e = l.end(), it;
    it = b;
    while (it != e) {
      cout << *it << endl;
      it++;
    }
  }

  #include <list>
  typedef std::list<double> dlist;
  ...
  void print(dlist& l) {
    for (dlist::iterator it = l.begin(); it != l.end(); it++)
      cout << *it << endl;
  }

Indien de lijst leeg is, wijzen begin() en end() naar dezelfde (onbepaalde) plaats (bv. null). Dit is belangrijk omdat bovenstaande code in dat geval geldig blijft (de "body" van de lus wordt geen enkele keer uitgevoerd)!

Opgelet: de copy-constructor kopieert alle elementen, een dure operatie dus. Geef dus nooit list-objecten "by value" door, altijd "by reference", zo mogelijk "by const reference".

Behalve iterator definieert list, net als elke standard container, ook een type const_iterator, dat gebruikt wordt om elementen te overlopen zonder ze te wijzigen. Het gebruik ervan is identiek.
Opm. men kan geen gewone (non-const) iterator verkrijgen van een const list&. Indien men in bovenstaande procedure het argument l const maakt (een belofte van de procedure om de lijst niet te wijzigen), dan is men ook verplicht const_iteratoren te gebruiken:

  void print(const dlist& l) {
    for (dlist::const_iterator it = l.begin(); it != l.end(); it++)
      cout << *it << endl;
  }

Zoeken, verwijderen, tussenvoegen

Merk op dat find() geen lidfunctie van list is: dezelfde routine kan gebruikt worden voor zoeken in vectoren en andere containers. Omdat de functie op een "range" werkt, kan men ook een deel van een container doorzoeken. Opgelet: zoeken gebeurt in O(N). In sommige datastructuren zoals een geordende lijst of een boom kan men sneller zoeken (bv. O(log(N)). In dat geval zal deze container een gespecialiseerde find() aanbieden als lidfunctie!

Voorbeeld. Om alle elementen vanaf de eerste 12.0 af te drukken:

  #include <list>
  #include <algorithm>
  using namespace std;
  ...
  dlist::iterator it = find(l.begin(), l.end(), 12.0);
  if (it == l.end)
    cout << "niet gevonden" << endl;
  else {
    while (it != l.end()) {
      cout << *it << endl;
      it++;
    }
  }

Toevoegen: l.insert(pos, x) voegt element x toe voor iterator pos

Verwijderen:

• l.erase(pos): verwijdert het element op positie pos
• l.erase(first, last): verwijdert de deelreeks [first, last)
• l.clear(): verwijdert alle elementen.

Voor- en nadelen

Indexering is inefficient: het i-de element kan enkel gevonden worden door al zijn voorgangers te overlopen, O(N) dus.

De standard vector kan wel efficient geindexeerd worden, en achteraan toevoegen heeft een performantie vergelijkbaar een met gelinkte lijst (geamortizeerd O(1)). Vooraan toevoegen of tussenvoegen is echter in het algemeen niet efficient. Vuistregel: vector is te verkiezen boven list, tenzij er frequent elementen tussengevoegd of verwijderd moet worden.

Enkel-gelinkte lijst

Voor sommige toepassingen is het niet nodig dat een lijst dubbelgelinkt is. Enkelgelinkte lijsten zijn iets sneller en gebruiken minder geheugen.

In STL kun je de klasse slist gebruiken voor enkelgelinkte lijsten. Opgelet: dit is een uitbreiding van de oorspronkelijke STL, en wordt niet door alle compilers ondersteund.

Meer informatie

Meer informatie op de website van SGI: