Solved

ArrayList and LinkedList

Posted on 2011-09-07
6
514 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
MS Dynamics Made Instantly Simpler

Make Your Microsoft Dynamics Investment Count  & Drastically Decrease Training Time by Providing Intuitive Step-By-Step WalkThru Tutorials.

 
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

Revamp Your Training Process

Drastically shorten your training time with WalkMe's advanced online training solution that Guides your trainees to action.

Question has a verified solution.

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

Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
The viewer will learn how to implement Singleton Design Pattern in Java.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Suggested Courses

737 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