Is an ArrayList an Array or a List?

Question

Simple old school C# question: Is an ArrayList an Array or a List? The differences between the two are enormous, so I'm curious if anyone knows the way that ArrayLists store data?

Does that mean it's like an expanding array or something? (That sounds terribly slow on deletions) — sircodesalot, Aug 05 '13 at 04:17
Are you asking if `ArrayList` stores it's data as a [linked list](https://en.wikipedia.org/wiki/Linked_list) internally? — p.s.w.g, Aug 05 '13 at 04:17
An `IList` is simply an interface that allows for dynamically sizing, but doesn't entail any specific implementation. So an `ArrayList` is a `IList` implementaiton backed by an array. If you'd like to use a linked list, please see [LinkedList](http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx). — p.s.w.g, Aug 05 '13 at 04:21
@sircodesalot two completely different concepts. A list in .NET terms, is any class that satisfies the `IList` / `IList` interface for dynamically adding / removing items and accessing them by index regardless of how that's implemented. A linked list, on the other hand is a specific kind of data structure, which (described in the Wikipedia article I linked to earlier). Because of the way the structure is designed, it doesn't support index-based access, so technically a `LinkedList` is not a `IList`. — p.s.w.g, Aug 05 '13 at 04:25
Have a look at this question for more info: http://stackoverflow.com/questions/2309694/arraylist-vs-list-in-c-sharp — Dev Rios, Aug 05 '13 at 04:28

score 11 · Accepted Answer · edited Aug 24 '13 at 18:26

11

ArrayList behaves like a list (in particular, its count of elements can grow, unlike an array), but it's backed by an array, which will be dynamically resized as needed. Hence the name ArrayList.

Things that behave like lists don't have to be backed by arrays (they could be linked lists, for example), but ArrayList is.

edited Aug 24 '13 at 18:26

fny

31,255
16
96
127

answered Aug 05 '13 at 04:19

jason

236,483
35
423
525

Perfect. That's what I was looking for. – sircodesalot Aug 05 '13 at 04:19
I'm pretty sure `List` is also backed by an array. – Dimitar Dimitrov Aug 05 '13 at 04:20
2

@Dimitar Dimitrov: Yes, it is. `ArrayList` is pre-generics though. – jason Aug 05 '13 at 04:22
When you say dynamically resized, that entails a full copy of the existing items into a new array? (Or is there some faster way of I'm unaware of). Seems like expansion and deletion would be fairly slow. – sircodesalot Aug 05 '13 at 04:27
1

@sircodesalot: Full copy. I *think* it doubles in size on regrowth (this sort of geometric growth is standard, Java uses 3/2 for its `ArrayList` and Python uses 9/8 for its list). By doing this, we get *amortized* `O(1)` insertion, and waste at most `O(n)` space. To insert `n` elements we only need `log n` regrowths. – jason Aug 05 '13 at 04:28
What about deletion? Do you know if that means moving all post deletion elements forward one? – sircodesalot Aug 05 '13 at 04:33
@sircodesalot: Yes, it does. Deletion in the middle is `O(n)`. – jason Aug 05 '13 at 04:33
Huh, enlightening. Thanks – sircodesalot Aug 05 '13 at 04:33
Apart from difference from dynamically growth point of view, Arrays are cache efficient but ArrayList is not if it is backed by LinkedList. – AKS Aug 06 '13 at 13:10
@AKS: Yes and no. `ArrayList` holds references. Those references will be contiguous in memory, and therefore cache friendly. It is *not* necessarily the case (and likely not the case) that the *referrents* will be contiguous in memory. That is, the contiguous nature of the *references* in `ArrayList` doesn't buy you much from the perspective of CPU cache because the *referrents* will still be fragmented in memory. – jason Aug 06 '13 at 13:28
@Jason, :( sounds gr8 butNot able to understand those terms esp referrents, but if you can explain the same answer in memory terms then that would be great. Arrays are stored as contiguous memory in main memory, and hence cache friendly, and linked lists are fragmented and not contiguous hence no advantage from cache point of view. Now it all depends how you have implemented ArrayList, Array or LinkedList. – AKS Aug 06 '13 at 13:42
@AKS: Given: `ArrayList` is backed by an array. The storage locations for that array occupy a contiguous memory region. Contiguous memory regions are cache friendly. The values in the storage locations in the `ArrayList` are references. The referrents of those references (meaning, the objects that are *referred* to) live on the managed heap. That is, the `ArrayList` does not actually hold the objects, it holds references to those objects. Those referred-to memory locations are not necessarily contiguous and *could* be highly fragmented. That is not cache friendly. – jason Aug 06 '13 at 13:48
@Jason, got it now :) , but if i go by this logic then in java even any array is object and hence reference, so it will never be cache friendly. right? – AKS Aug 06 '13 at 13:50
@AKS: Arrays of primitives are okay. – jason Aug 06 '13 at 13:58
@Jason, Ya, you are right, in case of array of primitives this cache friendly logic will be useful. Thanks for the detailed explanation. – AKS Aug 06 '13 at 14:01

score 1 · Answer 2 · answered Aug 05 '13 at 04:28

.NET Framework contains a data structure that provides this functionality—the System.Collections.ArrayList classThe ArrayList maintains an internal object array and provides automatic resizing of the array as the number of elements added to the ArrayList grows. Because the ArrayList uses an object array, developers can add any type—strings, integers, FileInfo objects, Form instances, anything.

While the ArrayList provides added flexibility over the standard array, this flexibility comes at the cost of performance. Because the ArrayList stores an array of objects, when reading the value from an ArrayList you need to explicitly cast it to the data type being stored in the specified location. Recall that an array of a value type—such as a System.Int32, System.Double, System.Boolean, and so on—is stored contiguously in the managed heap in its unboxed form. The ArrayList's internal array, however, is an array of object references. Therefore, even if you have an ArrayList that stores nothing but value types, each ArrayList element is a reference to a boxed value type.

you'll be able to invoke ArrayList specific methods and use ArrayList specific members in addition to those inherited from List.

score 0 · Answer 3 · answered Aug 05 '13 at 05:39

Apart from other differences, one more difference is that ArrayList are not strongly typed i.e array list can add any type of element which is derived from object as shown in the code below

ArrayList myArrayList = new ArrayList();
myArrayList.Add(1);
myArrayList.Add("test");

but array and IList are strongly typed i.e we can take advantage of compile type checking in both of them e.g

int[] myarray = new int[5];
myarray[0] = 1; // This is correct
myarray[1] = "test"; // compile time error

Is an ArrayList an Array or a List?

3 Answers3