aspose file tools*
The moose likes Beginning Java and the fly likes ArrayList and LinkedList? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "ArrayList and LinkedList?" Watch "ArrayList and LinkedList?" New topic
Author

ArrayList and LinkedList?

Allan Wang
Greenhorn

Joined: Apr 23, 2001
Posts: 20
According to Java Tutorial, "Positional access is linear time in a LinkedList and constant time in an ArrayList." But after I tested it using following code, the result shows there is no difference between two. Could someone clarify it? Thanks for any help.
------code-------
import java.util.*;
public class Test {
public static void main(String[] args) {
ArrayList al = new ArrayList();
for (int i=0; i<100000; i++) {
al.add(new Integer(i));
}
long begintime = System.currentTimeMillis();
for (int i=0; i<100; i++) {
int index = (int)(Math.random()*10000);
System.out.println(al.get(index));
}
System.out.println("arraylist during:"+
(System.currentTimeMillis()-begintime));
LinkedList ll = new LinkedList(al);
begintime = System.currentTimeMillis();
for (int i=0; i<100; i++) {
int index = (int)(Math.random()*10000);
System.out.println(ll.get(index));
}
System.out.println("linkedlist during:" +
(System.currentTimeMillis()-begintime));
}
}
output:
...
arraylist during:2534
...
linkedlist during:2163
Allen Alchian
Ranch Hand

Joined: Oct 11, 2000
Posts: 83
I believe what is meant is that accessing a single element in an array requires constant time regardless of which element you are accessing, whereas accessing a single element in a linked list requires linear time. In other words, if you want to access the 100th item in the array, the computer would go directly to the 100th item and get it. However with a linked list, the computer would have to go to the first item, then the second item, then the third item, etc, until it got to the 100th item...hence the "linear" access time for the linked list.
In your test, you accessed the 100th item of the array after accessing all of the previous items first...hence the time savings of an array data structure was eliminated.
Allen


Allen
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: ArrayList and LinkedList?