36

Most of the assignments in my school for the initial programming classes required me to use arrays. I work full time now, and I never used an array for any project that I have worked on. Even in the exisiting projects I never saw the use of arrays anywhere. In my opinion, List is easier to use and is a standard. Why do professors tell students to use arrays in their assignments? Is it just so that students understand the basics?

Since most of the universities teach Java, this question is specific to Java.

  • 7
    Arrays are more fundamental. – user253751 Mar 11 '15 at 6:30
  • Comments are not for extended discussion; this conversation has been moved to chat. – World Engineer Mar 14 '15 at 16:59
120

Because arrays teach concepts like indexing and bounds, two fundamentally important concepts in computer programming.

Lists are not a "standard." There is a wide variety of problem spaces for which arrays are a perfect fit.

48

They probably wanted to start with the data structure that most accurately represents how a computer works, so you're familiar with the fundamentals before they start introducing higher-level abstractions like Lists which make it easier to work with. Otherwise you'd have no way of understanding why a certain structure or algorithm is slow/fast for some operations and not others; if computer memory was actually made out of linked lists the world would be a very different place.

For much the same reason, my first programming class at college was in C, and the rest of the classes were all in C++, Java and other languages. It's not that C is somehow better or easier, it's that C (and Array) hides nothing from you.

  • 7
    A list is easier to work with in real code, but an array is easier to (completely) understand, and more important to understand since they're fundamental and universal, while (Java's) List is not. At least that's my opinion. – Ixrec Mar 11 '15 at 0:25
  • 21
    An assignment in which you store stuff in an array and access it later is a data structure assignment. You just may not have realized it. You have to ask yourself, what produces better engineers, understanding the basic computational models, or learning a language's standard library? The general concensus (and I agree, fwiw) is that you won't understand a lot of the library contents without first understanding the basics of computation. – Kent A. Mar 11 '15 at 0:29
  • 12
    LinkedList, ArrayList, OrderedList, etc. Which list should you learn first? How would you appreciate what they do for you if you don't understand why they exist in the first place? – Kent A. Mar 11 '15 at 0:31
  • 10
    +1 to @KentAnderson. Schools must produce engineers who understand data structures at a low level; ideally, producing engineers who can easily implement the basic structures in C. Any other program is merely a JavaSchool. – Christian Willman Mar 11 '15 at 2:44
  • 2
    "They probably wanted to start with the data structure that most accurately represents how a computer works" – So, what about computers with list-structured or object-structured memory? "It's not that C is somehow better or easier, it's that C (and Array) hides nothing from you." – Unless your computer doesn't have pointers, like the AS/400, where C essentially runs in a VM and hides pretty much everything for you. – Jörg W Mittag Mar 12 '15 at 7:59
21

The answers above are great, but I have another in mind. Java's main() method means that students encounter basic arrays very early on, often as soon as the first day of class. Why?

public static void main(String[] args)

It's the first thing you're going to have to deal with to write Hello World and beyond. (I've seen some courses use teaching IDEs like BlueJ at first, which allow you to point-and-click to run arbitrary methods, but we'll set those aside...) While it might be worthwhile to handwave over some of these keywords for a little while, sooner or later most teachers are going to want to explain them. Indeed, a classic beginner-level test question is to ask students to give the meaning of each keyword in a basic Hello World program. And what do we find as part of our main method signature? An array (The reason for that is, in part, historical. ArrayList didn't exist in Java 1.0). Arrays are part of that basic set of knowledge. List is not.

That said, it's not that uncommon for classes to introduce ArrayList a little later into the course, especially once objects and their use have been covered. Even the AP Computer Science curriculum for Java includes ArrayList (I know it used to, and Google seems to indicate that it still does), although it ignores the fact that ArrayList implements List and the rest of the Collections Framework.

Finally, it's my experience that university CS programs use Java as a means to exploring CS and programming concepts rather than to teach students how to become good Java developers. Some programs may be more focused on churning out professional developers while others focus more on theory, but in either case, there's a lot to learn about how to use Java in real professional work that won't be taught in most college curricula. This ranges from design patterns and techniques like those in Effective Java to frameworks like Spring, Hibernate, or JUnit, or even more common things like JSP or JDBC. With that philosophy in mind, emphasizing arrays over the more commonly used ArrayList makes a little more sense.

  • 3
    @Deduplicator sure. It just wasn't relevant to my point about arrays, so I omitted it. I also didn't include System.out.println("Hello World!"); either. – Zach Lipton Mar 11 '15 at 18:22
  • +1 for concepts vs. effective techniques for the "real world". No one was teaching version control either, at least not when I was in school -- but then I'm ancient :) – David Mar 13 '15 at 13:50
  • I took an operating systems class where we had to implement various pieces like a scheduler; we focused on one such piece at a time (exclusively) because at that point we were not capable of doing more. But thinking about trying to get all of those pieces working at the same time was what gave me (the beginnings of) an appreciation of the complexities of "real world" development / "programming in the large". – David Mar 13 '15 at 13:59
14

One reason that first-year programming classes use arrays is legacy: that's how the professors originally learned it before we started using standard libraries with dynamic lists baked in. Using the primitive data types is also more generally applicable: arrays exist in pretty much any computer language under the sun (and can be implemented in a handful of assembly instructions). When I was first learning programming, implementing a linked list was one of the assignments.

It's much easier to start from first-principles and then say "That's the basic structure. This language (or its libraries) gives you this high-level data structure that does all that, but gives you x, y, and z," than it is to say "So that's these high-level data structures, now here's what's under the hood." Learning to reason about whether to use a LinkedList vs. an ArrayList (or a HashSet vs. a TreeSet) is usually a second or third-year Algorithms course. Lists and Maps have the same interfaces and give the same results, but can have dramatically different behaviors in an application of any size. And once you get out of Programming 101, there's no guarantee that Programming 102 will be using the same language. If you start from the concept of an array, you can just say "this is how you use arrays in this language", rather than trying to explain why you don't get all the fancy things that Java Lists give you. And once you get out into "the real world", there are still people out there who have to program in C (particularly in high-performance projects where you need to get as close to the metal as possible).

Another reason to prefer "array" over "List" in an introductory course is that arrays are fundamentally easy to understand: An array of 20 bytes takes 20 bytes (plus a couple to indicate either the end of the array or the length, depending on implementation).

A "List" is a completely different kettle of fish and can be implemented in many different ways (ArrayList, LinkedList, and probably a couple I've forgotten), with fundamentally different performance characteristics. Without understanding the guts of what the different List classes are doing, you can't have a meaningful discussion of when you should use List foo = new ArrayList() vs. List foo = new LinkedList(). If you try to get the student to use a List implementation, someone is going to ask why you're using ArrayList instead of one of the other implementations. And "ArrayList" includes the word "Array" and is backed by one, so it really isn't a huge logic jump from "array" to "ArrayList".

Contrary to popular belief, there ARE situations in which it makes sense to use arrays over Lists, particularly when you're dealing with a list of static size. Here are a couple:

  • Lookup and iteration are slightly faster because you're not dealing with method invocation overhead: foo[n] dereferences and does some behind-the-scenes pointer arithmetic, while foo.get(n) has to dereference, do a method invocation, do a second dereference, and then maybe do pointer arithmetic (if you're using an ArrayList; LinkedLists potentially need to iterates over every element of the List).
  • Initialization is much cleaner: int[] foo = new int[]{1, 2, 3, 4, 5} vs. the suggestions in Another StackOverflow question
  • Another scenario when arrays massively beat arrays is when the sequence in which elements become available matches the sequence in which their final positions will become known, but does not match the final sequence. If perm is an int[256] that holds a permutation, one can easily invert it with an array: int[] inv = new int[256]; for (int i=0; i<256; i++) inv[perm[i]]=i; I don't think anything one could write with an ArrayList<> would be as clean. – supercat Mar 12 '15 at 2:21
  • @supercat That's not really with a problem with dynamic arrays, just the particular implementation; ArrayList could've easily been given a constructor that creates a default-initialized list of a certain size. – Doval Mar 13 '15 at 15:22
  • Do you have sources to back up the claim that an array list has to deal with method invocation overhead? In theory it does, but in practice I'd be surprised if get and set don't get inlined. – Doval Mar 13 '15 at 15:24
  • @Doval: There's no reason a a well-designed language/framework shouldn't supply a dynamic-array type which can conveniently add items out of sequence, but Java doesn't supply such a type. – supercat Mar 13 '15 at 15:59
  • @Doval: Even if get and set can be in-lined, something like myList.set(23,myList.get(23)+1) will be nowhere near as efficient as myArray[23]+=1. Further, even for types which wouldn't need boxing, I would be very surprised if any JITter could anything equivalent to for (i=0; i<1000; i++) myList2.set(i+2000,myList2.get(i+3000)); into anything whose performance is anywhere near System.arrayCopy(myArray1,3000,myArray2,2000,1000); There's no reason a framework's dynamic array type shouldn't offer a fast copy-range operation, but Java doesn't. – supercat Mar 13 '15 at 16:43
7

Java allows variables of any type to be stored into arrays. By contrast, ArrayList only allows storage of references. One may thus not usefully discuss ArrayList without first covering how auto-boxing will convert primitives to reference types, and how auto-unboxing will sometimes convert reference types to primitives:

for (int i=10; i<=10000; i*=10)
{
    ArrayList<Integer> l = new ArrayList<Integer>();
    l.add(i);
    l.add(i);
    l.add(l.get(0));
    System.out.print("i=" + i);
    System.out.print(" #0==i:" + (l.get(0)==i));
    System.out.print(" #1==i:" + (l.get(1)==i));
    System.out.print(" #2==i:" + (l.get(2)==i));
    System.out.print(" #0=#1:" + (l.get(0)==l.get(1)));
    System.out.print(" #1=#2:" + (l.get(1)==l.get(2)));
    System.out.println(" #0=#2:" + (l.get(0)==l.get(2)));
}

If the code had used an int[3] rather than an ArrayList, there would be no surprises. All three elements would compare equal to i and to each other. Using ArrayList, however, even though all three elements of the list will always compare equal to i, and the first and third will always compare equal to each other, the first two elements will only equal each other when i is 1, 10, or 100, but (on most implementations) not when i is 1000 or 10000.

  • Could you explain why #0 and #1 will be equal when they're 1 or 10 or 100? I followed up till that point. – Matthew Read Mar 12 '15 at 14:22
  • 2
    @MatthewRead: The Integer class has nested class called IntegerCache which holds pre-initialized Integer objects for a range of values that typically extends -128..127; boxing a value outside that range will require creating a new object, but boxing a value within the cached range will simply return a reference to one of the pre-initialized objects stored in IntegerCache.cache. Any good Java programmer needs to be aware that two Integer-type variables encapsulating the same value may or may not compare equal, but introducing that idea too early may make students flee in terror. – supercat Mar 12 '15 at 15:18
  • Huh, never would have guessed it was due to pre-initalized objects. Thanks for the info! – Matthew Read Mar 12 '15 at 16:31
  • 1
    @MatthewRead: I wish Java had disallowed certain sorts of implicit conversion with ==. Given the possibility that auto-unboxing can throw, I'd be inclined to disallow it entirely, but its behavior with == is especially horrid. The == operator also behaves badly in cases like 16777217==16777216f [reports true], and the implicit conversions for long v=Math.Round(123456789), w=Math.Round(123456789012345) are apt to be unexpected [can you guess what those expressions will yield?] – supercat Mar 12 '15 at 16:45
  • As for IntegerCache, there are certainly times when it can help performance, but it can frequently cause code which is Just Plain Wrong to kinda-sorta work. In some ways, I wish there were a mode where boxing would quasi-randomly return objects from two integer caches and quasi-randomly replace cache items with new ones, so that code relying upon the boxing behavior of values -128..127 would be unlikely to succeed for very long. – supercat Mar 12 '15 at 16:52
6

I think it makes sense to teach how to use arrays first due to the fact that ArrayList uses an array internally. The ArrayList class has a member variable called elementData which is an Object array.

From the JDK ArrayList source code:

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer.
 */
private transient Object[] elementData;

When you add, update, retrieve or remove elements from an ArrayList it uses this internal array to do those operations. As user Ixrec has already pointed out - ArrayList is just a higher-level abstraction which is typically easier to work with.

  • But an array uses a pointer to a block of memory, internally. Why start at that specific level of abstraction? – user25946 Mar 13 '15 at 20:03
  • The question is tagged as Java - It was asking why teach arrays when typically you may use ArrayList. Java doesn't have pointers. Right or wrong, I hold the opinion that C/C++ is a better language to start students with than Java. Many topics in programming can be better understood by having knowledge of C/C++. – Derek W Mar 13 '15 at 20:14
3

Assuming that list are indeed easier to work with, as you say — that doesn't really matter. Learning is more about "basic to complex" than "easy to hard". If fundamentals weren't important, then computer science wouldn't be an academic field. You could just learn how to click together apps using existing frameworks/libraries from online tutorials. (Of course, someone has to write those libraries ... and someone has to implement ArrayList in the first place....)

  • In many cases that use ArrayList could be better handled by using a separate array and "liveItems" count, except that there's no convenient way to work with the array and count together except by aggregating them. – supercat Mar 11 '15 at 17:26
2

It's because the most crucial thing in academic education is to teach you to use the correct terminology to describe the things you do.

List is something other that array. and You can't use java.util.List in Java because it's an interface. You usually use java.util.ArrayList which being a List implementation, is not a list, but an object wrapper around dynamic array. So you say you use a 'List' but you use an array.

It's very reasonable to skip that terminological chaos and simply use arrays to learn students what is array. If you use arrays in Java, at least you use arrays.

Honestly, it's also the argument why teaching programming with Java isn't a good idea. It's hard to learn the basic concepts of programming correctly.

  • what about hashmap? an array is just a type of hashmap, in a way.. – Thufir Mar 13 '15 at 11:13
  • @Thufir how can an array be a hashmap? Those are completely different data structures. – Danubian Sailor Mar 13 '15 at 13:09
  • you can represent an array with a hashmap. which is more "fundamental"? I'd argue hashmap is more conceptually interesting. – Thufir Mar 13 '15 at 13:12
  • 1
    @Thufir no, you can't. You can only emulate. Internally each data structure will be what it is. Those are fundamentally and conceptually different things. This is why it's bad idea to start learning programming with such highly abstract languages like Java or JavaScript. It's not clear there, what the data structures really are. – Danubian Sailor Mar 13 '15 at 13:33
1

You've literally never seen or used any arrays at all? We use them all the time, in addition to lists. We usually don't use Java, but we do use plenty of other languages that draw obvious similarities.

Between arrays and Lists, one's lighter-weight and, additionally, more to-the-point, whereas the other's got more functionality. As a general rule in programming, when there are two similar types that are basically divided along those lines, you should go for the lighter-weight one unless you actually need the fancier one. In addition to reducing overhead, this actually helps keep a handle on the amount of clutter and state in the program and particularly its code. If something goes wrong during testing, you have fewer places to look; and more importantly in the case of arrays vs. Lists, people get a better idea of the limited scope of what you're actually using it for and trying to do with it.

And yeah, from an academic standpoint, there is the added reason of teaching students the basics. However this goes a little bit deeper. Arrays and Lists are a good example of bulkier types often just being built on top of, and frequently just wrapping around, underlying instances of the lighter-weight types. Even when Lists don't have underlying arrays, they behave outwardly like they do. One part of teaching somebody what a List is would be to teach them what an array is.

I could see this maybe getting out of hand in a language like C++, where arrays basically could not be more stripped down than they are, but in higher-level languages, they're almost Lists unto themselves. If they suit your needs perfectly in a given situation, why would you need to use something else?

  • I wouldn't say a list has "more" functionality, so much as it has "different" functionality. A new T[] will be ready, right out the gate, to accept items in any order, while an ArrayList<T> requires that items be added, in order, before they can be modified. A T[] can copy an arbitrary range of items to a similarly-sized range of another T[] relatively quickly, while ArrayList<T> would require reading items individually out of one list and storing them to the other--much slower and less convenient. – supercat Mar 15 '15 at 20:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.