Материал из C\C++ эксперт
Your own list
#include <string>
#include <iostream>
#include <cassert>
using namespace std;
class List;
class Iterator;
class Node
{
public:
Node(string s);
private:
string data;
Node* previous;
Node* next;
friend class List;
friend class Iterator;
};
class List
{
public:
List();
void push_back(string s);
void insert(Iterator iter, string s);
Iterator erase(Iterator i);
Iterator begin();
Iterator end();
private:
Node* first;
Node* last;
};
class Iterator
{
public:
Iterator();
string get() const;
void next();
void previous();
bool equals(Iterator b) const;
private:
Node* position;
Node* last;
friend class List;
};
Node::Node(string s)
{
data = s;
previous = NULL;
next = NULL;
}
List::List()
{
first = NULL;
last = NULL;
}
void List::push_back(string s)
{
Node* newnode = new Node(s);
if (last == NULL)
{
first = newnode;
last = newnode;
}
else
{
newnode->previous = last;
last->next = newnode;
last = newnode;
}
}
void List::insert(Iterator iter, string s)
{
if (iter.position == NULL)
{
push_back(s);
return;
}
Node* after = iter.position;
Node* before = after->previous;
Node* newnode = new Node(s);
newnode->previous = before;
newnode->next = after;
after->previous = newnode;
if (before == NULL)
first = newnode;
else
before->next = newnode;
}
Iterator List::erase(Iterator i)
{
Iterator iter = i;
assert(iter.position != NULL);
Node* remove = iter.position;
Node* before = remove->previous;
Node* 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;
return iter;
}
Iterator List::begin()
{
Iterator iter;
iter.position = first;
iter.last = last;
return iter;
}
Iterator List::end()
{
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::equals(Iterator b) const
{
return position == b.position;
}
int main()
{
List staff;
staff.push_back("A");
staff.push_back("B");
staff.push_back("C");
staff.push_back("D");
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.equals(staff.end()); pos.next())
cout << pos.get() << "\n";
return 0;
}
