Doesn't it have to count every element in the array? Thus, not a constant number of operations, so O(n)?
7
-
What kind of array? fixed-size arrays have … well, a fixed size. You don't even need to get its size, you already know it. Variable-sized arrays know their size always.Jörg W Mittag– Jörg W Mittag2017-10-21 16:52:30 +00:00Commented Oct 21, 2017 at 16:52
-
1Java stores the length of the array in a final field, so it just reads that one value. Constant time.markspace– markspace2017-10-21 16:54:28 +00:00Commented Oct 21, 2017 at 16:54
-
1Java has fixed-size arrays. An array cannot change its size. Even if an array is variable-size, you can store the size inside the array and just get it out.Jörg W Mittag– Jörg W Mittag2017-10-21 16:54:37 +00:00Commented Oct 21, 2017 at 16:54
-
2Not sure why the downvotes, the question is valid.everag– everag2017-10-21 17:04:54 +00:00Commented Oct 21, 2017 at 17:04
-
1@Everton perceived lack of research, most likely (not that I have downvoted).Andy Turner– Andy Turner2017-10-21 17:17:46 +00:00Commented Oct 21, 2017 at 17:17
|
Show 2 more comments
3 Answers
No, Java arrays have a length property that stores their length (i.e. every arrays knows its own length). No counting is necessary.
5 Comments
melpomene
@everton I'm not sure what you mean by "API code". It's mentioned in docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html.
Andy Turner
@everton it isn't part of the API doc: it is in the language spec docs.oracle.com/javase/specs/jls/se8/html/jls-10.html#jls-10.7
everag
I meant API doc, sorry! But thanks for sharing anyway :)
shivam
@melpomene : can i say like if i am having an array of int(say 4 byte) with having 10 elements.In that case in Memory occupied by the array will be 44 byte (4*10 byte for elements and 4 byte for length variable)
JB Nizet
@shivam no, it's more than that, because arrays are objects, and objects have additional overhead (needed to store their type, their synchronization monitor, their GC information, etc.
Consider if you were writing a programming language, and you have to implement an array type. How would you do that?
Clearly, you would need to know how much memory you need to store the array. It follows that you would probably like to keep track of that somehow.
Thus, in all languages that have arrays, the number of elements in the array is also stored as part of the array. Knowing the length of the array is nothing more than looking at the length value, an O(1) operation.
C and C++ are special.
They treat pointers and arrays with near-identical syntax. What this means is that if you treat an actual array as a pointer, you lose the size information.
But even if you don’t, it is convenient for storing things like character strings, which can vary in length. The old C-style way to mark the end of a string is to use the character with zero value, the null character.
So to find the end of a C-string, no matter how large the array containing it is, you must count through all the characters until you find the one with a value of zero, an O(n) operation.
This is not the same as not knowing the length of the containing array.
It can be, and often is when dealing with C-strings, that access to a string array does not come with knowledge of the size of the array containing the string, because of the already-mentioned issue where arrays degenerate into pointers so easily.
So to answer your question, it kind of depends on what you mean by “array”. If you are talking about some open sequence, such as a character device or pipe, then yes, you must have some way of determining when you have encountered the last element or not. But for arrays proper, then no, the size of the array is an integral part of its type.
Comments
Hm..? Are you a C developer?
int[] arr = new int[500];
System.out.println(arr.length); //Prints 500
1 Comment
Curious Learner
Is this best practice?