LinkedList - Robo Wiki -= Collecting Robocode Knowledge =-

LinkedList is a member of the standard Java Collections library. It implements the List interface.

See http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedList.html

LinkedList might be one of the most misunderstood parts of the Java API. A user of LinkedList will have to accept that it should be used mostly via its iterators and that any indexing into the list will use these and that you can get surprisingly low performance if you don't pay enough attention to this.

Even so called Java experts sometimes make this error. Googling for "java linkedlist performance" you find a page about [Java Collections Performance] from where you this page: http://www.precisejava.com/javaperf/j2se/Collections.htm

If you follow those tips and findings you get the idea that it's really stupid using a LinkedList for when you need to insert and remove elements from the middle of the list. This somehow contradicts the main idea with a linked list! The test method looks like this:

    public void addMiddle(List list) {
	long startTime = System.currentTimeMillis();

	for(int i=0;i<NUM;i++){
	    list.add(i/2,objs[i]);
	}

	long endTime = System.currentTimeMillis();
	System.out.println("Time taken for adding Objects at Middle : " + (endTime - startTime) );
    }

Using 50000 String objects this gives the following results on one of my machines (using a beta of Java 1.5):

class java.util.ArrayList:
Time taken for adding Objects at End: 16
Time taken for adding Objects at Middle : 828
Time taken for adding Objects at First : 1640

class java.util.Vector:
Time taken for adding Objects at End: 16
Time taken for adding Objects at Middle : 859
Time taken for adding Objects at First : 1672

class java.util.LinkedList:
Time taken for adding Objects at End: 47
Time taken for adding Objects at Middle : 13873
Time taken for adding Objects at First : 16

Wow! But the thing is the above code snippet does exactly what you shouldn't do with large LinkedList instances - add(index, object). Doing this instead:

    public void addMiddle(List list) {
	long startTime = System.currentTimeMillis();

	ListIterator it = list.listIterator();
	for(int i=0;i<NUM;i++){
	    it.add(objs[i]);
	    if (i % 2 == 1) {
		it.previous();
	    }
	}

	long endTime = System.currentTimeMillis();
	System.out.println("Time taken for adding Objects at Middle : " + (endTime - startTime) );
    }

My machine reports the following results:

class java.util.ArrayList:
Time taken for adding Objects at End: 16
Time taken for adding Objects at Middle : 844
Time taken for adding Objects at First : 1656

class java.util.Vector:
Time taken for adding Objects at End: 15
Time taken for adding Objects at Middle : 844
Time taken for adding Objects at First : 1688

class java.util.LinkedList:
Time taken for adding Objects at End: 31
Time taken for adding Objects at Middle : 15
Time taken for adding Objects at First : 16

Quite different! Note also that the array based lists retained their performance. Which probably means you are better off using the second idiom than the first one if you're not sure what kind of List you will be fed.

-- PEZ

The problem is that classifying linked lists in the same category (using the same interface) as array lists is just wrong, imo. Thinking that you can just replace one with the other is a big mistake, like your tests confirm. There should be a completely separated interface for linked lists, without methods using indexes, just some smart Iterator-like methods. -- ABC

I think the Java Collections designers had a different goal than the one you're after. The API seems to think a list is a list is a list. And they provide different implementations to make available lists with high performance for the general cases. LinkedList is there to give us a high performance list for when we need to add and remove objects from somewhere else than the end of the list. Not to give a linked-list-like interface, since that interface is more or less the same for any List implementation through the listIterator(). Making it possible to switch list implementations at will makes sense to me. And they have also provided excellent sceletal abstract implementations so it is really straight forward, and in many cases even easy, to roll your own List implementations. -- PEZ

Excellent sceletal abstract implementation for array like collections, not for lists. I even would go as far as saying they misinterpreted the word List, using it like a synonym of Collection. ArrayList is, for me, almost a contradition in terms, you either have an array (good for random access) or a list (good for traversal and insertion/removal anywhere). Where is, for example, an interface for a circular list?-- ABC

I share that misinterpretations I think. For me a list and an array is about the same thing. It might be my Perl background, I don't know. -- PEZ

Strange, in a java book i read there is written that the proportions of runtime from different collection objects for push and pop of elements would be like this: 3:18:1 for Vector, LinkedList and ArrayList. Maybe you PEZ get such slow results for ArrayList because you dont use an initial size. Without this, the List increases its intern array quite often (and the elements have to be copied every time). --deathcon

Push and pop. The above results only test push (the "adding Objects at End" records) and the performance is more like 1:1:1 for the three lists tested using 50000 elements. That's not slow results for ArrayList is it? I think the 3:1 difference isn't measurable (sometimes 0 millisecs are reported even). Maybe using much larger lists would show it. The test program actually tests both size-initialized lists and non-initialized ones. But on my machine there's no difference in performance on any of the above reported operations so I edited away the extra info before posting on this page. -- PEZ

Further, I think maybe your book there could be using dated versions of Java. Java 1.2 was really slow on some Collections work. 1.3 was better, but it was first with 1.4 things started to go as fast "as they should" I think. Any Robocoder should today be able to assume at least Java 1.4 I think. Even Apple has gotten 1.4 to work on OS X. -- PEZ

I am using 1.4_02 (and my book is also about 1.4) --deathcon

OK. I modified the test a bit to use lists with 500,000 elements instead:

List created using new ArrayList():
Time taken for adding Objects at End: 63

List created using new ArrayList(500000):
Time taken for adding Objects at End: 32

List created using new Vector():
Time taken for adding Objects at End: 125

List created using new Vector(500000):
Time taken for adding Objects at End: 109

List created using new LinkedList():
Time taken for adding Objects at End: 297

That means "push" action ratios like 3:10:1 (using your books ordering) for the size initialized array based lists and 2:5:1 if no size-initialization is used. (The "insert" actions increased linearly for LinkedList while the array based lists didn't finish even one such task in the 20 minutes I cared to wait for it.)

-- PEZ

This may be really simple question, but how do you create a linked list varible?(or any other ADT for that matter.) I havn't really done anything with Java in the past couple of years and don't remember. I'm still in C++ mode for the most part.(That's the language of choice of the university I'm attending.) In C++ it would be something like this

List <int> var;

Something like that, but if I recall it had something to do with the type being defined as an Object class so it made it really easy to create a varible. Something like instead of templates, just uses inheritance from Object class or something. In any case could someone show me the line of code creating a Linked list var or some other ADT?

-- CelticSwarm

In case you don't have the link, you should know about the [Java API Docs] for a lot of specific info about things. But to answer your question, it would be something like:

java.util.LinkedList _myLinkedList = new java.util.LinkedList();
// ...
_myLinkedList.add(new SomeClass(5));
SomeClass blah = (SomeClass)_myLinkedList.getFirst();

Or you could do "import java.util.*;" or "import java.util.LinkedList;" and then just use "LinkedList" as the class name in your code. -- Voidious

I know that when I transitioned from C++ to Java one of the first things I missed was pointers. There may be a LinkedList class, but I tend to just use private List widgets = new ArrayList();. Typical usage looks like

Iterator iterator = widgets.iterator();
while( iterator.hasNext() )
{
    widget = (Widget)iterator.next();
    widget.doSomething();
}

-- Martin

Hey Martin, is there any performance advantage to using the Iterator rather than just the get() method with an ArrayList? I don't think there is, but I don't remember. --wcsv

I don't know the answer to your question, wcsv, but there is a lot of discussion about collections and their speeds on the page ABCsLinkedListChallenge. I presently just use ArrayLists? without iterators (looping with .size() and .get(x)). -- Voidious

Thanks for the help fellas. I had forgotten about the API docs. -- CelticSwarm