Solved

ArrayList and LinkedList

Posted on 2011-09-07
6
503 Views
Last Modified: 2012-05-12
I would lie to now about ArrayList and LinkedList. when, how, where, why to use them, advantages, disadvantages of the implementations.

I read ArrayList insertion, deletion slow compared to LinkedList. Why is it so.
Also how to decide which one to use.

I was not clear on this concept. thanks in advance
0
Comment
Question by:gudii9
6 Comments
 
LVL 47

Expert Comment

by:for_yan
ID: 36495821
0
 
LVL 7

Expert Comment

by:rumi78
ID: 36498355
arraylist - internally array of objects - have to reserve array for all objects, get complexity O(1),

linkedlist - two directional pointer list (like in c language), does not reserve the whole array, however getting indexed object e.g. linkedlist.get(10) - starts from head and iterates elements to get 10th, getting complexity is O(n)
0
 
LVL 1

Assisted Solution

by:amirms
amirms earned 166 total points
ID: 36501081
ArrayList is an extended version of a normal array structure which provides more convenient functionality to programmers, but what happens underneath is quiet complex specially when it comes to adding and removing array elements. For example if you had created an arrayList of default size 10, and you add items to it, once you add the 11th item, Java creates a new array of size 11, moves the whole content of the first array to the latter and then adds the 11th item to it. So as you see it would take a long time for such procedure. Linked list does not suffer from such limitation as adding a new item simply puts the reference to it at the "next-item" pointer of its last item. Generally speaking, use ArrayList if limitted amount of adding and removing operations are performed and the number of elements rarely exceeds the default size, otherwise use linked lists.
0
DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

 
LVL 7

Accepted Solution

by:
rumi78 earned 167 total points
ID: 36512063
generally correct. However, when internal array exceeds size the new internal size is set to:
int newCapacity = oldCapacity + (oldCapacity >> 1); // newCapacity=oldCapacity*3;
and arraycopy is performed.
0
 
LVL 7

Author Comment

by:gudii9
ID: 36643525
what is O(1) and O(n). please elaborate on this
0
 
LVL 47

Assisted Solution

by:for_yan
for_yan earned 167 total points
ID: 36688738


O(1) means that the time required to do aclculation does not depend on number of elements
O(n) means time grows linearly with the number of elemnts

Read here about the deatils:


http://en.wikipedia.org/wiki/Time_complexity
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
eclipse java  build path 6 44
Basic Java Case or If-Else statement... 3 43
servlet  URL Rewriting 1 25
tomcat not starting 6 29
An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
The viewer will learn how to implement Singleton Design Pattern in Java.

912 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now