Re: How to count value in a ArrayList

On Sat, 24 May 2008 15:23:21 -0700, j1mb0jay <j1mb0jay@xxxxxxxxx> wrote:

From reading the OP, i thought that they where inserting double values
into a data structure and wanted to make sure that the value that they
were adding was not already stored in the data structure.

That's not how I read the original message at all. He specifically states "I _have_ an ArrayList" (emphasis mine) and "that _is_ sorted". Granted, maybe English isn't his first language and he's misusing the tenses. But I don't see any reason to _assume_ that. If he wants to clarify, that's fine. But the English as stated doesn't imply anything at all about building the data structure. It's there already, and he just wants to interact with it.

To me this
means they will need to compare every insert item with ever single item
in the list O(n). Doing this with a ArrayList is a lot slower than a hash
table, as you could hash the double value to find out which linked list
the value would be stored in, then just check the few values in the list.

Well, if your interpretation of the OP was correct, then the above would be relevant to the OP. But still not relevant to the statement about the cost of adding an element to the data structure.

When an array list is full is needs to be cloned to another larger array
list.

As does a hash table, albeit under somewhat different rules.

I thought that hash tables where are array of linked lists (Also
known as a bucket array) this means they can never be full (will use SWAP/
Virtual Memory when RAM is full), but the more items that are in each
linked list the slower the search time becomes, the insert time of a
linked list is always O(1) if you are adding to the tail of the list.

I haven't checked the .NET hash table implementation specifically. But presumably they use a relatively common technique of having a fixed-sized array of bins that grows as the hash table accumulates items. This allows a hash table with relatively few elements to not take up too much memory, but still allows for minimizing collisions for hash tables that have a lot of elements.

Some implementations use bins that are either arrays or linked lists, while others simply use the next available spot in the hash table (and undoubtedly there are other implementations I'm not thinking of at the moment). Either way, the lookup part of the hash table is only ever as big as needed for the number of elements in the table.

If the OP is using a ArrayList and would like to keep the items in order
when inserting a new item this would mean moving all of items along one
in the list, again another slow process, maybe a tree of some kind would
be a better option.

Yes. But the OP never said he wants to do that.

I was always taught to stay away from ArrayList at all costs. Arrays are
fine if you know the amount of items that you would like to store, and
they have a fast data access compared to a list as you do not have to
iterate all of the items to find the one you require.

Don't confuse ArrayList with an array _or_ a list. It is neither, even though it shares some features with each.

In any case, arrays, lists, or ArrayLists, none deserve being considered as "stay away from at all costs". They each have their purposes, and they are perfectly valid data structures for those purposes.

Pete
.

Relevant Pages

  • Re: Dict sharing vs. duplication
    ... array to enforce unique keys and I use lists to enforce order. ... API in a page or two of Tcl code, it isn't so much a missing feature ... OpenACS database API which creates a new specialized data structure, ...
    (comp.lang.tcl)
  • Re: problem with hash & sort array
    ... Then I put the hash into an array with the sort ... The twist is I have to identify the duplicate ... a real data structure, and in the next place I make the exact opposite ...
    (comp.lang.perl.misc)
  • Re: Need someone very familiar with arrays
    ... I never would've thought of using an array as the basis for the list; ... figure out how to actually implement a hash table. ... For generic lists, the hash itself can be quite a challenge, since ...
    (microsoft.public.vb.general.discussion)
  • Re: Help with Hash of Hashes
    ... can visualize the data structure I need in my head, ... I solved an identical probelm with a hash array references. ... foreach $crs ...
    (comp.lang.perl.misc)
  • Re: beginning with ML
    ... What's the preferred data structure? ... Lists are commonly used, being functional, but hash tables are also ... I use the RedBlackTree implemenation in the utility library ...
    (comp.lang.functional)