summaryrefslogtreecommitdiffstats
path: root/linkedlist.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'linkedlist.cpp')
-rw-r--r--linkedlist.cpp156
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();
+}
+