Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 3

The method dataStructures.ChainWithSet.set is given below. 
/** set the element whose index is theIndex to theElement
  * @throws IndexOutOfBoundsException when theIndex < 0
  * or theIndex >= size 
  * @returns old element with index equal to theIndex */
public Object set(int theIndex, Object theElement)
{
   checkIndex(theIndex);

   // move to node with element whose index is theIndex
   ChainNode currentNode = firstNode;
   for (int i = 0; i < theIndex; i++)
      currentNode = currentNode.next;

   Object elementToReturn = currentNode.element;
   currentNode.element = theElement;
   return elementToReturn;
}


The complexity is O(theIndex) because it takes this much time to find the node whose element field is to be set to theElement.