compare LinkedList with ArrayList and Vector

[Amit Jain]

What are the performance issue with LinkedList in compare of ArrayList
and Vector?

Position-based access has constaint-time performane for the ArrayList
and Vector classes. However, position-based access is in linear time
for a LinkedList.

 

[=?ISO-8859-1?Q?Arne_Vajh=F8j?=]

What are the performance issue with LinkedList in compare of ArrayList
and Vector?

Position-based access has constaint-time performane for the ArrayList
and Vector classes. However, position-based access is in linear time
for a LinkedList.

So you answered your own question ? Or ?

Arne

 

[Mike Schilling]

What are the performance issue with LinkedList in compare of ArrayList
and Vector?

Position-based access has constaint-time performane for the ArrayList
and Vector classes. However, position-based access is in linear time
for a LinkedList.

That's one. Now, suppose you're iterating through a List and decide to
remove the current entry (or insert a new entry before the current one.)
The cost is linear for the ArrayList but fixed for the LinkedList.

 

[Amit Jain]

That's one. Now, suppose you're iterating through a List and decide to

remove the current entry (or insert a new entry before the current one.)
The cost is linear for the ArrayList but fixed for the LinkedList.

Can you please more describe the work Linear in your answer "The cost
is linear..." .

Thanks
Amit Jain

 

[Daniel Pitts]

What are the performance issue with LinkedList in compare of ArrayList
and Vector?

Position-based access has constaint-time performane for the ArrayList
and Vector classes. However, position-based access is in linear time
for a LinkedList.

Vector is obsolete and should not be used.

LinkedList has constant time addition/removal from both ends of the
list. Also, if you have an iterator into a specific location in the
list, insertion/removal at that location is constant time. For
ArrayList (and Vector), inserting/removing from the list (other than
the end) results in an array copy of all elements after the insert/
remove position.

In most common situations, I use:
List<SomeType> myList = new ArrayList<SomeType>();
If that turns out to be to slow because I'm using a lot of middle
inserts/removals, then I can switch it with LinkedList<SomeTime>().

 

[Mike Schilling]

Can you please more describe the work Linear in your answer "The cost
is linear..." .

I was copying your use of the word. Anyway, I meant proportonal to the size
of the array.

 

[Lew]

Mike Schilling wrote (and thus should be attributed):

Can you please more describe the work Linear [sic] in your answer "The cost
is linear..." .

Polynomial of order 1.

For example, the function "f(x) = mx + k" is linear in x because it scales as
the first power of x.

"f(x) = ax^2 + bx + c" is quadratic, i.e., it scales as the second power of x.

<http://en.wikipedia.org/wiki/Linear_equation>
<http://en.wikipedia.org/wiki/Quadratic>

The context for these terms here is /asymptotic analysis/, the analysis of a
problem for its limiting characteristics. The limit of growth rate with the
size of the input is a major analytical datum.

<http://en.wikipedia.org/wiki/Big_O_notation>

For an x-fold increase in problem size (e.g., the length of a List), the time
(or other metric of effort) to solve the problem will increase by some
function of x, f(x). If f(x) doesn't change with the problem size, it's of
order 0. If it increases in direct proportion to x, it's linear. If it
increases proportionate to the square of x, it's quadratic, and so on.

There is a lot of study time in your near future. GIYF.

 

[Roedy Green]

What are the performance issue with LinkedList in compare of ArrayList

and Vector?

Look at the implementation. One is good at indexing to find an
element, the other is good at inserting and deleting and element.

 

[Mike Schilling]

Look at the implementation. One is good at indexing to find an
element, the other is good at inserting and deleting and element.

And both are crap at doing lookups, which is why Maps exist..