How does ArrayBuffer work in memory?
I want to use ArrayBuffer in my program to store a list of numbers. I want to use it as a queue. Remove the first item in the list each time and use it. Then I was wondering every time I remove the first element, all the other numbers in the queue change one place. Next time I can read item (0) again?
source to share
If you look at the Scala or ArrayBuffer source code , you will see the following implementation remove
:
/** Removes the element on a given index position. It takes time linear in
* the buffer size.
*
* @param n the index which refers to the first element to delete.
* @param count the number of elements to delete
* @throws Predef.IndexOutOfBoundsException if `n` is out of bounds.
*/
override def remove(n: Int, count: Int) {
require(count >= 0, "removing negative number of elements")
if (n < 0 || n > size0 - count) throw new IndexOutOfBoundsException(n.toString)
copy(n + count, n, size0 - (n + count))
reduceToSize(size0 - count)
}
This way the removed element will no longer be present in the array, but indeed the remover copies all the elements ("shifts" in your definition) and it will be slower for longer arrays.
source to share
ArrayBuffer
is basically an array that implements all the convenience methods of a Buffer
.
It works as you describe: if you remove an element, all other elements will be offset to "fill in the gap" and, as the document states, it can take a while, especially if you remove the first element:
Adding, updating, and random access all take constant time (amortized time). Prepends and remove are linear in buffer size.
Therefore, I would not recommend using it ArrayBuffer
as a queue.
Actually, the best option is your question: just useQueue
. It's designed to ... well, the queue!
source to share
Why aren't you using a queue in a queue? Java Queue
It has this nice method called poll () (fetches and removes the head of this queue, or returns null if this queue is empty.)
Don't you need what you need? It also performs better than Array's solution.
source to share
If you want to use an array-backed data structure (for example to determine battery life (cache) or storage (no next pointer), you may want to consider java.util.ArrayDeque
. This class effectively implements a circular array that resizes when full. Method poll()
(retrieve and removing the first element) is implemented by simply increasing the start offset
The downside is that although this class implements the interface java.util.Queue
, there is no implicit conversion to scala.collection.mutable.Queue
, so you cannot use Scala collection methods such as map
etc.
Note: Scala has no interface since version 2.11 Deque
, leave the implementation alone ArrayDeque
.
source to share