import java.util.IndexOutOfBoundsException;

/**
 * A very basic list class.  Elements can only be added at the beginning at
 * the beginning of the list, and can only be removed according to their
 * index.
 *
 * @author Nathan Sprague (April 2010)
 * @author Alyce Brady (most recently in September 2025)
 * @author Your Name
 * @version The Date
 */
public class K_SimpleLL<T>
{
    private K_LLNode<T> first;
    private int size;

    /**
     * Create an empty list.
     */
    public K_SimpleLL()
    {
        this.first = null;
        this.size = 0;
    }

    /**
     * Returns the number of elements in the list.
     */
    public int size()
    {
        return this.size;
    }

    /** Returns <code>true</code> if this list contains no elements;
     *  <code>false</code> otherwise.
     **/
    public boolean isEmpty()
    {
        // YOU NEED TO ADD CODE HERE!
    }

    /**
     * Adds a new element AT THE BEGINNING of the list. 
     * @param element - The element to add
     */
    public void addFirst(T element) 
    {
        // YOU NEED TO ADD CODE HERE!
    }

    /**
     * Adds a new element AT THE END of the list. 
     * @param element - The element to add
     */
    public void addLast(T element) 
    {
        // YOU NEED TO ADD CODE HERE!
    }

    /**
     * Returns the element at the specified index. Throws
     * an IndexOutOfBoundsException if the index is out of bounds.
     *  
     * @param index - position of the element to get
     * @return the element at the specified index
     * @throws IndexOutOfBoundsException
     */
    public T get(int index) throws IndexOutOfBoundsException
    {
        // Make sure index is not out of range.
        if ( index < 0 || index >= this.size )
        {
            throw new IndexOutOfBoundsException("There is no element at index "
                    + index);
        }

        // Traverse the list until the current node is the one we want.
        K_LLNode<T> curNode = this.first;
        for ( int curIndex = 0; curIndex < index; curIndex++ )
        {
            curNode = curNode.getNext();
        }

        // Return the element at the current node.
        return curNode.getElement();
    }

    /**
     * Replaces the element at the specified position in this list with the
     * specified element. Throws an IndexOutOfBoundsException if the index
     * is out of bounds.
     *  
     * @param index - position of the element to replace
     * @return element to be stored at the specified position
     * @throws IndexOutOfBoundsException
     */
    public T set(int index, T element) throws IndexOutOfBoundsException
    {
        // YOU NEED TO ADD CODE HERE!
    }

    /**
     * Removes and returns the element at the specified index. Throws
     * an IndexOutOfBoundsException if the index is out of bounds.
     *  
     * @param index - position of the element to remove
     * @return the element that was removed
     * @throws IndexOutOfBoundsException
     */
    public T remove(int index) throws IndexOutOfBoundsException
    {
        // Make sure index is not out of range.
        if ( index < 0 || index >= this.size )
        {
            throw new IndexOutOfBoundsException("There is no element at index "
                    + index);
        }

        // Go ahead and reduce size now, before any return statements.
        this.size--;

        // Removing the first one is a special case.
        if ( index == 0 )
        {
            T eltToRemove = first.getElement();
            first = first.getNext();
            return eltToRemove;
        }

        // Traverse the list until the curNode is the one BEFORE the one
        // we want to remove, i.e., the one at (index - 1).
        K_LLNode<T> curNode = first;
        for ( int curIndex = 0; curIndex < index - 1; curIndex++ )
        {
            curNode = curNode.getNext();
        }

        // curIndex = index - 1, so
        // curNode is the one BEFORE the one we want to remove.
        K_LLNode<T> nodeToRemove = curNode.getNext();
        T eltToRemove = nodeToRemove.getElement();
        curNode.setNext(nodeToRemove.getNext());
        return eltToRemove;
    }

    /** {@inheritDoc}
     */
    @Override
    public String toString()
    {
        String s = "[";

        // If the list is not empty, add elements to s.
        if ( this.size != 0 )
        {
            // Add all but the last element followed by a comma.
            K_LLNode<T> node;
            for( node = first; node.getNext() != null; node = node.getNext() )
            {
                s += node.getElement() + ", ";
            }

            // Add the last element without a comma.
            s += node.getElement();
        }

        s += "]";
        return s;
    }
}