Results 1 to 18 of 18

Thread: what is arraylist

  1. #1

    Thread Starter
    Hyperactive Member
    Join Date
    Oct 2003
    Posts
    436

    what is arraylist

    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

  2. #2
    Frenzied Member conipto's Avatar
    Join Date
    Jun 2005
    Location
    Chicago
    Posts
    1,175

    Re: what is arraylist

    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
    Hate Adobe Acrobat? My Codebank Sumbissions - Easy CodeDom Expression evaluator: (VB / C# ) -- C# Scrolling Text Display

    I Like to code when drunk. Don't say you weren't warned.

  3. #3

    Thread Starter
    Hyperactive Member
    Join Date
    Oct 2003
    Posts
    436

    Re: what is arraylist

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

    thanks

  4. #4
    .NUT jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    105,430

    Re: what is arraylist

    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

  5. #5

    Thread Starter
    Hyperactive Member
    Join Date
    Oct 2003
    Posts
    436

    Re: what is arraylist

    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

  6. #6
    Hyperactive Member GlenW's Avatar
    Join Date
    Nov 2001
    Location
    Gateshead, England
    Posts
    479

    Re: what is arraylist

    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.

  7. #7
    PowerPoster
    Join Date
    Aug 2003
    Location
    Edinburgh, UK
    Posts
    2,773

    Re: what is arraylist

    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

    MVP 2007-2010 any chance of a regain?
    Professional Software Developer and Infrastructure Engineer.

  8. #8

    Thread Starter
    Hyperactive Member
    Join Date
    Oct 2003
    Posts
    436

    Re: what is arraylist

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

    regards
    nath

  9. #9

    Thread Starter
    Hyperactive Member
    Join Date
    Oct 2003
    Posts
    436

    Re: what is arraylist

    Quote Originally Posted by 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.

    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?

  10. #10
    PoorPoster iPrank's Avatar
    Join Date
    Oct 2005
    Location
    In a black hole
    Posts
    2,728

    Re: what is arraylist

    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.)
    Usefull VBF Threads/Posts I Found . My flickr page .
    "I love being married. It's so great to find that one special person you want to annoy for the rest of your life." - Rita Rudner


  11. #11

    Thread Starter
    Hyperactive Member
    Join Date
    Oct 2003
    Posts
    436

    Re: what is arraylist

    thanks for the link iprank.

    regards
    nath

  12. #12
    .NUT jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    105,430

    Re: what is arraylist

    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.

  13. #13
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403

    Re: what is arraylist

    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
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

  14. #14
    .NUT jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    105,430

    Re: what is arraylist

    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.

  15. #15
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403

    Re: what is arraylist

    Quote Originally Posted by 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.
    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.
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

  16. #16
    Hyperactive Member GlenW's Avatar
    Join Date
    Nov 2001
    Location
    Gateshead, England
    Posts
    479

    Re: what is arraylist

    Quote Originally Posted by bnathvbdotnet
    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.

  17. #17
    Hyperactive Member GlenW's Avatar
    Join Date
    Nov 2001
    Location
    Gateshead, England
    Posts
    479

    Re: what is arraylist

    Quote Originally Posted by 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.
    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.

  18. #18
    PowerPoster sunburnt's Avatar
    Join Date
    Feb 2001
    Location
    Boulder, Colorado
    Posts
    1,403

    Re: what is arraylist

    Quote Originally Posted by GlenW
    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:

    Code:
    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.
    Every passing hour brings the Solar System forty-three thousand miles closer to Globular Cluster M13 in Hercules -- and still there are some misfits who insist that there is no such thing as progress.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width