aspose file tools*
The moose likes Beginning Java and the fly likes Whak kind of array suits my needs better ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Whak kind of array suits my needs better ? " Watch "Whak kind of array suits my needs better ? " New topic
Author

Whak kind of array suits my needs better ?

Dave Jones
Ranch Hand

Joined: Feb 20, 2005
Posts: 77
Hello ranchers
I have a workung program, in it, I have an ArrayList that after I add x objects (strings in my case) I start removing an element before adding a new one (thus keeping the size of the array at x)


Now, a co-worker of mine says that there's supposed to be a better way to do this that to use an Arraylist, (and a queue is not a good option by what he says.)
Well, what can/should I use ?
Thanks
Jeff Albertson
Ranch Hand

Joined: Sep 16, 2005
Posts: 1780
remove(0) in ArrayList is implemented by shifting all the remaining elements,
so that may be what your coworker was pointing out. A LinkedList wouldn't have
this problem, but I don't know what other operations you are doing on
your list -- random access if O(N) on a linked list.

In a dimly-lit corner of my brain, I seem to have the words "circular queue"
lodged. I don't think there is an implementation of that in the j2se, but
it shouldn't be hard to whip up, if you feel like it.

On the other hand, is this really a time bottleneck, or are you just curious?


There is no emoticon for what I am feeling!
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

If you need to repeatedly delete the first element of the list, then java.util.LinkedList is a better option than ArrayList; deleting items from the beginning of an ArrayList is comparatively slow.

The catch is, then, that calling get() on a LinkedList is slow! So then you should only access the elements of the list through the Iterator returned by the iterator() method (or listIterator()). Furthermore, remove() calls get(), so you actually need to use Iterator's delete method to delete items, rather than calling remove on the list itself.

If you really need to call get(n), then which class to use depends on how frequently you'll call get() vs. how frequently you'll use remove(). If you remove infrequently, use ArrayList. If you remove as often as you get, then it's a wash.


[Jess in Action][AskingGoodQuestions]
Jeff Albertson
Ranch Hand

Joined: Sep 16, 2005
Posts: 1780
Originally posted by Ernest Friedman-Hill:
Furthermore, remove() calls get(), so you actually need to use Iterator's delete method to delete items, rather than calling remove on the list itself.


This refers to the remove(int) method. The no-argument remove() and removeFirst
methods are implemented efficiently, although they are not part of the List interface
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[Dave]: Whak kind of array suits my needs better ?

To be clear, this question is not about arrays - it's about Lists.

[EFH]: The catch is, then, that calling get() on a LinkedList is slow!

Not really - not if you're we're talking about the beginning or end of the list. The get() method requires time proportional to the distance from either end of the list (whichever is closer). So getting from the middle is slow (unless the list is short), but getting from the ends is quick. And yes, getFirst() and getLast() are even faster, but that difference is quite small. for most applications. I wouldn't bother using the LinkedList methods unless profiling told me that was really a bottleneck - I'd prefer to keep the standard List methods. Same for remove(0) vs. remove(), removeFirst() and removeLast() - the differences in performance are trivial.

Note that in JDK 5, LinkedList has been retrofitted to implement the new Queue interface. For this situation, from what we've seen in Dave's code, Queue is probably a better fit than List. And there are other implementations of Queue besides LinkedList. I'm not sure offhand which of these would be best, but I would think that using the Queue interface would give you better options than the List interface.

[Jeff]: In a dimly-lit corner of my brain, I seem to have the words "circular queue" lodged.

Yeah, that's probably a good choice here (especially based on the limit to the maximum size of the collection). I'm sure there are implementations floating around out there (not in J2SE but in 3rd-party libraries) - though I don't know any in particular to recommend them. And sure, it's possible to implement your own. But for the effort it would take to make it and test carefully and make sure it's really right, I'd certainly wait until I had an observable performance problem and I'd already tried all the existing options in the JDK.


"I'm not back." - Bill Harding, Twister
Tony Morris
Ranch Hand

Joined: Sep 24, 2003
Posts: 1608
Originally posted by Jim Yingst:
[Dave]: Whak kind of array suits my needs better ?

To be clear, this question is not about arrays - it's about Lists.

[EFH]: The catch is, then, that calling get() on a LinkedList is slow!

Not really - not if you're we're talking about the beginning or end of the list. The get() method requires time proportional to the distance from either end of the list (whichever is closer). So getting from the middle is slow (unless the list is short), but getting from the ends is quick. And yes, getFirst() and getLast() are even faster, but that difference is quite small. for most applications. I wouldn't bother using the LinkedList methods unless profiling told me that was really a bottleneck - I'd prefer to keep the standard List methods. Same for remove(0) vs. remove(), removeFirst() and removeLast() - the differences in performance are trivial.

Note that in JDK 5, LinkedList has been retrofitted to implement the new Queue interface. For this situation, from what we've seen in Dave's code, Queue is probably a better fit than List. And there are other implementations of Queue besides LinkedList. I'm not sure offhand which of these would be best, but I would think that using the Queue interface would give you better options than the List interface.

[Jeff]: In a dimly-lit corner of my brain, I seem to have the words "circular queue" lodged.

Yeah, that's probably a good choice here (especially based on the limit to the maximum size of the collection). I'm sure there are implementations floating around out there (not in J2SE but in 3rd-party libraries) - though I don't know any in particular to recommend them. And sure, it's possible to implement your own. But for the effort it would take to make it and test carefully and make sure it's really right, I'd certainly wait until I had an observable performance problem and I'd already tried all the existing options in the JDK.


Whether or not a queue implementation is "circular" is unimportant. What is important is that both a 'dequeue' and an 'enqueue' operation are O(1). This can be achieved with a "circular queue" (a single reference in the implementation), or many other ways, without affecting the client in any way. That LinkedList implements the Queue interface is pretty retarded (to point out the obvious), and I recommend against it, due to excessive (to an extreme) contract.

An ArrayList and a singly 'LinkedList' are at opposite ends of the spectrum, having alternating O(1)/O(n) seek versus insert. A doubly linked list (a reference held at the start and end) leaves its extreme to approach the ArrayList extreme, ever so slightly. One could have a "triply" linked list, that holds a reference to the centre of the list, which again, approaches the ArrayList (faster seek, slower average insertion). In fact, you could have n references in a "nly" linked list, which has approached the extreme of an ArrayList (O(1) seek, O(n) insertion)). In fact, you'd have a map. Why is this gradual performance trade-off not available to clients of the collections API (only two extremes)? Does anything smell fishy yet?

Rolling your own Queue is pretty simple, and in fact, I did so myself, because I became tired of Sun's inability to recognise that a Queue has 3, and only 3, operations; dequeue, enqueue, peek. Not any more, not ever. The arguments to permit "blocking on dequeue", fixed size, etc. do not validate the approach that has been taken by Sun.

http://www.contractualj.com/api/net/tmorris/adt/queue/Queue.html


Tony Morris
Java Q&A (FAQ, Trivia)
Dave Jones
Ranch Hand

Joined: Feb 20, 2005
Posts: 77
Thank you all
I understand now that I should have given more information.
Well, what the code segment does, is go over a file, reading each line, and add it (after checking that it's a line that needs to be added) to the list/queue , now the list size will normally be not more than 10, and the file may contain up tp 1000 lines (or even more)
once the list/queue is 'ready' I simply copy the information (once) and use it with another part of the program. so I use the get() not more that 10 times
and I use the remove(0) and add(str) many many times.

Although I've learnt plenty from your answers, I still don't really know what is better, so I guess I'll stick to the ArrayList and If I feel that there are performance problems, I will revise

Thanks again to all og you
Dave
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Whak kind of array suits my needs better ?