ListTiming.java

import java.util.LinkedList;

public class ListTiming {
    public static void main(String[] args) {
      
        long startTime, endTime, diff;

        // Time our list object
        startTime = System.nanoTime();
        testMyList();
        endTime = System.nanoTime();
        diff = endTime - startTime;

        System.out.println("Elapsed time: "+ (diff/1E6) + " ms");

        // Time the Collections list object
        startTime = System.nanoTime();
        testTheirList();
        endTime = System.nanoTime();
        diff = endTime - startTime;

        System.out.println("Elapsed time: "+ (diff/1E6) + " ms");
    }

    public static void testMyList(){
        for(int k=0;k<10;k++) {
        	LinkedIntegerList list = new LinkedIntegerList();
        	for(int i=0; i<1E5; i++ ) {
        		list.add(i);
        	}
        }
    }

    public static void testTheirList(){
        for(int k=0;k<10;k++) {
        	LinkedList<Integer> list = new LinkedList<Integer>();
        	for(int i=0; i<1E5; i++ ) {
        		list.add(i);
        	}
        }
    }

}

class LinkedIntegerList{
    LilNode head;
    public LinkedIntegerList() {
        this.head = null;
    }

	// Add an item to the list.
	// This starts with a pointer to the beginning of the list,
	// and runs all the way through the list to the end. 
	public void add(int z) {
		if(this.head==null) { 
			head = new LilNode(z); 
		} else {
			LilNode iter = this.head;
			while(iter.next != null) { 
				iter = iter.next;
			}
			// Now we are at the end...
			iter.next = new LilNode(z);
		}
	}

	// Add an item to a location in the list.
	// This starts with a pointer to the beginning of the list,
	// and runs all the way up to index. It then swaps out (carefully)
	// the pointers in the list.
	public void add(int index, int z) {
		if(index==0) { 
			// New head node equal data (z) and pointer to old head node
			this.head = new LilNode(z, this.head);
		} else {
			// Get the node right in front of the one we are going to add
			LilNode pointer = nodeAt(index-1);

			// Add the new node right in front
			// New pointer.next equals data (z) and old pointer.next
			pointer.next = new LilNode(z, pointer.next);
		}
	} 

}
class LilNode {
    Integer data;
    LilNode next;
    public LilNode(Integer z){
        this(z,null);
    }
    public LilNode(Integer z, LilNode next) {
        this.next = next;
        this.data = z;
    }
}