#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_

#include "collection.h"
#include <string>
#include <sstream>

class LinkedList : public Collection
{
  private:
    class Node {
      public:
        Node() : v(-1), next(NULL), prev(NULL) {}
        int v;
        Node *next;
        Node *prev;
    };

  public:
    LinkedList();
    LinkedList(const LinkedList&);
    /* we can override the return type and still preserve dynamic binding! */
    LinkedList& operator=(const Collection&);
    ~LinkedList();

    virtual void add(int);
    virtual bool remove(int);
    virtual int operator[](const int);
    virtual LinkedList *copy(void);

    /* override these methods that had empty definitions in the interface */
    void iterate(void (*)(int *));
    bool contains(int) const;

    std::string print(void) const;

  protected:
  private:
    void print_helper(std::stringstream&, Node *) const;
    void cleanup(void);
    Node *head;
    Node *tail;
};

#endif