Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  ArrayList vs LinkedList  (Read 4985 times)
0 Members and 1 Guest are viewing this topic.
Offline roland
« Posted 2012-06-04 14:19:49 »

Hi, I am adding a whole bunch of elements to a list, then iterating through it once.
-no contains
-no delete

LinkedList is order(1) for add
where as ArrayList is worst case order(n) when doubling its size (assuming it starts from the initial size)

Why is ArrayList still slightly faster for me?

Thanks,
roland
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2012-06-04 14:25:08 »

In general: the Big-O notation only states what the performance characteristics are for growth. Meaning that O(1) can be a lot slower than O(n) or even slower than O(n2), depending on size of the datastructure.



In this case: even LinkedList.add(0, value), which is the ideal case for LinkedList and the worst case for ArrayList, will only surpass ArrayList.add(0, value) in performance for 'really big lists'.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline roland
« Reply #2 - Posted 2012-06-04 14:29:20 »

Thanks for the reply, Riven Smiley

So ArrayList is the fastest of the Java collections, say for adding up to 1 million elements?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2012-06-04 14:31:59 »

Thanks for the reply, Riven Smiley

So ArrayList is the fastest of the Java collections, say for adding up to 1 million elements?
I don't know. Measure it.

If you are adding elements at the end of the List, then ArrayList should always be used.

There are barely any cases where LinkedLists are a good idea.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline roland
« Reply #4 - Posted 2012-06-04 14:34:45 »

Linked Lists are doubly linked though right? why are they slower for adding at the end?
Edit: Oh, you mean because that's fast for ArrayList and ArrayList is faster than LinkedList
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 816
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2012-06-04 14:37:24 »

Linked Lists are doubly linked though right? why are they slower for adding at the end?
For every elements in the list, a new Object is created, which takes time. These objects add another level of indirection and are scattered all over the heap, resulting in lots of cache misses.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline roland
« Reply #6 - Posted 2012-06-04 14:40:12 »

Oh, I see Smiley
Thanks Riven!
Offline sproingie

JGO Kernel


Medals: 202



« Reply #7 - Posted 2012-06-04 15:30:47 »

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #8 - Posted 2012-06-04 15:33:00 »

Yup, I pretty much never use LinkedList. Always ArrayList. Plus index access is a lot nicer in my opinion than using Iterators.

See my work:
OTC Software
Offline krasse
« Reply #9 - Posted 2012-06-04 22:09:20 »

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

I often use the ListIterator where you can remove an element while iterating through the list. It's convenient for objects that are removed suddenly like particles, actions, projectiles etc. This is probably bad to do with an ArrayList.
Its mainly for convenience though, I haven't tested the performance, but I still use it quite often Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #10 - Posted 2012-06-05 01:22:21 »

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

I often use the ListIterator where you can remove an element while iterating through the list. It's convenient for objects that are removed suddenly like particles, actions, projectiles etc. This is probably bad to do with an ArrayList.
Its mainly for convenience though, I haven't tested the performance, but I still use it quite often Smiley
Just do 1 pass and remove all the deleted objects at once O(n).

See my work:
OTC Software
Offline davedes
« Reply #11 - Posted 2012-06-05 01:35:40 »

LinkedList has very few use cases where it's in any way superior to ArrayList.  Small lists of large chunks ala a "free list" perhaps, or one where you're doing a lot of mutations whilst navigating in the middle of it ... not your typical collection uses.  If you need a non-concurrent Queue implementation, use ArrayDeque.

I often use the ListIterator where you can remove an element while iterating through the list. It's convenient for objects that are removed suddenly like particles, actions, projectiles etc. This is probably bad to do with an ArrayList.
Its mainly for convenience though, I haven't tested the performance, but I still use it quite often Smiley
Just do 1 pass and remove all the deleted objects at once O(n).
Another way to do it

Offline krasse
« Reply #12 - Posted 2012-06-05 07:02:36 »

I used that method before I started messing around with LinkedLists. It looks so deceptively nice and clean when you do it that way Cheesy

Offline princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #13 - Posted 2012-06-05 08:39:06 »

So deceptively nice, clean and simple it's been at the core of my games for the last 10 years Smiley

Cas Smiley

Offline krasse
« Reply #14 - Posted 2012-06-05 10:31:46 »

Well, has anyone played your games?
It might just work nicely on your system Wink

Offline R.D.

Senior Duke


Medals: 2
Projects: 1


"For the last time, Hats ARE Awesome"


« Reply #15 - Posted 2012-06-05 11:37:40 »

I'm "cheating" this like so:

1  
2  
3  
4  
5  
for(int i = (list.size() - 1); i >= 0; i--) {
   if(updateDrop(delta, list.get(i))) {
      releaseDrop(list, i);      
   }
}


where releaseDrop removes the "drop" (strange rain system) and add it to the free list. Shocked Dunno if this is good but it works quite fast Cheesy
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #16 - Posted 2012-06-05 19:14:53 »

Yep, actually what Cas is doing is what I was referring to. The 1 pass can be the same thing as the update pass.

See my work:
OTC Software
Offline Rorkien
« Reply #17 - Posted 2012-06-05 19:55:35 »

What is the issue with the ArrayList.remove() method? I noticed that nobody here uses it...
Offline matheus23

JGO Kernel


Medals: 109
Projects: 3


You think about my Avatar right now!


« Reply #18 - Posted 2012-06-05 20:03:18 »

The problem with the remove() method is, that everything, which is in the ArrayList's array AFTER that element to be deleted, will be needed to be shifted one element to the left. That makes the method kind of slow.
(but I don't acctually care... its fast enough, unless you spam delete Elements ?!?)

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline ChristerSwahn

Junior Newbie





« Reply #19 - Posted 2012-06-07 17:32:01 »

Sounds like there would be some case for writing a new linked list implementation backed by one or a small set of arrays, now that the RAM cache misses is such a major performance factor. I.e. in order to avoid new object creation for each link, maintaining cache locality, and yet offer fast insertion and deletion.

Offline sproingie

JGO Kernel


Medals: 202



« Reply #20 - Posted 2012-06-07 18:18:45 »

Scala's default IndexedSeq implementation, Vector, works pretty much like that, using a some sort of wide tree of array chunks.  Performance is pretty good.  Python's deque I think uses chunks.  Java's ArrayDeque uses a single array, it's just smart enough to adjust the starting index when deleting from the front instead of shifting everything over.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (41 views)
2014-10-17 03:59:02

Norakomi (33 views)
2014-10-16 15:22:06

Norakomi (26 views)
2014-10-16 15:20:20

lcass (30 views)
2014-10-15 16:18:58

TehJavaDev (59 views)
2014-10-14 00:39:48

TehJavaDev (60 views)
2014-10-14 00:35:47

TehJavaDev (50 views)
2014-10-14 00:32:37

BurntPizza (66 views)
2014-10-11 23:24:42

BurntPizza (38 views)
2014-10-11 23:10:45

BurntPizza (80 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!