Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > LinkedList vs ArrayList

Reply
Thread Tools

LinkedList vs ArrayList

 
 
Thomas Hawtin
Guest
Posts: n/a
 
      04-11-2006
Vanessa Berni wrote:
> I'ev a big problem. I've a program that handles with a orded set of object.
> With this objects I've to
>
> a)execute a LOT of random access
> b) insert/remove from head and tail (not so frequently as the number of
> operation (a) )
>
> Do I have to use an ArrayList o LinkedList?


Suck it and see.

You should find a long LinkedList is absolutely terrible for random access.

Unfortunately ArrayList isn't cyclic, removing from the head will cost.
It probably wont cost as much as a random access on a long LinkedList.
Removing from the head of an array list, just involves a block move of
pointers. Making your way through a linked list involves accessing large
amounts of memory (whether randomly or sequentially will likely depend
upon GC algorithm).

If you do lots of inserts/removes on heads and tails separately, perhaps
you could get away with reversing the list from time to time or
inserting/removing a block at a time.

For small lists, you may find different results apply.

You might be able to find a CyclicArrayList implementation somewhere (or
write your own if it is important). Java 1.6 will have Deque and in
particular ArrayDeque, unfortunately neither support random access.

Tom Hawtin
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
 
Reply With Quote
 
 
 
 
Vanessa Berni
Guest
Posts: n/a
 
      04-11-2006
Hi all,
I'ev a big problem. I've a program that handles with a orded set of object.
With this objects I've to

a)execute a LOT of random access
b) insert/remove from head and tail (not so frequently as the number of
operation (a) )

Do I have to use an ArrayList o LinkedList?

Grazie mille
Vanessa


 
Reply With Quote
 
 
 
 
Ben
Guest
Posts: n/a
 
      04-11-2006
Vanessa Berni wrote:
> Hi all,
> I'ev a big problem. I've a program that handles with a orded set of object.
> With this objects I've to
>
> a)execute a LOT of random access
> b) insert/remove from head and tail (not so frequently as the number of
> operation (a) )
>
> Do I have to use an ArrayList o LinkedList?
>
> Grazie mille
> Vanessa
>
>


For a lot of random access, it's actually better to use the
java.util.TreeSet especially since you specified an ordered set.

LinkedList are better when you don't have an order or a set.
and ArrayList when you are more worried about the adding execution time.

Ben
 
Reply With Quote
 
Vanessa Berni
Guest
Posts: n/a
 
      04-11-2006
Hi,
thank you for your help.
How do I get the i-th element from a treeset (the equivalent of
ArrayList.get(i))??

Thank you
Vanessa

"Ben" <(E-Mail Removed)> ha scritto nel messaggio
news:e1ggmi$dcg$(E-Mail Removed)...
> Vanessa Berni wrote:
>> Hi all,
>> I'ev a big problem. I've a program that handles with a orded set of
>> object.
>> With this objects I've to
>>
>> a)execute a LOT of random access
>> b) insert/remove from head and tail (not so frequently as the number of
>> operation (a) )
>>
>> Do I have to use an ArrayList o LinkedList?
>>
>> Grazie mille
>> Vanessa
>>
>>

>
> For a lot of random access, it's actually better to use the
> java.util.TreeSet especially since you specified an ordered set.
>
> LinkedList are better when you don't have an order or a set.
> and ArrayList when you are more worried about the adding execution time.
>
> Ben



 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      04-11-2006
Vanessa Berni wrote:
> Hi all,
> I'ev a big problem. I've a program that handles with a orded set of object.
> With this objects I've to
>
> a)execute a LOT of random access
> b) insert/remove from head and tail (not so frequently as the number of
> operation (a) )
>
> Do I have to use an ArrayList o LinkedList?
>
> Grazie mille
> Vanessa
>
>


When you do your random access, how do you select the element? By value,
or by index?

Patricia
 
Reply With Quote
 
Fahd Shariff
Guest
Posts: n/a
 
      04-11-2006
If you really want to "get the i-th element" use an iterator and call
its next() method i times.

--
Fahd Shariff
http://www.fahdshariff.cjb.net

 
Reply With Quote
 
Vanessa Berni
Guest
Posts: n/a
 
      04-11-2006
Sometimes by vakue and sometime by index.


"Patricia Shanahan" <(E-Mail Removed)> ha scritto nel messaggio
news:SQP_f.1407$(E-Mail Removed) ink.net...
> Vanessa Berni wrote:
>> Hi all,
>> I'ev a big problem. I've a program that handles with a orded set of
>> object.
>> With this objects I've to
>>
>> a)execute a LOT of random access
>> b) insert/remove from head and tail (not so frequently as the number of
>> operation (a) )
>>
>> Do I have to use an ArrayList o LinkedList?
>>
>> Grazie mille
>> Vanessa
>>
>>

>
> When you do your random access, how do you select the element? By value,
> or by index?
>
> Patricia



 
Reply With Quote
 
Hendrik Maryns
Guest
Posts: n/a
 
      04-11-2006
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Vanessa Berni schreef:
> Hi,
> thank you for your help.
> How do I get the i-th element from a treeset (the equivalent of
> ArrayList.get(i))??


You can’t, but there is of course an iterator, and if that doesn’t
suffice, there is tailset(element).first().

But did you mean by ordered that you elements are ordered, or that they
induce an ordering? Only in the latter case is a TreeMap interesting.

If you do only adding and deleting at the end, then ArrayList is
perfect, if you need insertion and deletion at the front, you could
consider re-implementing ArrayList with a start and end pointer, instead
of only the end pointer, as it is now.

LinkedList is only interesting if you want to insert elements in the middle.

H.
- --
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEO8p5e+7xMGD3itQRAgjvAJ0X9jlFvFGPyu40+jmBYT G8AXvcDQCfdNx6
pClxCmp6EoTWhRXFoqoNvSY=
=1Y1t
-----END PGP SIGNATURE-----
 
Reply With Quote
 
Hendrik Maryns
Guest
Posts: n/a
 
      04-11-2006
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Ben schreef:
> Vanessa Berni wrote:
>> Hi all,
>> I'ev a big problem. I've a program that handles with a orded set of
>> object.
>> With this objects I've to
>>
>> a)execute a LOT of random access
>> b) insert/remove from head and tail (not so frequently as the number
>> of operation (a) )
>>
>> Do I have to use an ArrayList o LinkedList?
>>
>> Grazie mille
>> Vanessa
>>
>>

>
> For a lot of random access, it's actually better to use the
> java.util.TreeSet especially since you specified an ordered set.
>
> LinkedList are better when you don't have an order or a set.
> and ArrayList when you are more worried about the adding execution time.


You did mean the inverse, right?
H.
- --
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEO8qfe+7xMGD3itQRAhhSAKCCXz1Xj1gAZ3979PwpgB P2X/J5RwCdG5bS
GADhdO7f9C6pV46Si2j7cCU=
=HKnQ
-----END PGP SIGNATURE-----
 
Reply With Quote
 
Vanessa Berni
Guest
Posts: n/a
 
      04-11-2006
In this way It will cost me O(i) every time ....

"Fahd Shariff" <(E-Mail Removed)> ha scritto nel messaggio
news:(E-Mail Removed) oups.com...
> If you really want to "get the i-th element" use an iterator and call
> its next() method i times.
>
> --
> Fahd Shariff
> http://www.fahdshariff.cjb.net
>



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
compare LinkedList with ArrayList and Vector Amit Jain Java 8 10-03-2007 03:24 AM
Does the clone() method of ArrayList<> make a copy of the objects in the ArrayList? xz Java 16 08-04-2007 10:33 PM
a class inherited from ArrayList, is saved to ViewState, why the type of the object read from ViewSate is not the class, but the parent, ArrayList leal ting ASP .Net 1 02-10-2004 07:45 PM
writeObject with ArrayList of ArrayList? Kaidi Java 4 01-03-2004 08:16 PM
Iterate through ArrayList using an another ArrayList Saravanan Rathinavelu ASP .Net 3 08-19-2003 07:03 AM



Advertisments