aspose file tools*
The moose likes Java in General and the fly likes ArrayList vS linkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "ArrayList vS linkedList" Watch "ArrayList vS linkedList" New topic
Author

ArrayList vS linkedList

Saral Saxena
Ranch Hand

Joined: Apr 22, 2011
Posts: 202

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
Bartender

Joined: Sep 20, 2010
Posts: 3365
    
    9
First explain to us, in your own words, in what way the operation between these two types differs.
Saral Saxena
Ranch Hand

Joined: Apr 22, 2011
Posts: 202

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
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 13868
    
  10

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.

Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7029
    
  16

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


Isn't it funny how there's always time and money enough to do it WRONG?
Artlicles by Winston can be found here
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: ArrayList vS linkedList
 
Similar Threads
advantage Doublylink list over linklist
Arraylist and linklist !!
Cast LinkedList to ArrayList, enjoy the class cast exception
Arraylist or linked list
Find where the loop is in a doubly - linked list