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


Win a copy of Java 8 in Action this week in the Java 8 forum!
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: ArrayList and LinkedList?
 
Similar Threads
Are ArrayList really slower than LinkedList?
What is the use of this New Enhanced for loop feature ??
is using ArrayList.iterator() is faster than looping ArrayList in for loop?
Speed of Accessing ArrayList and LinkedList
Hashtable vs Hashmap