ArrayList vS linkedList

[Saral Saxena]

Hi Guys,
Can you tell me on which the better searching can be done , it is the array list or linked list ...? and suppose I have to insert an item which is better option arraylist or linked list..? I know this question is being put up many times but I want an detail one result which can justfied the explnation..?

[Stephan van Hulst]

First explain to us, in your own words, in what way the operation between these two types differs.

[Saral Saxena]

Stephan van Hulst wrote:First explain to us, in your own words, in what way the operation between these two types differs.

What I have discovered that In a LinkedList, each element is linked to its previous and next element making it easier to delete or insert in the middle of the list. A ArrayList is more as its name subjects used as an array.Performance is similar, though LinkedList is optimized when inserting elements before the end of the list, where ArrayList is optimized when adding elements at the end. But can you guys give me a justfied anwer which will prove my point..!!

[Jesper de Jong]

You have the basic idea right: in a linked list, the list consist of nodes, each of which holds an element of the list and a reference to the next node (and also the previous node, if it is a doubly-linked list); in an array list, the list holds its elements in an array (contiguously in memory).

Because of these different ways that the elements are stored, operations that you can do on the list have different performance characteristics.

For example, if you want to get element number X in a linked list, you have to start at the beginning of the linked list, and walk over the nodes until you get to element X. In an ArrayList, you can immediately find element number X - you don't need to walk over elements 0, 1, 2, ... because in an ArrayList you know that element X is at position X * N (where N is the size of an element in the array). So, for finding an element by index, an ArrayList is much more efficient than a LinkedList.

On the other hand, if you want to insert a new element at position X in a LinkedList, all you have to do is make element X - 1 point to the new element as its next element, and make the new element point to the old element X as its next element. In an ArrayList, you would have to shift all elements in the array by 1 position (which means moving a large amount of data, if the list is large) to make room for the new element at position X. So, for inserting an element somewhere in the middle of the list, a LinkedList is much more efficient than an ArrayList.

It's important to understand these differences when choosing whether to use a LinkedList or an ArrayList. Which one will be more efficient for your particular application depends on what operations your application needs to do with the list. So, find out what your application needs to do with the list, and then study whether those operations are more efficient on a LinkedList or on an ArrayList.

It would be an interesting exercise to make two versions of your program: one with a LinkedList and one with an ArrayList, and compare their performance.

[Winston Gutkowski]

Jesper de Jong wrote:...if you want to get element number X in a linked list, you have to start at the beginning of the linked list, and walk over the nodes until you get to element X. In an ArrayList, you can immediately find element number X - you don't need to walk over elements 0, 1, 2, ... because in an ArrayList you know that element X is at position X * N (where N is the size of an element in the array). So, for finding an element by index, an ArrayList is much more efficient than a LinkedList....

@Saral: Further to what Jesper said: there is an interface that a surprising number of even quite experienced Java programmers forget about called RandomAccess.
It is a "marker" interface (ie, it has no methods - like java.lang.Cloneable) that is supposed to indicate whether a List has good "random" (ie, direct) access to elements via their index.

You will notice that ArrayList implements it, and LinkedList doesn't, which is an indicator of precisely what Jesper was talking about; and you should remember to add it (or not) for any List class that you create too.

Winston