// Programm: list.C
// Doppelt verkettete Listen
#include
#include
#include
namespace ifet {
class ListElement {
public:
ListElement(int x, ListElement* p, ListElement* n);
int data;
friend class List;
friend std::ostream& operator<<(std::ostream& o, const List& l);
private:
ListElement* prev_;
ListElement* next_;
};
ListElement::ListElement(int x, ListElement* p, ListElement* n)
: data(x), prev_(p), next_(n)
{}
class List {
public:
List(); // POST: Initialisiert zu leerer Liste.
~List(); // POST: Alle Listenelemente geloescht.
private:
// Kopieren verboten!
List(const List&);
List& operator=(const List&);
public:
ListElement* begin();
ListElement* end();
const ListElement* begin() const;
const ListElement* end() const;
void insert(int x, ListElement* i);
// PRE: i ist aus [begin(),end())
// POST: fuege x vor i ein.
void erase(ListElement* i);
// PRE: i ist aus [begin(), end())
// POST: i aus Liste entfernt
private:
void destroy(ListElement* b, ListElement* e);
// POST: alle Elemente aus [b,e) wurden geloescht, der belegte
// Speicher wurde freigegeben.
ListElement sentinel;
};
List::List() : sentinel(0, 0, 0)
{
sentinel.next_ = &sentinel;
sentinel.prev_ = &sentinel;
}
List::~List() { destroy(begin(), end()); }
void List::destroy(ListElement* b, ListElement* e)
{
while (b != end()) {
ListElement* d = b;
b = b->next_;
delete d;
}
}
const ListElement* List::begin() const { return sentinel.next_; }
const ListElement* List::end() const { return &sentinel; }
ListElement* List::begin() { return sentinel.next_; }
ListElement* List::end() { return &sentinel; }
void List::insert(int x, ListElement* i)
// PRE: i ist aus [begin(),end())
// POST: fuege x vor i ein.
{
ListElement* n = new ListElement(x, i->prev_, i);
n->prev_->next_ = n;
n->next_->prev_ = n;
}
void List::erase(ListElement* i)
// PRE: i ist aus [begin(), end())
// POST: i aus Liste entfernt
{
i->prev_->next_ = i->next_;
i->next_->prev_ = i->prev_;
delete i;
}
std::ostream& operator<<(std::ostream& o, const List& l)
{
o << "(";
for (const ListElement* i = l.begin(); i != l.end(); i = i->next_)
o << i->data << ",";
return o << ")";
}
} // namespace ifet
int main()
{
ifet::List l;
l.insert(2, l.end());
l.insert(1, l.end());
std::cout << l << std::endl;
l.insert(1, l.end());
std::cout << l << std::endl;
return 0;
}
