170 lines
2.3 KiB
C++
170 lines
2.3 KiB
C++
#include <iostream>
|
|
using namespace std;
|
|
|
|
class Item {
|
|
public:
|
|
Item(int val) {
|
|
this->val = val;
|
|
this->prev = NULL;
|
|
this->next = NULL;
|
|
}
|
|
|
|
int val;
|
|
Item* prev;
|
|
Item* next;
|
|
};
|
|
|
|
class List {
|
|
private:
|
|
Item* first;
|
|
Item* last;
|
|
int _size;
|
|
public:
|
|
List() {
|
|
first = NULL;
|
|
last = NULL;
|
|
_size = 0;
|
|
}
|
|
void push_back(int val) {
|
|
_size++;
|
|
if(last == NULL) {
|
|
Item* i = new Item(val);
|
|
first = i;
|
|
last = i;
|
|
return;
|
|
}
|
|
|
|
Item* i = new Item(val);
|
|
last->next = i;
|
|
i->prev = last;
|
|
last = i;
|
|
}
|
|
Item* begin() {
|
|
return first;
|
|
}
|
|
Item* end() {
|
|
return last;
|
|
}
|
|
Item* find(int val) {
|
|
for(Item* i = begin(); i != NULL; i = i->next) {
|
|
if(i->val == val) {
|
|
return i;
|
|
}
|
|
}
|
|
return NULL;
|
|
}
|
|
bool erase(int pos) {
|
|
if(pos >= size()){
|
|
return false;
|
|
}
|
|
|
|
Item* i = begin();
|
|
for(int counter = 1; counter <= pos; counter++) {
|
|
i = i->next;
|
|
}
|
|
|
|
i->prev->next = i->next;
|
|
i->next->prev = i->prev;
|
|
|
|
delete i;
|
|
_size--;
|
|
return true;
|
|
}
|
|
int size() {
|
|
return _size;
|
|
}
|
|
bool swap(int pos) {
|
|
// swap pos with the next
|
|
if(pos >= size()-1){
|
|
return false;
|
|
}
|
|
|
|
Item* a = begin();
|
|
for(int counter = 1; counter <= pos; counter++) {
|
|
a = a->next;
|
|
}
|
|
Item* b = a->next;
|
|
|
|
Item* before = a->prev;
|
|
Item* after = b->next;
|
|
|
|
if(before) {
|
|
before->next = b;
|
|
}
|
|
else {
|
|
first = b;
|
|
}
|
|
|
|
a->next = after;
|
|
a->prev = b;
|
|
b->next = a;
|
|
b->prev = before;
|
|
|
|
if(after) {
|
|
after->prev = a;
|
|
}
|
|
else {
|
|
last = a;
|
|
}
|
|
|
|
return true;
|
|
}
|
|
};
|
|
|
|
void printList(List* v) {
|
|
for(Item* i = v->begin(); i; i = i->next) {
|
|
cout<<i->val<<" ";
|
|
}
|
|
cout<<endl;
|
|
}
|
|
|
|
void printListR(List* v) {
|
|
for(Item* i = v->end(); i; i = i->prev) {
|
|
cout<<i->val<<" ";
|
|
}
|
|
cout<<endl;
|
|
}
|
|
|
|
void test(List* v) {
|
|
cout<<"Forward: ";
|
|
printList(v);
|
|
cout<<"Reverse: ";
|
|
printListR(v);
|
|
}
|
|
|
|
int main() {
|
|
List v;
|
|
|
|
//test 1
|
|
cout<<"- Test 1\n";
|
|
v.push_back(10);
|
|
v.push_back(8);
|
|
v.push_back(37);
|
|
v.push_back(1);
|
|
v.push_back(0);
|
|
v.push_back(5);
|
|
test(&v);
|
|
|
|
//test 2
|
|
cout<<"- Test 2\n";
|
|
Item* x = v.find(8);
|
|
cout<<"Before: "<<x->prev->val<<" | Current: "<<x->val<<" | After: "<<x->next->val<<endl;
|
|
|
|
//test 3
|
|
cout<<"- Test 3\n";
|
|
v.erase(3);
|
|
test(&v);
|
|
|
|
//test 4
|
|
cout<<"- Test 4\n";
|
|
v.swap(2);
|
|
test(&v);
|
|
|
|
//test 5
|
|
cout<<"- Test 5\n";
|
|
v.swap(3);
|
|
test(&v);
|
|
|
|
return 0;
|
|
}
|