#include <iostream>
#include<string>
using namespace std;

class linkedList {
private:

    class node {
    public:
        string data;
        node *next;
        node *prev;

        node(string passedData) {
            data = passedData;
            next = NULL;
            prev = NULL;
        }
    };

    void display(node *p) {
        if (p->next != NULL) {
            cout << p->data << " ";
            display(p->next);
        } else {
            cout << p->data << endl;
        }
    }

    void insertAt(int location, string item, node *p) {
        if (location == 0) {
            node *baby = new node(item);
            (p->prev)->next = baby;
            baby->prev = p->prev;
            p->prev = baby;
            baby->next = p;
        } else {
            insertAt(location - 1, item, p->next);
        }
    }

    void remove(string item, node *p) {
        if (p->data == item) {
            if (tail == head && tail == p) {
                tail = NULL;
                head = NULL;
                delete p;
            } else if (head == p) {
                head = head->next;
                head->prev = NULL;
                delete p;
            } else if (tail == p) {
                tail = tail->prev;
                tail->next = NULL;
                delete p;
            } else {
                (p->next)->prev = p->prev;
                (p->prev)->next = p->next;
                delete p;
            }
        } else {
            p = p->next;
            remove(item, p);
        }
    }

    node *head;
    node *tail;
    int numItems;

public:
    linkedList() {
        head = NULL;
        tail = NULL;
        numItems = 0;
    }


    void display() {
        display(head);
    }

    void addBack(string item) {
        node *baby = new node(item);
        if (head == NULL) {
            head = baby;
            tail = baby;
        } else {
            tail->next = baby;
            baby->prev = tail;
            tail = baby;
        }

        numItems+=1;
    }

    void insertAt(int location, string item) {
        insertAt(location, item, head);
        numItems +=1;

    }

    void remove(string item) {
        if (head != NULL) {
            remove(item, head);
            numItems -=1;
        }
    }

    int size(){
        return numItems;
    }

    bool empty(){
        return numItems == 0;
    }

    bool contains(string item){
        bool flag = false;

        node * runner = head;

        while(runner!=NULL){
            if(runner->data == item){
                flag = true;
                break;
            }
            runner = runner->next;
        }

        return flag;
    }

};