Solved

ArrayList and LinkedList

Posted on 2011-09-07
6
516 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

How Do You Stack Up Against Your Peers?

With today’s modern enterprise so dependent on digital infrastructures, the impact of major incidents has increased dramatically. Grab the report now to gain insight into how your organization ranks against your peers and learn best-in-class strategies to resolve incidents.

Question has a verified solution.

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

Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

724 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