I had the same, so I let somebody else bite the bullet. Thx!
Why would you use List instead of ArrayList? When would you ever need to switch to a different List implementation (unless you didn’t understand what you were doing)?
One practical application I have of it is 2d arrays where I switch between packed and sparse implementatios.
Some pseudo-ish-code:
interface Layer<T> {
T get(int x, int y);
void set(int x, int y, T val);
}
class ArrayLayer<T> implements Layer<T> {
ArrayList<T> store;
public T get(int x, int y) { return store.get(x + y*width); }
public void set(int x, int y, T val) { store.set(x + y*width, val); }
}
class MapLayer<T> implements Layer<T> {
Map<Pair<Int,Int>, T> store;
public T get(int x, int y) { return store.get(new Pair(x,y)); }
public void set(int x, int y, T val) { store.put(new Pair(x,y), val); }
}
class Display {
List<Layer<Tile>> layers;
public Display(int width, int height) {
layers.add(new ArrayLayer<Tile>(width,height)); // tiles
layers.add(new MapLayer<Tile>(width,height)); // cursor
}
}
(the real thing is scala so it’s a lot less ugly … though I manage to add plenty of ugliness in other ways)
Because one of the geniuses here abouts might implement a version of one of the others that actually works better? Like a LinkedList backed by a Node object pool or something that’ll take some of the pain (Extra time to create/manage the nodes) out of using them, or implement whatever else might be required to make a ‘good’ Java LinkedList implementation. I mean it still bothers me that something backed with an array, that has to copy to grow as well as shift indexes is better than LinkedList for regular insertions and the like. Raw. >.>
Ah, seems I was misunderstood then. If you intentionally need to use different List implementations, I understand. But if all your code uses is ArrayList, then using List as the field type makes my eyes bleed.
My question has nothing to do with polymorphism really. It’s more style-oriented.
Well it bother me too when I just finished my class on datastructure but since I learn how to live with it… Creating a lot of object is not free and you need more operation in linked list to add a new element.
Well you might consider using a LinkedArrayList : You get the best of the two world. Here is a quick example
public class ArrayList {
private int[] list = new int[10];
private int size = 0;
public void add(int n){
if(size < list.length-1){
list[size] = n;
size++;
}else{
int[] newlist = new int[list.length*2];
for(int i=0; i<list.length; i++){
newlist[i] = list[i];
}
list = newlist;
list[size] = n;
}
}
}
public class LinkedArrayList {
private class Node {
Node next;
Node previous;
int[] array = new int[1000];
int size = 0;
public Node(Node previous){
this.previous = previous;
}
public boolean isFull(){
return size > array.length;
}
public void add(int n){
array[size] = n;
}
}
private Node head;
private Node tail;
private int size = 0;
public void add(int n){
if(size == 0){
head = new Node(null);
tail = head;
tail.add(n);
size++;
}else{
if(tail.isFull()){
Node newnode = new Node(tail);
tail.next = newnode;
tail = newnode;
tail.add(n);
size++;
}else{
tail.add(n);
size++;
}
}
}
}
You can test a lot of insertions with that :
public class Test {
public static void main(String [] args){
long begin;
long end;
long delta;
begin = System.nanoTime();
ArrayList arrayList = new ArrayList();
for(int i=0; i<100000000; i++){
arrayList.add(i);
}
end = System.nanoTime();
delta = end-begin;
System.out.println("--- ArrayList ---");
System.out.println("Time elapsed in nano : " + delta);
System.out.println("Time elapse in milli : " + delta/(1000*1000));
System.out.println();
begin = System.nanoTime();
LinkedArrayList linkedArrayList = new LinkedArrayList();
for(int i=0; i<100000000; i++){
linkedArrayList.add(i);
}
end = System.nanoTime();
delta = end-begin;
System.out.println("--- LinkedArrayList ---");
System.out.println("Time elapsed in nano : " + delta);
System.out.println("Time elapse in milli : " + delta/(1000*1000));
System.out.println();
}
}
Here are my results running it :
--- ArrayList ---
Time elapsed in nano : 708601408
Time elapse in milli : 708
--- LinkedArrayList ---
Time elapsed in nano : 362729744
Time elapse in milli : 362
You would probably get even more benefits with insertion since in the ArrayList you have to move every objects back one spot while in the LinkedArrayList you only have to move the object in one Node 
Yep, Datastructures: Where the information doesn’t really matter and the numbers are made up.
Ahem, that’s really why I suggested this Wiki chunk. Because Data Structure classes tend to spend so much time beating you over the head about the BigO stuff, and how LinkedLists are good in these situations and this other is good in those situations. Then you get out into the real world and find out “Welp, because of the way the API implemented these, you’ll be using ArrayList pretty much exclusively”.
As an aside, you’d still need to implement a proper Iterator for that system that meets the requirements of being an implementer of the List API. Which is more of what I’m talking about.
It is pretty much intresting to have had a look into languages like scheme, which build up entirely on linked Lists. That means iterating on such a list is very fun… you need to do it with recursion btw, because there aren’t any loops.
Take a look, guys, you will find it ugly in the beginning, if you wrote Java and other imperative language before. But I actually think the concept of that language is pretty good.
Like ra4king I disagree with the general advice, but on different grounds. The notion of using the most basic ‘type’ which fits a given need is something I pretty much never do. The idea behind this is the sound thought of hiding of implementation details. Given the strengths of refactoring this is slightly less important that it once was, but that’s not really my point. You’re much more effective at hiding implementation details by not giving the world outside of the subsystem in question ANY notion of how it’s implemented. This is achieved by hiding the field(s) in question from the outside world and providing the required methods to access/modify the contained set. An added bonus of going this route is that it’s much more backend compiler friendly.
Add wiki vector ^^
Removed wiki vector. 
Added some basic info on multi-threaded collections. I’m sure someone else could add some more info on some of the other concurrent.* collections but I haven’t used them much.
Polymorphism and accessibility are two distinct subjects. You should pretty much always make fields private, and keep the type of the field as generic as possible, for the functionality required.
Sure, but that’s not really the topic at hand. The point is protection against changes in implementation. If a field is private, then there’s no reason not to state its concrete type. Not doing so (in general) causes more work for the backend compiler, which it may not be able to perform. For instance declaring a reference to an interface (should always be able to for private however), the backend may not be able to infer a base class and therefore require a dynamic lookup for each method call.
Polymorphism, accessibility and performance are three distinct subjects.
If you take all three into account, you can never give any ‘general advice’.
IMHO the ‘general advice’ part was offtopic in this wiki entry in the first place, so we might have to move that to a different wiki entry that takes into account some context on the matter.
Yes, have links to related topics would make much more sense.
Time to try adding WikiLinks to the SMF wiki, Riven? 
Nuh-uh!
Added a reference section with a sole entry of a link to an applet that shows how some data structures work step-by-step.
BTW: Why not add LaTeX support?
I think that there should be something about iterators and the enhanced “for each” loop. Using this syntactic sugar will create a new iterator every time it is called with the straight java implementations of lists and maps etc. If you are iterating over big collections in every cycle of your game loop you start to get some nice GC homework to do. This might not be so relevant on a Desktop or laptop, but on a mobile device this is something you really need to be aware of. LibGDX for example provides datastructures which reuse the iterators. You need to be careful about doing nested loops, but this has never hindered me in my own use of them.
I think that there should be something about iterators and the enhanced “for each” loop. Using this syntactic sugar will create a new iterator every time it is called with the straight java implementations of lists and maps etc. If you are iterating over big collections in every cycle of your game loop you start to get some nice GC homework to do. This might not be so relevant on a Desktop or laptop, but on a mobile device this is something you really need to be aware of. LibGDX for example provides datastructures which reuse the iterators. You need to be careful about doing nested loops, but this has never hindered me in my own use of them.