import java.util.NoSuchElementException;

/**
 * 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()
    {
        first = null;
        size = 0;
    }

    /**
     * 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) 
    {
        // An empty list is a special case.
        if ( size == 0 )
        {
            addFirst(element);
        }
        else
        {
            K_LLNode thisOne = first;
            K_LLNode nextOne = first.getNext();

            while ( nextOne != null )
            {
                thisOne = nextOne;
                nextOne = nextOne.getNext();
            }

            // nextOne is null, so thisOne is the last in the list until
            // we add one after it.
            thisOne.setNext(new K_LLNode(element));
            size++;
        }
    }

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

        // Go ahead and reduce size now, before any return statements.
        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.
        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;
    }

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

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

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

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

}