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?
3 Answers
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.
15 Comments
sircodesalot
Perfect. That's what I was looking for.
Dimitar Dimitrov
I'm pretty sure
List<T> is also backed by an array.
jason
@Dimitar Dimitrov: Yes, it is.
ArrayList is pre-generics though.sircodesalot
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.
jason
@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. |
.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.
Comments
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
ArrayListstores it's data as a linked list internally?IListis simply an interface that allows for dynamically sizing, but doesn't entail any specific implementation. So anArrayListis aIListimplementaiton backed by an array. If you'd like to use a linked list, please see LinkedList<T>.LinkedListis a linked-list, what then isList?IList/IList<T>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 aLinkedList<T>is not aIList<T>.