File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes difference between linked list and array list? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "difference between linked list and array list?" Watch "difference between linked list and array list?" New topic
Author

difference between linked list and array list?

sasikumar srinivasan
Greenhorn

Joined: Aug 27, 2009
Posts: 4
What is the difference between array list and linked list?
manoj r patil
Ranch Hand

Joined: Jun 06, 2002
Posts: 181
Both are inherited from AbstractList. Linklist unlike Arraylist is much like a Queue.

Refer javadoc and you will get all the answers!


love your job and not your company;
...because you never know when your company will stop loving you!
Srikanth Chelemela
Greenhorn

Joined: Oct 23, 2009
Posts: 6
I will try to supply an answer for the LinkedList / ArrayList issue. The first thing to do is to look at what interfaces these two implement. This might hint us at their purpose, as Sun usually bound purposes into interfaces.


// lang java
public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Queue<E>, Cloneable, Serializable

We can ignore Cloneable and Serializable as all of the JCF implement those. It’s also quite obvious that both of them implement the List interface, as they need to provide list functionability (backwards iteration, sub listing, etc).

Now for the differences: ArrayList is implementing RandomAccess while LinkedList implementing Queue. You could already tell something about the usage of the two classes.
ArrayList

Now for some implementation notes. The ArrayList is actually encapsulating an actualy Array, an Object[]. When you instanciate ArrayList, an array is created, and when you add values into it, the array changes its size accordingly. This gives you strengths and weaknesses:

* Fast Random Access

You can perform random access without fearing for performence. Calling get(int) will just access the underlying array.
* Adding values might be slow When you don’t know the amount of values the array will contain when you create it, a lot of shifting is going to be done in the memory space when the ArrayList manipulates its internal array.
* Slow manipulation When you’ll want to add a value randomly inside the array, between two already existing values, the array will have to start moving all the values one spot to the right in order to let that happen.

LinkedList

The LinkedList is implemented using nodes linked to each other. Each node contains a previous node link, next node link, and value, which contains the actual data. When new data is inserted, a node is inserted and the links of the surrounding nodes are updated accordingly. When one is removed, the same happens – The surrounding nodes are changing their links and the deleted node is garbage collected. This, as well, gives strengths and weaknesses:

* Fast manipulation As you’d expect, adding and removing new data anywhere in the list is instantanious. Change two links, and you have a new value anywhere you want it.
* No random access Even though the get(int) is still there, it now just iterates the list until it reaches the index you specified. It has some optimizations in order to do that, but that’s basically it.

Some Conclusions

ArrayList is very useful when a well defined set of data is needed in a List interface as opposed to an array. It can be dynamically changed, but try not to do so frequently throughout the life of the application. LinkedList is there for you to do just that: Manipulating it is very easy, and as long as its used for iteration purposes only and not for random accessing, it’s the best solution. Further, if you need random accessing from time to time, I suggest toArray for that specific moment.

Another point I didn’t raise here is the Queue issue. LinkedList implements extended abilities to the normal List interface which allows it to add and remove elements from its beginning and end. This makes the LinkedList perfect for Queue and Stack purposes – Although in Java 5 they already added a Stack class


Embla Tingeling
Ranch Hand

Joined: Oct 22, 2009
Posts: 237
sasikumar srinivasan wrote:What is the difference between array list and linked list?


ArrayList is based on a static array, whereas LinkedList is based on a linked list. The properties of these data structures determine the differences.

In short,

* An ArrayList has fast random accesses (accesses using an index). A LinkedList has slow random accesses.

* An ArrayList has fast additions/removes at the end only. A LinkedList has fast additions/removes everywhere.

* Sequential scanning (using an iterations or a for_each loop) are equally fast.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

this topic already discussed many times here.please search



 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: difference between linked list and array list?