Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

LinkedList vs ArrayList

 
 
Patricia Shanahan
Guest
Posts: n/a
 
      04-11-2006
Vanessa Berni wrote:
> 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


Depending on details of what you are doing, consider alternatives such
as one or more HashMap instances. It depends partly on a tradeoff
between time, code complexity, and space.

You could get the equivalent of your access by index with a HashMap that
maps Integer to your objects. Keep track of the index of the lowest and
highest index elements. To insert or delete at head or tail, both do the
put or remove, and also adjust the lowest or highest index value.

To access by value fast, keep the reverse map, object to Integer. You
can do O(1) access by value, and keep the first map consistent only
accessing it by Integer key.

Essentially, turn EVERYTHING into key-based access to a HashMap, and it
is all O(1).

Patricia

 
Reply With Quote
 
 
 
 
Ben
Guest
Posts: n/a
 
      04-11-2006
Vanessa Berni wrote:
> 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
>


in a TreeSet you don't have a method like the .get(i) of the arrayList.
Instead the TreeSet provides you with an iterator that will allow you to
step through and find the object that you want. Look at the Java API for
more specific information :

http://java.sun.com/j2se/1.3/docs/ap...l/TreeSet.html

Ben
 
Reply With Quote
 
 
 
 
Vanessa Berni
Guest
Posts: n/a
 
      04-11-2006
> 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.


The problem of removing from the front of the ArrayList is that the array
will be "resized and re-indexed" and so it costs O(n)? Isn't it?

If I had a pointer at the start won't it be resized?

Vanessa


 
Reply With Quote
 
Thomas Hawtin
Guest
Posts: n/a
 
      04-11-2006
Vanessa Berni wrote:
>
> The problem of removing from the front of the ArrayList is that the array
> will be "resized and re-indexed" and so it costs O(n)? Isn't it?


O(n) but by a tiny factor. It's just a System.arraycopy.

LinkedList.get is also an O(n) operation, but probably with a slightly
larger factor.

Tom Hawtin
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      04-11-2006
Hendrik Maryns wrote:

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


Actually I found out in another project that it's also faster if you do
a lot of iterating. Probably because of the array bounds checks in
ArrayList.

Kind regards

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

Vanessa Berni schreef:
>> 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.

>
> The problem of removing from the front of the ArrayList is that the array
> will be "resized and re-indexed" and so it costs O(n)? Isn't it?


Indeed.

> If I had a pointer at the start won't it be resized?


I wrote /re/-implement. Have a look at the source code of ArrayList.
Then instead of only the size int, which is in fact a pointer to the end
of the list, have a start and end pointer, which indicate which part of
the array is used. Of course you’ll have to consider how to add an
element in the middle...

This is basically the CyclicArrayList Tom Hawtin writes about.

You could also keep two ArrayLists, one for the last half in normal
order, one for the first half in reversed order. Then insertion and
deletion at the beginning is cheap, but you have to deal with the case
your front list gets empty and such.

H.
- --
Hendrik Maryns

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

iD8DBQFEO9KNe+7xMGD3itQRAj0uAJ9xt5mnYZGENCwrIEZpjh RxNvLJ+wCfajnk
pWOsjY1OVmduCHFXUkcb7dw=
=Yzz2
-----END PGP SIGNATURE-----
 
Reply With Quote
 
Dimitri Maziuk
Guest
Posts: n/a
 
      04-11-2006
Vanessa Berni sez:
> In this way It will cost me O(i) every time ....


So will LinkedList.get( i ), the $15 question is how long it
will take on a real CPU with a real list. OTGH, there's only
one way to resize an array: create a new larger (or smaller)
one and copy elements. Every resize of an ArrayList requires
2x the memory -- dep. on the size of your list, this may be
a bigger concern than time.

If you know the number of elements in advance, you can avoid
resizing (delete by setting element to null) and have O(1)
indexed access with an array(List). Other options include a
map with orig. index as a key (requires extra memory for
Integer keys) for storage, or a list for storage and a map
for index.

Dima
--
Q276304 - Error Message: Your Password Must Be at Least 18770 Characters
and Cannot Repeat Any of Your Previous 30689 Passwords -- RISKS 21.37
 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      04-11-2006

"Vanessa Berni" <(E-Mail Removed)> wrote in message
news:AmP_f.78608$(E-Mail Removed)...
> 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?


What you want is a random access List-like structure that has both negative
and positive indices, and where both start and end index can chance.
Operations at the head increment and decrement the start index, operations
at the tail increment and decrement the end index. This can easily be built
using two ArrayLists, one for the negative indices and one for the
non-negative. You'll need to keep track of the current start and end
indices. You'll also need to keep track of the current actual sizes of the
ArrayLists, so that you know whether an insert at the head (or tail) is a
set() or an add().


 
Reply With Quote
 
Vanessa Berni
Guest
Posts: n/a
 
      04-12-2006
I've been thinking about all the operation I have to do with my set andf
I've found out that

1) I've to read all the elements (in order) : I can do it with a
listiterator
2) Given the current element (pointed by the listIterator) (i-th element) I
have to find the previous element (that is NOT necessarly (i-1))
3) Given the current element (pointed by the listIterator) (i-th element) I
have to find the next element (that is NOT necessarly (i+1))
4) I've to do some operation with the 3 elements (modify the current
element)
5) I've to move "up" or "down" the current element

I think that, in this case, the best solution would be a LinkedList.
I'm not able to execute operations 2) and 3).

I'd like to create 2 new listIterator "cloning" the one I have that points
to the current element.
With the first I will execute operation 2 and with the other operation 3.

//pseudo code
ListIterator curr=myset.listIterator();
while(curr.hasNext()){
//get element
MyObject obj=(MyObject)curr.next();

//create listIterator
ListIterator findPrec=curr;
ListIterator findNext=curr;

//find previous element moving findPrec
!!!! if I move findPrec I'll move also findNext and curr

//find previous element moving findNext
!!!! if I move findNext I'll move also findPrec and curr
}

Is there a way to do what I want to?

Thanks
Vanessa


"Vanessa Berni" <(E-Mail Removed)> ha scritto nel messaggio
news:AmP_f.78608$(E-Mail Removed)...
> 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
 
Thomas Hawtin
Guest
Posts: n/a
 
      04-12-2006
Vanessa Berni wrote:
>
> I'd like to create 2 new listIterator "cloning" the one I have that points
> to the current element.


If you use the iterators to modify the list, then you'll get into
trouble with ConcurrentModificationException.

Possibly there is a better data structure, but it depend upon the
details of what you are trying to do. Or possibly if you suck it and
see, ArrayList will turn out to be fast enough. There's not much point
in optimising something that performs sufficiently well.

Tom Hawtin
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
 
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