Data structure with constant time access and variable size

Question

I was asked this question in one of my interviews.

Is there a data structure which has the following 2 capabilities:

1. Constant time access (Random Access), like ArrayList

2. Variable size, like LinkedList

If there is no such data structure, create one on your own.

Answer 1

I believe the answer you're looking for is "Hash table" (See: "Hash Table" in Wikipedia) as you've commented that they were looking for another one beyond ArrayList (For Java, see: Hashtable)

Though be aware that it can be near constant time depending on the hashing algorithm and data set as collisions may occur resulting in a (short) secondary linear search. The Javadoc gives a really good explanation of how this is handled in the Java implementation.

Answer 2

In addition to the HashTable as Brian Roach said, the interviewer may have been alluding to a LinkedHashMap or LinkedHashSet, which provides about constant time performance for some basic operations, while also maintaining order of insertion, as it combines a HashTable with a doubly-linked list.

In other words, the order you put elements into the LinkedHashMap will be the same order they are retrieved if you loop over the keys.

One downside with using Sets though is you can't have duplicates, and Maps likewise can't have duplicate keys. The workaround would be having a Set of Lists, or using something like Google's Multimap.

But as everyone else said, an ArrayList already meets both requirements. It's an array that doesn't have variable size.

Plus, the major advantage of a LinkedList over an ArrayList is constant time insertion/deletion at both the end and beginning of the list, compared to ArrayList's O(n) performance. Both can provide variable size.