/*
 * LinkedList is an example of a second implementation of a basic data structure.
 * A LinkedList is a sequential collection of integers stored with 0-based integer
 * indexes and internally represented as a list of linked node structures.
 */

#ifndef _linkedlist_h
#define _linkedlist_h

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

/* The internal structure representing a single node */
struct ListNode {
    int data;         // element stored in each node
    ListNode* next;   // pointer to the next node (nullptr if none)
    
    ListNode(int d, ListNode* n) {
        data = d;
        next = n;
    }
};

class LinkedList {
public:
    /*
     * Constructs a new empty list.
     */
    LinkedList();

    /*
     * This destructor frees the memory that was allocated internally by the list.
     */
    ~LinkedList();

    /*
     * Appends the given value to the end of the list.
     */
    void add(int value);

    /*
     * Removes all values from the list.
     */
    void clear();

    /*
     * Returns the value at the given 0-based index of the list.
     */
    int get(int index) const;

    /*
     * Adds the given value just before the given 0-based index in the list.
     */
    void insert(int index, int value);

    /*
     * Returns true if there are no elements in the list.
     */
    bool isEmpty() const;

    /*
     * Removes the element at the given 0-based index from the list.
     */
    void remove(int index);

    /*
     * Stores the given value at the given 0-based index in the list.
     */
    void set(int index, int value);

    /*
     * Returns the number of elements in the list.
     */
    int size() const;

    /*
     * Returns a string representation of the list such as "[42, 3, 17]".
     */
    string toString() const;

private:
    ListNode* m_front = nullptr;   // pointer to front node in list;  nullptr if empty

    /*
     * This helper throws an out_of_range exception if the given index is not between
     * the given min/max indexes, inclusive.
     */
    void checkIndex(int index, int min, int max) const;
};

#endif