What's the difference between LinkedList and ArrayList?

[love2mao]

ArrayList implements interface RandomAccess, while
LinkedList not. I've thought LinkedList doesn't support random
success. However, cgecking its methods, I found out that it DOES!

set(int index, Object element)
// Replaces the element at the specified position in this list with the specified
 element.

Then looks like one of them is redundant? Am I right?

Thank you.

[cma]

LinkedList's don't support the notion of constant-time random-access. This means that in order to access any element in the linked list, there's code that has to traverse the list until it comes to the proper node, then do the operation (such as either return the item stored in the node or store a new item). That's why traversing a LinkedList using get() is incredibly inefficient.

[Chris_Student]

I think the way ArrayList works is that it is basically an array of finite size. Once this array is filled, it stores additional data as a linked list.

[cma]

Not exactly, ArrayList's get() method runs in constant time (http://java.sun.com/j2se/1.5.0/docs/...ArrayList.html). Using a linked list just because you need extra space would violate that contract. What usually happens is when an ArrayList's internal storage (usually an array) needs more space, it will create a new larger array, copy the elements over, then do a couple of reference re-assignments.

[cjard]

ArrayList implements interface RandomAccess, while
LinkedList not. I've thought LinkedList doesn't support random
success. However, cgecking its methods, I found out that it DOES!

set(int index, Object element)
// Replaces the element at the specified position in this list with the specified
 element.

Then looks like one of them is redundant? Am I right?

Thank you.

that an element can be retrieved from the centre of a sequential flow of data does not necessarily confer that the data is accessed randomly (i.e. directly, without need to traverse the stream first)


a linked list is like a audio tape or a backup tape; you can find a file on it/song on it but you have to stream through from one end to the other. its very quick to add more tape to the end; just splice it in.

An arraylist is more like a keyboard; you can see the key you want to press, you go straight to it. to add more keys is a major operation