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();
+}
+