import java.lang.*;
import java.util.*;


public class LinkedList extends CommonList
{
    class Link 
    {
        Object item;
        Link next;
        
        Link(Object o) 
        {
            item = o;
            next = null;
        }
        
    }


    protected Link head;        // the first link in the list


    LinkedList() 
    {
        head = null;
    }


    public void add(int index, Object element)
    {
        Link cur = head;
        Link prev = null;
        
        for (int i = 0; i < index; i++) {
            prev = cur;
            cur = cur.next;
        }
        Link l = new Link(element);     
        if (prev == null) {
            // adding to head of list
            l.next = head;
            head = l;
        } else {
            // adding to middle of list
            l.next = prev.next;
            prev.next = l;
        }
    }


    
}