// linkedlist.cpp

#include <iostream>
#include <assert.h>
using namespace std;

class Node
{
  friend class List; // list can see value and next
private:
    int value;
    Node *next;
public:
    Node(int val); // make a new node containing val
    ~Node();
};

class List
{
private:
    Node *head;
public:
    List(); // creates an empty list
    ~List();
    void clear();
    void display();
    void insert(int val); // insert val in order into list
    void remove(int val); // remove val from list (if there)
    int size();
    bool contains(int val); // return true if val is in list
};

// Constructors

Node::Node(int val)
{
    value = val;
    next = NULL;
}

List::List()
{
    // set to the empty list
    head = NULL;
}

// Destructors

Node::~Node()
{
    if (next != NULL)
    {
        delete next;
        next = NULL;
    }
}

List::~List()
{
    if (head != NULL)
    {
        delete head;
        head = NULL;
    }
}

void List::clear()
{

}

void List::display()
{
    cout << "[ ";
    for (Node *p = head; p != NULL; p = p->next)
    {
        cout << p->value << " ";
    }
    cout << "]" << endl;
}

void List::insert(int val)
{
    // Note: referring to an attribute of the
    // NULL pointer causes a segmentation fault
    Node *p = head;
    Node *q = p; // q is a trailer
    while (p != NULL && p->value < val)
    {
        q = p;
        p = p->next;
    }
    Node *temp = new Node(val);
    if (p == q)
    {
        // i.e. inserting at head of list
        head = temp;
    }
    else
    {
        q->next = temp;
    }
    temp->next = p;
}

void List::remove(int val)
{
    Node *p = head;
    Node *q = p;
    while (p != NULL && p->value != val)
    {
        q = p;
        p = p->next;
    }
    if (p != NULL && p != q) // make sure val is in the list!
    {
        q->next = p->next;
        p->next = NULL;
        delete p;
    } 
    else if (p != NULL && p == q) // the first node is being removed!
    { 
        head = p->next;
        p->next = NULL;
        delete p;
    }
}

int List::size()
{
    int count = 0;
    for (Node *p = head; p != NULL; p = p->next)
    {
        count++;
    }
    return count;
}

bool List::contains(int val)
{

}

int main()
{
    List *list = new List();
    cout << "list size == " << list->size() << endl;
    list->insert(4);
    list->insert(5);
    list->insert(8);
    list->insert(3);
    list->insert(9);
    list->insert(1);
    list->display();
    cout << "list size == " << list->size() << endl;
    cout << "Removing 8..." << endl;
    list->remove(8);
    list->display();
    cout << "list size == " << list->size() << endl;
    cout << "Removing 6..." << endl;
    list->remove(6);
    list->display();
    cout << "list size == " << list->size() << endl;
    cout << "Removing 1..." << endl;
    list->remove(1);
    list->display();
    cout << "list size == " << list->size() << endl;
    cout << "Removing 9..." << endl;
    list->remove(9);
    list->display();
    cout << "list size == " << list->size() << endl;

    delete list;
}