CODEWITHSUNDEEP
arraysalgorithmdata-structurescomputer-sciencehashtable
serkank
serkank

Reputation: 23

Choice of Data Structures

I've found the question below in the CS GRE sample test but can't be sure if it's a) or e) Can anyone point out which one it is?

Thanks in advance

Which data structure would be most appropriate to implement a collection of values with the following three characteristics?

Items are retrieved and removed from the collection in FIFO order. There is no a priori limit on the number of items in the collection. The size of an item is large relative to the storage required for a memory address. A) Singly-linked list, with head and tail pointers B) Doubly-linked list, with only a head pointer C) Array D) Binary tree E) Hash table

Upvotes: 2

Views: 1275

Answers (2)

Bill the Lizard
Bill the Lizard

Reputation: 405735

  1. Items are retrieved and removed from the collection in FIFO order.
  2. There is no a priori limit on the number of items in the collection.
  3. The size of an item is large relative to the storage required for a memory address.

Given requirements 1 and 2, I'd say a Singly-linked list, with head and tail pointers is your best bet. You can insert elements quickly with the tail pointer and remove them using the head pointer.

You can eliminate each of the other options based on one or more of the requirements.

Doubly-linked list, with only a head pointer - only having a head pointer makes it hard to implement the FIFO requirement.

Array - imposes an a priori limit on the size of the collection that other data structures do not.

Binary tree - doesn't organize the elements in a way that makes it convenient to implement FIFO.

Hash table - makes FIFO impossible.

Upvotes: 3

Kevin
Kevin

Reputation: 25269

The answer is a queue that is implemented as a linked list, but since that isn't an option, answer A will have to do.

B. no tail pointer means removing from the queue will be O(n) which is worse than list with head and tail pointers.

C. Would implement FIFO but "size of an item is large relative to storage required for a memory address" is a dead give away that a linked list of some kind is expected.

D. maintains sort order but not insertion order so you won't be able to implement FIFO

E. would not be correct because hash tables do not maintain order.

Upvotes: 1

Related Questions