compare LinkedList with ArrayList and Vector

A

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?=

Amit said:
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
 
M

Mike Schilling

Amit Jain said:
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.
 
A

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
 
D

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>().
 
M

Mike Schilling

Amit Jain said:
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.
 
L

Lew

Mike Schilling wrote (and thus should be attributed):
Amit said:
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.
 
R

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.
 
M

Mike Schilling

Roedy Green said:
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..
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top