Even if the real C array contained a pointer to the last element in the LL (which it does not, it only points to the first) What version of PHP are you looking

Even if the real C array contained a pointer to the last element in the LL (which it does not, it only points to the first) What version of PHP are you looking at? PHP 5.3 and up seem to have a sensible linked list implementation in zend_hash.[ch]. The buckets only have a pointer to the list head, but items are inserted at the head. The hash has a separate list for ordered traversal of all items in the "array" and that has pointers to both the head (for traversal) and tail (for insertion). In both cases, list insertion is O(1). Of course, as you said, the search for our worst case is necessarily O(N). Depending on your perspective, we can say that's a trade-off with hashes, a fault with the hash algorithm, or a fault with the collision resolution strategy.