Data structure with constant time access and variable size

I was asked this question in one of my inter开发者_JS百科views.

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.

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.

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.

How about a deque, or a "double-ended queue"? In many implementations, it doesn't change size efficiently for insertions and removals at any location but its head or tail, but it otherwise provides the two properties you seek:

• Growth with only occasional and minimal reallocation as elements are added
• Constant-time access, as the deque is usually stored as an array of arrays

You mention Java in your question—by way of a tag—and I must note that the Deque interface in Java does not offer random access. Even the ArrayDeque concrete class doesn't offer it. That's an unfortunate choice, made in the interest of being more abstract and imposing as few requirements on the interface as possible.

Regardless, beyond Java, you will find deque implementations that do satisfy the properties you requested.

Why not have one hashtable and insert all elements in it while inserting element in LinkedList and read from hashtable in constant time.