CODEWITHSUNDEEP
c++data-structureslinked-list
Don Lun
Don Lun

Reputation: 2777

What data structure can you use to store elements dynamically and access them efficiently?

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.

Upvotes: 1

Views: 1730

Answers (6)

templatetypedef
templatetypedef

Reputation: 372972

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!

Upvotes: 14

Manoj R
Manoj R

Reputation: 3247

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))

Upvotes: 0

Alvin
Alvin

Reputation: 10458

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).

Upvotes: 5

payne
payne

Reputation: 14187

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.

Upvotes: 2

asciz
asciz

Reputation: 125

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/

Upvotes: 0

Benjamin Lindley
Benjamin Lindley

Reputation: 103733

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

Upvotes: 1

Related Questions