LinkedList vs ArrayList

[Thomas Hawtin]

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

 

[Vanessa Berni]

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

 

[Ben]

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

 

[Vanessa Berni]

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

 

[Patricia Shanahan]

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

 

[Fahd Shariff]

If you really want to "get the i-th element" use an iterator and call
its next() method i times.

 

[Vanessa Berni]

Sometimes by vakue and sometime by index.

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

Patricia

 

[Hendrik Maryns]

-----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+jmBYTG8AXvcDQCfdNx6
pClxCmp6EoTWhRXFoqoNvSY=
=1Y1t
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Ben schreef:

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+7xMGD3itQRAhhSAKCCXz1Xj1gAZ3979PwpgBP2X/J5RwCdG5bS
GADhdO7f9C6pV46Si2j7cCU=
=HKnQ
-----END PGP SIGNATURE-----

 

[Vanessa Berni]

In this way It will cost me O(i) every time ....

 

[Patricia Shanahan]

Sometimes by vakue and sometime by index.

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

 

[Ben]

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/api/java/util/TreeSet.html

Ben

 

[Vanessa Berni]

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

 

[Thomas Hawtin]

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

 

[Robert Klemme]

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

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Vanessa Berni schreef:

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+7xMGD3itQRAj0uAJ9xt5mnYZGENCwrIEZpjhRxNvLJ+wCfajnk
pWOsjY1OVmduCHFXUkcb7dw=
=Yzz2
-----END PGP SIGNATURE-----

 

[Dimitri Maziuk]

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

 

[Mike Schilling]

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().

 

[Vanessa Berni]

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

 

[Thomas Hawtin]

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