?
Solved

ArrayList and LinkedList

Posted on 2011-09-07
6
Medium Priority
?
523 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 664 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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 7

Accepted Solution

by:
rumi78 earned 668 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 668 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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

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…
In this post we will learn different types of Android Layout and some basics of an Android App.
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
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:
Suggested Courses
Course of the Month13 days, 14 hours left to enroll

807 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