what is arraylist

[bnathvbdotnet]

I am seeing lot of examples in regards to arraylist in c#.

but what is the arraylist? is it a list of arrays? can I assume like that?

Is it some thing like linked list?

any explanation would be very helpful.

nath

[conipto]

It is like a dynamically sized array that can hold multiple types inside. It uses an Items collection inside, and it lives in the System.Collections namespace.

Bill

[bnathvbdotnet]

what do you mean by "It uses an Items collection inside"??

thanks

[jmcilhinney]

I suggest that you read the official documentation and then ask again if you don't understand what it is saying.

http://msdn2.microsoft.com/en-us/lib...arraylist.aspx

[bnathvbdotnet]

Thank you for the link. But I went thru that stuff already and I wanted to know how the data is stored in the memory if we a Linked List.

thanks
nath

[GlenW]

An ArrayList is an object that represents a linked list. The linked list is accessed by the object. A Collection in vb6, a vector in C++. When you understand how to use them you'll realise they are one God's greatest gifts.

[Techno]

totally
cant live without them now. they are also sortable to the way you want if you override a method or so

in .NET 2.0 there is a new one called a generic List. Just thought I would mention it

[bnathvbdotnet]

Cool...great explanation...thanks all of you and have a wonderful day/probably evening for folks in UK.

regards
nath

[bnathvbdotnet]

An ArrayList is an object that represents a linked list. The linked list is accessed by the object. A Collection in vb6, a vector in C++. When you understand how to use them you'll realise they are one God's greatest gifts.

I am in a training class and when I asked him if arraylist is a linked list, he said no...

so from your reply, you mentioned that arraylist is implemented as linked list behind the scene.

is that correct?

[iPrank]

Me too would like to here from you experts.

(If anyone is interested, today Saurabh posted a new article on Limitations of ArrayLists in C# in CSC.)

[bnathvbdotnet]

thanks for the link iprank.

regards
nath

[jmcilhinney]

The ArrayList does not behave like a linked list because each item knows nothing of the item either before or after it. It is the collection itself that keeps track of the items. The .NET 2.0 Generic.List(Of T) is the strongly typed equivalent of the ArrayList. .NET 2.0 has also introduced the Generic.LinkedList(Of T), which is a genuine linked list as each item is a LinkedListNode that is aware of its neighbours. With the LinkedList you could traverse the entire collection without a reference to the collection itself by moving from node to node, while with the ArrayList or List you need a reference to the collection itself.

[sunburnt]

According to the msdn, the ArrayList is implemented as an "array whose size is dynamically increased as required."

So no, it is not implemented as a linked list internally.

HTH

[jmcilhinney]

That is interesting. I didn't realise that increasing the capacity of an ArrayList actually involved essentially the same operation as ReDimming an array. That makes the importance of specifying a realistic initial Capacity for an ArrayList much more obvious. Here's a link to the page I assume that sunburnt got that information from.

[sunburnt]

That is interesting. I didn't realise that increasing the capacity of an ArrayList actually involved essentially the same operation as ReDimming an array. That makes the importance of specifying a realistic initial Capacity for an ArrayList much more obvious. Here's a link to the page I assume that sunburnt got that information from.

Yup, it's always good to specify the capacity when you know ahead of time how many items you will begin with.

I assume that the algorithm for resizing the array involves doubling the capacity every time you fill it up, so it might also be interesting to see if it makes a difference in memory usage to lower the capacity once you have finished adding objects to your list.

[GlenW]

I am in a training class and when I asked him if arraylist is a linked list, he said no...

so from your reply, you mentioned that arraylist is implemented as linked list behind the scene.

is that correct?

Yes, an ArrayList stores its data in a linked list on the heap. As I said, just like a C++ vector.

[GlenW]

The ArrayList does not behave like a linked list because each item knows nothing of the item either before or after it. It is the collection itself that keeps track of the items. The .NET 2.0 Generic.List(Of T) is the strongly typed equivalent of the ArrayList. .NET 2.0 has also introduced the Generic.LinkedList(Of T), which is a genuine linked list as each item is a LinkedListNode that is aware of its neighbours. With the LinkedList you could traverse the entire collection without a reference to the collection itself by moving from node to node, while with the ArrayList or List you need a reference to the collection itself.

A LinkedList merely allows the actual implementation to be seen, an ArrayList still uses a linked list to store its data. A node in a linked list does not know anything about its neighbours, it merely stores the next nodes memory address. An ArrayList is an object that holds the address of the first node, that node will contain the object you are aware of and the address of the next one. All the operations the ArrayList make accessible are carried out behind the scenes on the linked list. An array is a contiguous segment of stack memory, any dynamic collection of data must be stored on the heap, by definition this cannot be guaranteed to be contiguous. So there needs to be a way to transverse the items in the collection, you use a linked list.

[sunburnt]

Yes, an ArrayList stores its data in a linked list on the heap. As I said, just like a C++ vector.

If you had read what I posted or followed the msdn page jmcilhinney linked to, you would realize that an ArrayList is not implemented as a linked list, but as an array that is realloc'ed as needed.

Not only that, but a std::vector cannot possibly be implemented as a linked list because the STL guarantees that the items in a vector are stored in a contiguous block of memory such that the following expression will point to the Nth item in the vector:

vector<int> myvector;

int* i = (&myvector[0]) + n;

An array is a contiguous segment of stack memory, any dynamic collection of data must be stored on the heap, by definition this cannot be guaranteed to be contiguous.

When you request a block of memory from malloc, c++ new, or C# new(), the block returned must be a contiguous block large enough to hold the item you requested (new) or the number of bytes requested (malloc).

Behind the scenes, an ArrayList or a std::vector will request a block of memory. When you have filled this block of memory with items, it will request a block of memory twice as large, copy your previous data to the beginning of this block, and free the previous block. There is no usage of any sort of linked list structure.


To sumarize: yes, a std::vector and an ArrayList are implemented in the same way, and neither are implemented as linked lists.