Solved

ArrayList and LinkedList

Posted on 2011-09-07
6
508 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

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
How can I   ajax html table  rows? 20 76
reverse digits of a number using for loop 5 45
String array comparison 4 34
mysql jsp example issue 32 38
I had a project requirement for a displaying a user workbench .This workbench would consist multiple data grids .In each grid the user will be able to see a large number of data. These data grids should allow the user to 1. Sort 2. Export the …
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
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…

822 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