GeeCON Prague 2014*
The moose likes Beginning Java and the fly likes in case of fast array or link list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Beginning Java
Bookmark "in case of fast array or link list" Watch "in case of fast array or link list" New topic
Author

in case of fast array or link list

sam liya
Ranch Hand

Joined: Nov 25, 2008
Posts: 1165
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?
Muhammad Khojaye
Ranch Hand

Joined: Apr 12, 2009
Posts: 449

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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39095
    
  23
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!
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11356
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Muhammad Khojaye
Ranch Hand

Joined: Apr 12, 2009
Posts: 449

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

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39095
    
  23
Unfortunately java.util.LinkedList hasn't got an insertAfter method.

And Fred's answers were so much better phrased than mine.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18876
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39095
    
  23
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.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19697
    
  20

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14196
    
  20

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.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Good Explanation Jesper Young .thanks
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19697
    
  20

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.
Bob Wheeler
Ranch Hand

Joined: Apr 24, 2009
Posts: 317
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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39095
    
  23
Rob Prime wrote:Henry was talking about ListIterator's add(E) method.
Thank you. I was mistaken there. Sorry.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19697
    
  20

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
Bob Wheeler
Ranch Hand

Joined: Apr 24, 2009
Posts: 317
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
Chitta Ranjan Mahato
Ranch Hand

Joined: Jun 20, 2009
Posts: 38
Hello Aruna
This link may help you more http://java.sun.com/developer/JDCTechTips/2002/tt0910.html
Muhammad Khojaye
Ranch Hand

Joined: Apr 12, 2009
Posts: 449

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.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.

ActionArrayListArrayDequeueLinkedList
get from the beginning or end of listO(1)O(1)O(1)
get from the middle of listO(1)O(1)O(N)
add/delete at beginning of listO(N)O(1)O(1)
add/delete at end of listO(1)O(1)O(1)
add/delete in middle of list by random accessO(N)O(N)O(N)
add/delete in middle of list using an iteratorO(N)O(N)O(1)


All the ArrayList and ArrayDequeue costs above are actually amortized costs.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39095
    
  23
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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39095
    
  23
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
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

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

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.


Steve
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39095
    
  23
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.
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: in case of fast array or link list