1

What data structure can you use to store elements dynamically and access them efficiently?This is an interview question. Should I answer std::list (I mean in C++)? or others?

As a follow-up question, what is the complexity of finding any element in a linked list in the worst case?

Thank you for all your opinions.

Improve this question
1
  • 1
    What kind of elements? What exactly do you mean by 'access'? Commented Feb 10, 2011 at 1:42

6 Answers 6

Reset to default
15

This question is pretty vague. The whole reason we have multiple data structures is that they all support different access patterns more or less efficiently than others. For example:

  • A linked list is a good choice if all access is from the start of the list forward.
  • A dynamic array is a good choice if the accesses are random and insertion/deletion is at the end.
  • A stack is a good choice if the accesses are always FIFO.
  • A queue is a good choice if the accesses are always LIFO.
  • A deque is a good choice if accesses are always at the ends.
  • A priority queue is a good choice if the accesses are always to the smallest element.
  • A hash table is good if accesses are totally random and no ordering is required.
  • A balanced binary search tree is good if accesses are totally random and an ordering is required.
  • A trie is good if the elements being stored are strings or otherwise digital.
  • A kd-tree is good if the elements are points in space and you want to support range queries or nearest-neighbor searches.
  • A union-find structure is good if you want to know how elements are connected to one another.
  • A van Emde Boas tree is good if the values are integers, accesses are random, and you want them to be in order.
  • A quadedge is good if you want to store the elements as a geometric structure and want to access points and edges near particular faces (or vice-versa)
  • etc.

There are myriad good answers to this question depending on just what you're trying to do to the data. This list is only a small sampling of what data structures are out there, and all of them could be the right answer depending on the circumstance. They could also all be the wrong answer depending on the circumstances. Remember - when choosing a data structure, make sure you know what problem you're trying to solve!

As to your second question: in the worst case, it can take O(n) time to find an element in a linked list. This happens either when the element you are searching for is not present in the linked list or if it is near the end. In that case, you need to scan the entire linked list one element at a time before you can conclude whether or not the element in question is contained within the list.

Hope this helps!

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

First question I would say hash table. Putting and getting elements using hash table is O(1) in average case. Linked list have worse case of storing in O(n) and worse case of access in O(n). Array has worse case of storing O(1) and worse case of access in O(1). Linked List can grow dynamically very fast, where as array will need to do allocate new and bigger array, and copy existing element over to achieve dynamically growing capability.

For question 2, the complexity of finding an element in linked list is O(n) since you have to iterate through all the elements in the list in worse case (consider the case where the element is not in the list).

Improve this answer

Comments

2

I think the answer depends entirely on what you're storing and what the access patterns are:

  • What kind of access do you need? Random? Sequential?
  • Are inserts/updates frequent or infrequent?
  • How many elements?
  • What type are the elements?
  • .. etc ..

If I were asked your question in an interview, I would start by asking back those clarifying questions. Sometimes interviewers ask vague, open-ended questions to see how you think: to see if you can recognize a not fully specified problem, and ask questions to get the necessary context to answer.

Improve this answer

Comments

1

Access to elements in list is not efficient. You should default to using vector, it's random access.

Improve this answer

3 Comments

but vector is not match "dynamically" I think
@Don Lun: What do you mean by "dynamically". You can insert and erase elements from a vector at will. Although, unless the insertions and erasures are at the back, there is a cost in efficiency.
@Don Lun: in C++ terminology, a vector is a Standard container using heap memory and capable of growing to arbitrary size - very dynamic indeed. By way of contrast, a fixed-length array ala int x[20] is not dynamic.
0

That depends on the usage pattern:

for example, for vector, fast access to random elements comes at a price of new elements addition,

with list you will be efficient at adding new elements, while random element access is impossible - you will have to traverse the entire list (in worst case) to access the desired element, that is, O(n) complexity.

You can find information regarding complexity for different stl containers operations here: http://www.cplusplus.com/reference/stl/

Improve this answer

Comments

0

If I would have asked this I would have answered this short and simple as

No frequent deletion - hash map. (Everything O(1))
Frequent deletion - Rb tree (Everything O(logN))

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.