1

Possible Duplicate:
Size-limited queue that holds last N elements in Java
Java - Ring Buffer

I am interested in a bounded above queue, that whenever faced with object insertion, would remove the oldest object first, if the insertion would result in 'overflowing'. I want the addition to be O(1) and the memory usage as little as possible. I was thinking about either overriding add method on LinkedList, but ideally I would implement a circular, array based list, with catching front/back pointer. Whenever the addition is made over capacity, front pointer advances, and then the back one. Is there an implementation similar to this?

Community
  • 1
  • 1
Bober02
  • 15,034
  • 31
  • 92
  • 178
  • 1
    You could use CircullarFifoBuffer similar answer is [enter link description here][1]. [1]: http://stackoverflow.com/questions/5498865/size-limited-queue-that-holds-last-n-elements-in-java –  Dec 05 '12 at 20:24
  • That can be achieved with a circular/ring buffer. – Anders R. Bystrup Dec 05 '12 at 20:24
  • http://stackoverflow.com/questions/3742168/can-i-use-java-util-linkedlist-to-construct-a-circular-cyclic-linked-list – Cratylus Dec 05 '12 at 20:30

1 Answers1

-1

A linked list is a waste of memory, since the next pointer uses mem, that the ArrayList does not.

The performant implementations are based on ArrayList or better on an array. If your circular buffer size is fixed, you would use an array.

I implemented a circular buffer using an internal array, with start and end position index vars. I did not found an implemnetation of a circular list / buffer, that did that what i wanted.

It was not dificullt to implement, but i recomend using a high number of unit test cases, to prove that your circ buffer works as expected.

AlexWien
  • 28,470
  • 6
  • 53
  • 83
  • A word of caution about `ArrayList`: at least the OpenJDK implementation is not based on a circular array: removing an item - any item - results in a partial copy of the internal array. Removing the *first* item actually shifts *all* remaining elements - definitely not something you want to be doing very often... – thkala Dec 05 '12 at 20:52
  • That depends on the type of circular buffer: Deleting from the middle is rarly needed. usually you add only to the buffer. The oldest elements are overwrittem with the new ones. Only the start and the pos has to be correctly maintained. Removing from front should also work by just moving the curStat index. Shifting in an array with memcopy is far faster then reasigning two pointers, even if that are 100000 elements. That are situation where the Big O notation is useless, when you dont consider the pre factor. – AlexWien Dec 05 '12 at 21:00
  • 1. *"Shifting in an array with memcopy is far faster then reasigning two pointers"*: Would you mind qualifying this statement, because to me it does not make any sense. 2. As I said, `ArrayList` typically does *not* use a circular buffer internally - you could use it as a glorified array and maintain your own indexes, I suppose, but then why not use a primitive array directly? `ArrayDeque` on the other hand *does* use a circular array *but* IIRC it does not implement the `List` interface, which is a pity... – thkala Dec 05 '12 at 21:08
  • Yes i wrote that using an Array is best. But when the max Buffer Size can dynamically change, then One has to think further. In These Cases the Arraylist Could be less Programming work. – AlexWien Dec 05 '12 at 21:13
  • @thkala ArrayList never is based oj circular arrays. Where did you get that from? – AlexWien Dec 05 '12 at 21:34
  • Where did I get what? The fact that `ArrayList` is horribly inefficient when used as a FIFO? – thkala Dec 05 '12 at 21:43