Реализация на свързани списъци - класове, итератори,  операции.
    Ще напишем класове, подобни на стандартните list<string> и list<string>::iterator (вж 19. Въведение в структурите от данни).
// list2.cpp
#include <string>
#include <iostream>
#include <cassert>
using namespace std;

/* декларации на класовете List и Iterator за да могат да бъдат използвани при дефиниране на List*/
class List;
class Iterator;
/* елемент на свързания списък */
class Link {
public:
   Link(string);
private:
   string data;
   Link* previous;
   Link* next;
/* член-функциите на класовете List и Iterator имат достъп до частните членове на класа Link */
   friend class List;
   friend class Iterator;
};

class List {
public:
   List();
   void push_back(string);
   void insert(Iterator, string);
   void erase(Iterator);
   Iterator begin(); /* начало на свързания списък */
   Iterator end();   /* край на свързания списък */
private:
   Link* first;  /* първи елемент на свързания списък */
   Link* last;   /* последен елемент на свързания списък */
};

class Iterator {
public:
   Iterator();
   string get() const; /* реализира операция * за итератори */
   void next();        /* реализира операция ++ за итератори */
   void previous();    /* реализира операция -- за итератори */
   bool not_equal(Iterator) const; /* реализира операция != */
private:
   Link* position; /* текущ елемент на свързания списък */
   Link* last;     /* последен елемент на свързания списък */
/* член-функциите на класа List имат достъп до частните членове на Iterator */
   friend class List;
};

Link::Link(string s)
/* ПОЛУЧАВА: s - данната, която ще се съхранява в този елемент */
{ data = s;  previous = NULL;  next = NULL; }

List::List()
/* ЦЕЛ: конструира празен свързан списък */
{ first = NULL; last = NULL; }

void List::push_back(string s)
/* ЦЕЛ: добавя елемент към свързан спесък
   ПОЛУЧАВА: s - данната, която ще се добави
*/
{ Link* newlink = new Link(s);
  if (last == NULL)            /* празен свързан списък */
  { first = newlink; last = newlink; }
  else
  { newlink->previous = last;
    last->next = newlink;
    last = newlink;
  }
}

void List::insert(Iterator iter, string s)
/* ЦЕЛ: вмъква елемент в свързан спесък
   ПОЛУЧАВА: iter - позицията, преди която да се вмъкне
             s - данната, която ще се вмъкне
*/
{ if (iter.position == NULL) /* вмъкване в края */
  { push_back(s);  return;  }
  Link* after = iter.position;
  Link* before = after->previous;
  Link* newlink = new Link(s);
  newlink->previous = before;
  newlink->next = after;
  after->previous = newlink;
  if (before == NULL) first = newlink; /* вмъкване в началото */
  else         before->next = newlink;
}

void List::erase(Iterator iter)
/* ЦЕЛ: отстранява елемент от свързан спесък
   ПОЛУЧАВА: iter - позицията на елемента, който ще се отстрани
*/
{ assert(iter.position != NULL);
  Link* remove = iter.position;
  Link* before = remove->previous;
  Link* after = remove->next;
  if (remove == first) first = after;/* изтриване на първия елемент */
  else          before->next = after;
  if (remove == last)  last = before;/* изтриване на последния елемент */
  else      after->previous = before;
  iter.position = after;
  delete remove;
}

Iterator List::begin()
/* ВРЪЩА: итератор, сочещ към началната позиция на свързан списък */
{ Iterator iter;
  iter.position = first;
  iter.last = last;
  return iter;
}

Iterator List::end()
/* ВРЪЩА: итератор, сочещ след края на списъка (NULL) */
{ Iterator iter;
  iter.position = NULL;
  iter.last = last;
  return iter;
}

Iterator::Iterator()
{  position = NULL;   last = NULL;  }

string Iterator::get() const
/* ВРЪЩА: данната на елемента, който сочи итератора */
{ assert(position != NULL);
  return position->data;
}

void Iterator::next()
/* ЦЕЛ: да премести итератора на следващия елемент от списъка */
{ assert(position != NULL);
  position = position->next;
}

void Iterator::previous()
/* ЦЕЛ: да премести итератора на предишния елемент от списъка */
{ if (position == NULL)  position = last;
  else                   position = position->previous;
  assert(position != NULL);
}

bool Iterator::not_equal(Iterator b) const
/* ЦЕЛ: сравнява два итератора
   ПОЛУЧАВА: b - вторият итератор за сравнението
   ВРЪЩА: true ако този итератор и b не са равни
*/
{ return position != b.position; }

int main()
{ List staff;
  staff.push_back("Cracker, Carl");
  staff.push_back("Hacker, Harry");
  staff.push_back("Lam, Larry");
  staff.push_back("Sandman, Susan");

/* добавя елемент на четвърто място */
  Iterator pos;
  pos = staff.begin();
  pos.next();   pos.next();   pos.next();
  staff.insert(pos, "Reindeer, Rudolf");

/* отстранява втория елемент */
  pos = staff.begin();
  pos.next();
  staff.erase(pos);

/* отпечатва свързания списък */
  for (pos = staff.begin(); pos.not_equal(staff.end());
       pos.next()) cout << pos.get() << "\n";
  return 0;
}

Начално състояние на списъка:

След добавяне на елемент на четвърто място:

След отстраняване на втория елемент: