C++/List/your list
Your own list
<source lang="cpp">
- 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;
}
</source>