Solved

Regarding LinkedList and ArrayList

Posted on 2011-09-19
5
289 Views
Last Modified: 2012-08-14
Hi Friends,
Recently I saw one article regarding list implementations i.e  For LinkedList get is O(n) and
For ArrayList get is O(1) please explain the difference between them?
0
Comment
Question by:PrakashVarma
  • 4
5 Comments
 
LVL 4

Expert Comment

by:reijnemans
ID: 36558660
0
 
LVL 47

Accepted Solution

by:
for_yan earned 500 total points
ID: 36558864
In LinkedList in order to get to element number n you need to traverse other elements - therefore the longer the list the more time t takes to get to element with certain number
This means O(m) - the time is proportional to the number of elements

In the ArrayList you just calculate where is your element with the number n and immediately go there - therefore the
time to get to certain element does not dpend on the length of the list - this means O(1) - the time is constant - indpendent of the numebr of elements

 
0
 
LVL 47

Expert Comment

by:for_yan
ID: 36558870

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

about time complexity of algrorithms in computation
0
 
LVL 47

Assisted Solution

by:for_yan
for_yan earned 500 total points
ID: 36558887

Imagine say list of elements where each element tells you where is the next element - the longer will be such lsit the more time on average you would need
to get to sertain element

 On the other hand imagine list of elements which has an index which tells where is the location of each elemet - then by number of element
you can calculate where is the address of particular element and no matter how long is the list this calculation will take the same time

This is analogy which corresponds to LinkedLst and ArrayList
 
0
 
LVL 47

Assisted Solution

by:for_yan
for_yan earned 500 total points
ID: 36558903
On the other hand if you want to insert element into certain position - in case of ArrayList you'll have to
shift all elements say upwards to make the space for the new element - so the longer list you have it will take longer time

In LinkedList you just need to chenge the pointers of two neighboring elements and the time it takes to insert
element into any pposition will be the same.

Therefore if you have really long lists where most of the time you need to insert new elements
then you want to use linkedlist . If you have long lists and you populate it just once and then you want
mostly to read elements - then ArrayList would be more efficient.

Of course if lists are short - then all of it is not so much relevant, but when you get in many thousads of elements
then it becomes significant
 
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
Application launch issue with Apache Tomcat 5 21
bitbucket vs gitbucket 3 57
web services creation SOAP vs REST 5 20
servlet example issue 6 30
Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

910 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

23 Experts available now in Live!

Get 1:1 Help Now