• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

in case of fast array or link list

 
Ranch Hand
Posts: 1325
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Ranch Hand
Posts: 449
Scala IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 80282
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
lowercase baba
Posts: 13091
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Muhammad Khojaye
Ranch Hand
Posts: 449
Scala IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 80282
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Unfortunately java.util.LinkedList hasn't got an insertAfter method.

And Fred's answers were so much better phrased than mine.
 
author
Posts: 23958
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Campbell Ritchie
Marshal
Posts: 80282
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Sheriff
Posts: 22821
132
Eclipse IDE Spring Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Good Explanation Jesper Young .thanks
 
Rob Spoor
Sheriff
Posts: 22821
132
Eclipse IDE Spring Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Ranch Hand
Posts: 317
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 80282
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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

Thank you. I was mistaken there. Sorry.
 
Rob Spoor
Sheriff
Posts: 22821
132
Eclipse IDE Spring Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 317
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Aruna
This link may help you more http://java.sun.com/developer/JDCTechTips/2002/tt0910.html
 
Muhammad Khojaye
Ranch Hand
Posts: 449
Scala IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 80282
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 80282
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.

 
Mike Simmons
Master Rancher
Posts: 5122
82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 80282
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 4179
22
IntelliJ IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
permaculture is a more symbiotic relationship with nature so I can be even lazier. Read tiny ad:
We need your help - Coderanch server fundraiser
https://coderanch.com/wiki/782867/Coderanch-server-fundraiser
reply
    Bookmark Topic Watch Topic
  • New Topic