in case of fast array or link list

what is the fast access when considering accessing element?
array or link list?
in my knoledge it is array?because we can access any element directly.but in link list we have to go several element to access other element.is it true?

True, ArrayList gives better performance when accessing and iterating objects whereas LinkedList gives better performance when adding and removing objects from beginning and end. LinkedList become worse when adding/removing objects from middle.

Are you sure about that? LinkedLists are slower at finding elements in the middle, but it may be faster to insert if you can use an insertAfter method. Have a look at the RandomAccess interface, and look which classes implement it. And the fastest stack implementation is ArrayDeque!

I would say that a) if the linked list is implemented correctly, and b) you know the spot where you want to insert it, a linked list would be faster to insert in the middle.

If you DON'T know where to insert it buy you have to search for it, there's not much of an advantage over either - you still have to iterate over it until you find the spot. But once you do... you're back at the first case, where again the linked-list wins.

Campbell Ritchie wrote:LinkedLists are slower at finding elements in the middle, but it may be faster to insert if you can use an insertAfter method.

Thanks Campbell for giving insertAfter method

Unfortunately java.util.LinkedList hasn't got an insertAfter method.

And Fred's answers were so much better phrased than mine.

Campbell Ritchie wrote:Unfortunately java.util.LinkedList hasn't got an insertAfter method.

And Fred's answers were so much better phrased than mine.

Well, it kinda does. It just has a different name. There is an add() method in the list iterator, which is used to insert after the previously traversed element. So, while you are iterating through a linked list, you can insert on-the-fly.

Henry

But add(E) adds an element at the end of the List, and add(E, int) would have to iterate through the List to find its insertion location.

Campbell Ritchie wrote:But add(E) adds an element at the end of the List, and add(E, int) would have to iterate through the List to find its insertion location.

Henry was talking about ListIterator's add(E) method. That adds an element just one position after the current position.

Muhammad Ali Khojaye wrote:True, ArrayList gives better performance when accessing and iterating objects whereas LinkedList gives better performance when adding and removing objects from beginning and end. LinkedList become worse when adding/removing objects from middle.

You have some things confused.

- ArrayList is fast at looking up an element at a random position (if you know the index of the element, it can find it very quickly).
- LinkedList is slower at looking up an element at a random position, because the list has to be traversed to find the element.

- ArrayList is slow at inserting elements (head, tail or in the middle), because all elements have to be shifted.
- LinkedList is fast at inserting elements (head, tail or in the middle), because the new element can just be linked in, existing elements to not have to be moved.

The API documentation of java.util.ArrayList and java.util.LinkedList give more information.

Good Explanation Jesper Young

.thanks

Jesper Young wrote:- ArrayList is slow at inserting elements (head, tail or in the middle), because all elements have to be shifted.

Not 100% correct. Granted, inserts at the start or middle are slow because of the shifting. However, inserts at the tail can be fast if the backing array still has capacity left. It can then simply store the element at the next available spot and increase the count. It becomes slow again if the capacity is not sufficient, because a new array must be created and all elements must be copied.

Rob Prime wrote:

Jesper Young wrote:- ArrayList is slow at inserting elements (head, tail or in the middle), because all elements have to be shifted.

Not 100% correct. Granted, inserts at the start or middle are slow because of the shifting. However, inserts at the tail can be fast if the backing array still has capacity left. It can then simply store the element at the next available spot and increase the count. It becomes slow again if the capacity is not sufficient, because a new array must be created and all elements must be copied.

This is really an interesting discussion. Looking at the API, they say for the inserting operation (add) it needs amortized constant time. They also say, that by adding elements to the array the capicity grows automatically and the growth policy is not specified. So how should we know what the effect is? is it negligible or not?

cheers
Bob

Source: API (ArrayList)

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
...
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

Rob Prime wrote:Henry was talking about ListIterator's add(E) method.

Thank you. I was mistaken there. Sorry.

Bob Wheeler wrote:This is really an interesting discussion. Looking at the API, they say for the inserting operation (add) it needs amortized constant time. They also say, that by adding elements to the array the capicity grows automatically and the growth policy is not specified. So how should we know what the effect is? is it negligible or not?

Well, I usually start by looking at the source of the class (current implementation). That shows me that the size of the backing array is increased with at least 50% if it needs to be. Afterwards, all data is copied to the new array using System.arraycopy (in the end). That copying is O(list.size()).

I don't really buy that amortized constant time. If you add many objects without using addAll (addAll moves everything as much as needed, so only one move for all elements combined), that can potentially cause many resizing and shift operations. For instance, an empty ArrayList with initial capacity of 10, with 1000 objects added individually at index 0, will require 11 resizing operations*, and 999 shift operations. Those shift operations range from 1 element to 999 elements. Including the copying during the resizing operations, that's 1010 calls to System.arraycopy, all with O(list.size()). In the end, 501500 objects are copied, for an average of over 501 per added object. No, you can't tell me that's even remotely constant time. Even adding at the center (rounding up) requires 251500 objects copied, or an average of over 251 per added object.

Adding at the end, sure, that's only 11 System.arraycopy calls. Using addAll there is at most 2 (one for resizing, optionally one for shifting). Compared to the 1000 added elements, that's negligible. (And because the list is initially empty there will actually be 0 copied objects.)

*10 -> 16 -> 25 -> 38 -> 58 -> 88 -> 133 -> 200 -> 301 -> 452 -> 679 -> 1019

Rob Prime wrote:

Bob Wheeler wrote:This is really an interesting discussion. Looking at the API, they say for the inserting operation (add) it needs amortized constant time. They also say, that by adding elements to the array the capicity grows automatically and the growth policy is not specified. So how should we know what the effect is? is it negligible or not?

Well, I usually start by looking at the source of the class (current implementation). That shows me that the size of the backing array is increased with at least 50% if it needs to be. Afterwards, all data is copied to the new array using System.arraycopy (in the end). That copying is O(list.size()).

It looks like either the API wasn't precise enough to mention they talk only about the "add to the end" method or it's simply false. But sure enough, that's true. If you add only to teh end of the arraylist the amortized cost are constant.

Rob Prime wrote:
I don't really buy that amortized constant time. If you add many objects without using addAll (addAll moves everything as much as needed, so only one move for all elements combined), that can potentially cause many resizing and shift operations. For instance, an empty ArrayList with initial capacity of 10, with 1000 objects added individually at index 0, will require 11 resizing operations*, and 999 shift operations. Those shift operations range from 1 element to 999 elements. Including the copying during the resizing operations, that's 1010 calls to System.arraycopy, all with O(list.size()). In the end, 501500 objects are copied, for an average of over 501 per added object. No, you can't tell me that's even remotely constant time. Even adding at the center (rounding up) requires 251500 objects copied, or an average of over 251 per added object.
Adding at the end, sure, that's only 11 System.arraycopy calls. Using addAll there is at most 2 (one for resizing, optionally one for shifting). Compared to the 1000 added elements, that's negligible. (And because the list is initially empty there will actually be 0 copied objects.)
*10 -> 16 -> 25 -> 38 -> 58 -> 88 -> 133 -> 200 -> 301 -> 452 -> 679 -> 1019

Thanks for your answer. To make it short, I guess the costs for adding at index 0 / center are O(n) (for your example k * 1000; for an array with 1000 entries) and at the end amortized O(1). The program has to shift the entries, which is only possible in linear time. And here comes the advantage for the linkedList, which has only costs O(1).

cheers
Bob

Hello Aruna
This link may help you more http://java.sun.com/developer/JDCTechTips/2002/tt0910.html

Jesper Young wrote:
- LinkedList is fast at inserting elements (head, tail or in the middle), because the new element can just be linked in, existing elements to not have to be moved.

Well, what i think is that LinkedList gives good performance when adding elements at the beginning/end but it may not be good when adding objects at middle because it needs to scan the node whenever it needs to add an object. Please correct me, if i am wrong.

Here's a summary of the performance of both lists for various operations discussed above. For our purposes here, you can pretend O(1) simply means "fast" and O(N) means "slow". Usually.

Action	ArrayList	ArrayDequeue	LinkedList
get from the beginning or end of list	O(1)	O(1)	O(1)
get from the middle of list	O(1)	O(1)	O(N)
add/delete at beginning of list	O(N)	O(1)	O(1)
add/delete at end of list	O(1)	O(1)	O(1)
add/delete in middle of list by random access	O(N)	O(N)	O(N)
add/delete in middle of list using an iterator	O(N)	O(N)	O(1)

All the ArrayList and ArrayDequeue costs above are actually amortized costs.

I think you and Jesper are both correct, just phrasing it differently. What Jesper means is that LinkedList is very fast for insertion (or removal) of an element, once the location of the element has been found. But finding that location may be slower, in the middle of the list.

I think when it says in the API that add() runs in amortized constant time, it means add(E), and that the add(int, E) method counts as one of the "other" operations which run in linear (O(n)) time

I added ArrayDequeue to my last post, as it's an excellent alternative for some cases. Good call, Campbell.

Also, I agree with Campbell's last post - the ArrayList API did a poor job of saying what they meant, but I'm sure they were just thinking of the one-argument add(), not the two-argument version.

Mike Simmons wrote:I added ArrayDequeue to my last post, as it's an excellent alternative for some cases. Good call, Campbell.

Also, I agree with Campbell's last post - the ArrayList API did a poor job of saying what they meant, but I'm sure they were just thinking of the one-argument add(), not the two-argument version.

Which is kind of funny, because the JavaDoc style guide specifically uses the ArrayList add methods as an example for referring to a specific form of a method, or to all forms of a method:

* Omit parentheses for the general form of methods and constructors

When referring to a method or constructor that has multiple forms, and you mean to refer to a specific form, use parentheses
and argument types. For example, ArrayList has two add methods: add(Object) and add(int, Object).
The add(int, Object) method adds an item at a specified position in this arraylist.
However, if referring to both forms of the method, omit the parentheses altogether. It is misleading to include empty parentheses,
because that would imply a particular form of the method. The intent here is to distinguish the general method from any of its
particular forms. Include the word "method" to distinguish it as a method and not a field.
The add method enables you to insert items. (preferred) The add() method enables you to insert items. (avoid when you mean "all forms" of the add method)

Agreed. But it's not as if everything in the standard Java API was written by a single person, and it's reasonable to imagine that not everyone was on the same page at all times. Also, to imagine that those individual persons might simply make mistakes. To me, it seems like it is (or at least, should have been) very, very obvious to anyone who thought a moment about it, that add(E, int) could not be O(1). And so I think it's far more believable that they simply forgot to consider the more general meaning of "add" (sans parentheses) or they were unaware of it. Well, even if they were unaware, it should have been obvious on consideration that the given API did not distinguish between the different cases. So I think they just overlooked it entirely, having been more concerned with implementation than documentation. That's just a guess, of course.

Mike Simmons wrote:Good call, Campbell.

Coming from Mike Simmons that means a lot. Thank you.

And I can't remember where I first heard about ArrayDeque. It appears such a strange design, until you read it properly.

Mike Simmons wrote:Agreed. But it's not as if everything in the standard Java API was written by a single person, and it's reasonable to imagine that not everyone was on the same page at all times. Also, to imagine that those individual persons might simply make mistakes. To me, it seems like it is (or at least, should have been) very, very obvious to anyone who thought a moment about it, that add(E, int) could not be O(1). And so I think it's far more believable that they simply forgot to consider the more general meaning of "add" (sans parentheses) or they were unaware of it. Well, even if they were unaware, it should have been obvious on consideration that the given API did not distinguish between the different cases. So I think they just overlooked it entirely, having been more concerned with implementation than documentation. That's just a guess, of course.

Oh, I agree that it was such a (simple really) mistake. I just find it ironic that the very method used in the example doesn't follow the guide, that's all.