Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

ArrayList and LinkedList?

 
Allan Wang
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 83
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic