• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Array vs ArrayList  RSS feed

 
Greenhorn
Posts: 28
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
People say that ArrayLists are preferable to arrays because Arrays are immutable.

If you want to add an element to an array, you have to pretty much overwrite it with a new array which is one size larger containing the new entry.

Hence ArrayLists come in handy as they have the Add function which is more efficient as you don't have to use memory overwriting the ArrayList with a new ArrayList

However, looking into the makeup of ArrayList, it appears that the fundamental structure behind an ArrayList is in fact an array so in order to edit the ArrayList, you are editing an Array (on a deeper level)

Does this mean that an ArrayList is actually more inefficient than an array ?

Does the same logic apply to String and StringBuilder ?
 
Greenhorn
Posts: 27
Android Java Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
StringBuilder uses characters to manage the String and only builds a String if you invoke toString(). So the answer to that question is: To use a StringBuilder is much more efficient than using Strings.
How it looks like with Arrays and ArrayLists I don't know.
 
Bartender
Posts: 19731
92
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You cannot overwrite an array, precisely because arrays are immutable. You have to construct an entirely new array and populate it from the old one, after which you will presumably discard the original array. You can assign that array as a value to a variable formerly indicating the old array, but the old array remains until garbage-collected as a separate object from the new array.

An ArrayList (as far as I know) encapsulates an array (although it could just as easily employ an internal linked list) and automates this process so technically it would be "less efficient". But "efficiency" should not dictate your design. You can optimize code after it's well-designed, but if you optimize as part of the design, you'll often find it very expensive if you discover - as we often have - that the true inefficiencies are actually somewhere else.

So use an array if the size changes rarely, and an ArrayList if you need something that can grow (and shrink) flexibly.

As far as String, StringBuffer and StringBuilder go, the StringBuffer* and StringBuilder keep a working array that the string is assembled into piece by piece. Then when you invoke "toString" on it, they use the String constructor to build a (immutable) String and return it, after which you can either continue working with the current buffer data or clear it and start building a whole new string from scratch.

Because the StringBuilder (*hereafter assume I also mean StringBuffer) is actually using a buffer that's an array of Character, it is very efficient, since you're (well, actually the StringBuilder) just copying text into the array and keeping track of how many array elements are in use. If the working array is too small, it allocates a new one that's 150% the size of the old one, copies all the characters over and continues just as you would expand any other array.

You can make a StringBuilder even more efficient if you have a rough idea of how big the resulting String will be because you can define the size of the initial builder array as a constructor parameter. If I'm not mistaken, this defaults to a paltry 16 characters, so if I'm building lines of text averaging aroun 80 characters, I might construct a builder with about 100 characters and save it from having to run about a half-dozen expansion operations as it builds the first string.
 
Marshal
Posts: 60142
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have never thought of arrays as immutable; the only feature about them that is fixed is their capacity, as shown by their length field. All the other elements can be reassigned or manipulated at any time, except in one circumstance. I shall leave the OP to work out that that is.
The advantage of a List is that it changes its size automatically to match the number of elements, both added and removed. There is no risk of overrunning its size and getting nulls, as one could easily do with a plain simple array.
Actually, the code for adding elements to an ArrayList which already has sufficient spare capacity for more elements is very simple:-That isn't any sort of exact quote; you would have to look at the original source for that. In terms of execution speed that differs not at all from adding to a plain simple array, and the memory consumption of the ArrayList is but slightly greater. Count how many clock cycles you would require for that sort of code (I make it 3), and if you compare it with this sort of code:-...I think you will make it 3 clock cycles per iteration, too. So I think there is probably no significant difference in execution speed.

I know that a plain simple List is implicitly mutable, but if you look here and here, you will find there are five ways to create a List to return form a method, some of which are immutable. But the elements reserve the right to change their state.
 
Tim Holloway
Bartender
Posts: 19731
92
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I have never thought of arrays as immutable



The contents of an array are mutable. The "array" itself, meaning the object that holds those contents, is immutable. And a mathematician or physicist would point out that a Java "array" is mathematically speaking, a vector. Not to be confused with the Java class of the same (if differently-capitalized) name.

Campbell Ritchie wrote:The advantage of a List is that it changes its size automatically to match the number of elements, both added and removed.



Careful! List isn't a class, it's an interface. You can define List in lots of different ways, some of which are fixed-size (caches and queues often are). In fact, if you look at the JavaDocs for List, the add and remove methods are all labelled as optional!

Campbell Ritchie wrote:I think you will make it 3 clock cycles per iteration, too.



Clock cycles? In this day and age? Actually, once pipelining became standard, the idea of a CPU running instructions in strictly-predictable timing chunks went down the bog. Timing these days is as much about what instructions precede and follow the current one as the inherent  "cycle" time of an instruction. Several instructions are typically in the pipes simultaneously, and it becomes more of a probabalistic computation than the old "Add to accumulator takes 1.5 ms" of days of yore.

I'm a paranoid little critter, so I don't code "if ( size == capacity )", I code "if ( size >= capacity )". That way, if something has gotten out of sync internally, I can repair it instead of possibly throwing an unexpected exception.

Nitpicking aside, I'm blind this afternoon and can't figure out what your example is illustrating. But one last nit: an array can be (as you illustrated)  a vector of integers. But it can also be composed of any other type of primitive, such as byte, float, or char. OR it can be an array of a specified object class such as Strings or even ArrayLists. OR it can be an array of Object, which means simply any non-primitive type. Since you can have an array of class objects or an array of primitives, but not a mixed array of both.
 
Campbell Ritchie
Marshal
Posts: 60142
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:. . . The contents of an array are mutable. The "array" itself, meaning the object that holds those contents, is immutable.  . . . .

Point taken.
 
Bartender
Posts: 2180
46
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:An ArrayList (as far as I know) encapsulates an array (although it could just as easily employ an internal linked list)


So it would become a LinkedList.
 
Marshal
Posts: 6008
415
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tim Holloway wrote:The contents of an array are mutable. The "array" itself, meaning the object that holds those contents, is immutable.


I find it confusing to think that way.

If one things (and probably should) about the arrays as about the black box - it is mutable, since you can't guarantee its elements will be the same over the time.

Only one class which I definitely can think of as an immutable - is String class. Meaning once you created, you won't be able to modify it without constructing a new one.

[added]
Very similar concept I find of public static <T> List<T> asList(T... a)
for which JavaDocs say:


And I find this description well fitting to arrays too. "A fixed-size array..." (no mentioning about immutability).
 
Campbell Ritchie
Marshal
Posts: 60142
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
. . . except for a zero‑length array, which is totally immutable. What about Number and most of its subclasses being immutable? Though Joshua Bloch confesses to a nasty mistake about two of its subclasses.
If you create a List via Arrays#asList(T...), any immutability will depend on the T[] array created from the T... parameter being a local variable which goes out of scope leaving no reference to itself. If the array cannot be accessed to modify, then the List cannot be modified. Of course, if “immutable” means, “never able to change state,” that would be contingent on its elements being immutable themselves. That latter is an unavoidable problem with all Collections, Maps, arrays, etc., because it is not always possible to take defensive copies. If you look at my four ways to copy and return a List here, No 2 returns a read‑only copy of the List which reflects changes in the original, and No 4 returns a List in such a manner as to prohibit any change to the elements' identity. If you call set() add() or remove() you can expect an UnsupportedOperationException to be thrown.
 * * * * * * * * *
In the context of the original question, the advantages ArrayList (or more precisely java.util.ArrayList because there are other classes with a similar name) has over arrays include:-
  • 1: Automatic control of capacity and memory consumption, up to the maximum allowed by the heap space available.
  • 2: “Remembering” the insertion point for the add() method.
  • 3: Fully overridden equals(), toString(), and hashCode() methods.
  • 4: Java8 gave it sort(), forEach(), and stream() methods, too.
  • 5: You can create Lists of elements with <> in their name, which you are not supposed to do with arrays.
  • That makes it much easier to use than a plain array in most circumstances. There is a slight disadvantage in that Lists can't contain primitives, but boxing and unboxing conversions made that only a very minor problem. The only method which arrays have that is overridden from Object is clone(): see the Java® Language Specification.
     
    Liutauras Vilda
    Marshal
    Posts: 6008
    415
    BSD
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:Of course, if “immutable” means, “never able to change state,” that would be contingent on its elements being immutable themselves. That latter is an unavoidable problem with all Collection


    In Java 9 this concept is being called "unmodifiable", but not immutable. An example is static <E> List<E> of​(E... elements) - "Returns an unmodifiable list containing an arbitrary number of elements."

    From JavaDocs...
  • They are unmodifiable. Elements cannot be added, removed, or replaced. Calling any mutator method on the List will always cause UnsupportedOperationException to be thrown. However, if the contained elements are themselves mutable, this may cause the List's contents to appear to change.


  • An immutable to me is absolutely immutable, as in Racket language for instance, if you have created a list of something, that means you'll have such object and its contents for the entire its life. Any modifications need to be made by assembling completely new list - and that is I think very clear definition of immutability.
     
    Saloon Keeper
    Posts: 9239
    177
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I think an important benefit of a List versus an array has been overlooked: Lists are invariant, while arrays are covariant.

    This means that using a List prevents you from doing naive stuff like Animal[] animals = new Lion[10];

    Type checking is just way better with collections. You throw all of that out of the window when you use arrays.
     
    Tim Holloway
    Bartender
    Posts: 19731
    92
    Android Eclipse IDE Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Paweł Baczyński wrote:

    Tim Holloway wrote:An ArrayList (as far as I know) encapsulates an array (although it could just as easily employ an internal linked list)


    So it would become a LinkedList.



    Well, a LinkedList is a realization of the abstract concept of a linked list, so it's one way of internally implementing a logical vector using chained elements.

    Then again, I used a linked list as one possible internal implementation. Any sequential collection - whether implemented by a concrete Java class or simply via internal logic - would also do. Including variants, like having linked buckets of "b" value slots, doubly-linked list implementations, hash-indexed chunks, whatever.
     
    Campbell Ritchie
    Marshal
    Posts: 60142
    188
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Stephan van Hulst wrote:. . . . Lists are invariant, while arrays are covariant. . . . .

    Does that only apply if you supply an actual type parameter to the List? So...won't compile. There used to be a section in the Java™ Tutorials explaining how a Cage<Lion> differs from a Cage<Butterfly>.

    Liutauras Vilda wrote:. . . . In Java 9 this concept is being called "unmodifiable", but not immutable. . . . .

    Good term; I shall try to remember that.
     
    Tim Holloway
    Bartender
    Posts: 19731
    92
    Android Eclipse IDE Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:Does that only apply if you supply an actual type parameter to the List? So...won't compile.



    Are you sure? ArrayList is a subclass of List, presumably Lion is a subclass of Animal. It should be valid at both compile and run times to assign narrower types to more general ones, just not the other way around.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 9239
    177
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:Does that only apply if you supply an actual type parameter to the List?


    It applies if you don't use wildcards. When you're not using any type arguments¹ (a raw type), you can't speak of variance at all because there is nothing to vary. Even arrays have better type checking than raw collections:


    ¹ Type parameters are variables such as E, T, K, V. Type arguments are values like String, ? extends Number, ? super T.
     
    Stephan van Hulst
    Saloon Keeper
    Posts: 9239
    177
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Tim Holloway wrote:Are you sure? ArrayList is a subclass of List, presumably Lion is a subclass of Animal. It should be valid at both compile and run times to assign narrower types to more general ones, just not the other way around.


    It's not. Generic types without wildcards are invariant. ArrayList<Lion> is a subtype of List<Lion> and List<? extends Animal>. It's NOT a subtype of List<Animal> or even ArrayList<Animal>. Here's the usual example that illustrates why not:
     
    Campbell Ritchie
    Marshal
    Posts: 60142
    188
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Tim Holloway wrote:

    I wrote:. . ....won't compile.



    Are you sure? . . .

    Yes; I even tried it to confirm.

    jshell wrote:|  Error:
    |  incompatible types: java.util.ArrayList<Lion> cannot be converted to java.util.List<Animal>
    |  List<Animal> menagerie = new ArrayList<Lion>();

    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!