diff options
Diffstat (limited to 'linkedlist.cpp')
-rw-r--r-- | linkedlist.cpp | 156 |
1 files changed, 156 insertions, 0 deletions
diff --git a/linkedlist.cpp b/linkedlist.cpp new file mode 100644 index 0000000..9298521 --- /dev/null +++ b/linkedlist.cpp @@ -0,0 +1,156 @@ +#include "linkedlist.h" + +LinkedList::LinkedList() : Collection(), head(NULL), tail(NULL) +{ +} + +LinkedList::LinkedList(const LinkedList& list) : Collection(list), head(NULL), tail(NULL) +{ + Node *iter = list.tail; + while (iter) { + this->add(iter->v); + iter = iter->prev; + } +} + +LinkedList& LinkedList::operator=(const Collection& rhs) +{ + if (this == &rhs) + return *this; + + this->cleanup(); + this->size_ = 0; + + Node *iter = dynamic_cast<const LinkedList *>(&rhs)->head; /* it's ok g++ */ + while (iter) { + this->add(iter->v); + iter = iter->next; + } + + return *this; +} + +LinkedList::~LinkedList() +{ + this->cleanup(); +} + +void LinkedList::cleanup(void) +{ + Node *iter, *prev; + iter = prev = this->head; + while (iter) { + prev = iter; + iter = iter->next; + delete prev; + } +} + +void LinkedList::add(int n) +{ + Node *node = new Node(); + node->v = n; + node->next = this->head; /* link next */ + if (!this->head) /* first node */ + this->tail = node; /* this where tail gets assigned */ + else + this->head->prev = node; /* link prev */ + + this->head = node; + this->size_++; +} + +bool LinkedList::remove(int n) +{ + if (!this->head) + return false; + + if (this->head->v == n) { /* deleting first element or head */ + Node *first = this->head; + this->head = this->head->next; + if (this->get_size() == 1) + this->tail = NULL; /* tail gets nuked here */ + delete first; + return true; + } + else if (this->tail->v == n) { /* deleting last element or tail */ + Node *last = this->tail; + this->tail = this->tail->prev; + this->tail->next = NULL; + delete last; + return true; + } + + Node *iter = this->head; + while (iter) { + if (iter->v == n) { + iter->prev->next = iter->next; + delete iter; + this->size_--; + return true; + } + iter = iter->next; + } + + return false; +} + +/* assumes first element is at index of zero */ +int LinkedList::operator[](int i) +{ + /* invalid accesses */ + if (!this->size_ || i < 0 || i+1 > this->size_) + return -1; + + Node *iter = this->head; + int cnt = this->size_ - i - 1; + while (cnt--) { + iter = iter->next; + } + + return iter->v; +} + +LinkedList *LinkedList::copy(void) +{ + LinkedList *ret = new LinkedList(*this); + return ret; +} + +void LinkedList::iterate(void (*modifier)(int *)) +{ + Node *iter = this->head; + while (iter) { + modifier(&iter->v); /* missing smalltalk? No! */ + iter = iter->next; + } +} + +bool LinkedList::contains(int i) const +{ + Node *iter; + for (iter = this->head; iter != NULL && iter->v != i; iter = iter->next) + ; + + return iter ? true : false; +} + +void LinkedList::print_helper(std::stringstream& sstm, Node *n) const +{ + if (!n) + return; + + print_helper(sstm, n->next); + sstm << n->v << " "; +} + +/* does a recursive print since ll is inverted with respect to array */ +/* could just use tail and iterate through prev pointers */ +std::string LinkedList::print() const +{ + std::stringstream sstm; + print_helper(sstm, this->head); + + return sstm.str(); +} + |