1

I was reading and I found this question , I do not know what is the right answer of it .. Here is the question :

Suppose you are implementing the address book feature for a cellphone. The address book needs to be kept sorted by person’s last name and support fast access when queried by last name. Which of the following data structures would be a good choice to use for storing the address book? Explain why. Which would be the bad choice and why?

(a) unsorted linked list

(b) sorted linked list

(c) binary search tree

(d) hash table

My answer is to use a hash table because it has key and value ... Is my answer correct ?

Thanks

Kostas Kryptos
  • 4,081
  • 2
  • 23
  • 24
  • Can a hash table be sorted? – JB Nizet Jan 04 '16 at 22:57
  • I do not konw ,.... –  Jan 04 '16 at 23:00
  • Then... read the documentation. That's a great way to learn. – JB Nizet Jan 04 '16 at 23:02
  • what is your answer to this question I posted? –  Jan 04 '16 at 23:03
  • He doesn't want to give you the answer. This sounds like a homework question. He's giving you advice to find the answer yourself. – Troncoso Jan 04 '16 at 23:04
  • yes ,, what is your answer ? –  Jan 04 '16 at 23:05
  • ok .. Hashtables are not sorted. according to this http://stackoverflow.com/questions/5176771/sort-hashtable-by-values So I guess the right answer is binary search tree because it is sorted .. is it correct????? thanks –  Jan 04 '16 at 23:14
  • Perhaps a LinkedHashMap could work? https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html – Simon Jan 04 '16 at 23:16
  • Why not binary search tree ?? the answer should be one of the alternatives above in the topic .. thank you –  Jan 04 '16 at 23:18
  • @car Part of the task was to explain **why** each of the 4 choices are good/bad. Try adding "good"/"bad" to each and explain why, then ask us for any remaining questions you have. Like, you just learned that for "(d) hash table" it is: *"Bad. Not sorted."* – Andreas Jan 04 '16 at 23:21
  • unsorted linked list is bad, because it is unsorted .. Now I do not understand the difference between using of binary search tree and sorted linked list .. thanks –  Jan 04 '16 at 23:26
  • Do they both "support fast access"? – Andreas Jan 04 '16 at 23:27
  • you mean that binary search tree and sorted linked list are good solutions because they support fast access !!! –  Jan 04 '16 at 23:30
  • I didn't say that, and it's wrong. They don't both support fast access. If you had 1000 contacts and you need to find "Smith", how fast would that be? If you can't answer that, you need to learn more about what "linked list" and "binary search" means. – Andreas Jan 04 '16 at 23:31
  • according to this link http://stackoverflow.com/questions/270080/difference-between-a-linkedlist-and-a-binary-search-tree they say that a binary search tree is faster in searching than a linked list .. So that means that a binary search tree support fast access ... so the final answer is to use a binary search tree ... thank you brother :) –  Jan 04 '16 at 23:40

3 Answers3

1

No, generally a hash table is not the best choice for a phone book.

Hashtables have excellent O(1) lookup performance, but they gain that by having little support for walking the book in order. Nearly every scenario I can think of for searching something in a phone book involves not having the answer in the first place.

For example, If I want to look up all people who's name starts with "George", I would not want to know that I needed to query "George Jestson" because that's the value stored in my hash table.

Use an ordered data structure, any kind of tree will allow you to trim values too high or too low, as will an ordered list or an ordered array; however, avoid an ordered linked list, as you still have to transverse the list O(n) to find an entry. You can do better O(n log n) by doing a b-tree search on an array, or just using a linked list tree of some sort.

Edwin Buck
  • 69,361
  • 7
  • 100
  • 138
  • Lookup performance is wonderful if you have the full "key" you need to access the "value". Under any other scenario, it's not the right choice. – Edwin Buck Jan 05 '16 at 00:36
1

Based on the requirements the correct struture to use is binary search tree. Why?

(a) unsorted linked list : NOT Sorted, O(n) search

(b) sorted linked list : Sorted, O(n) search; note that you cannot apply binary search on a linked list single or double

(c) binary search tree : Sorted, O(logn) search

(d) hash table : NOT sorted, O(1) search

(a) and (d) are excluded due to the sorting requirment; then (c) is faster than (b) when searching.

*Just noticed that you also ask "for the bad choice", which is apparently (a) (unsorted linked list)

Kostas Kryptos
  • 4,081
  • 2
  • 23
  • 24
0

(c) binary search tree

Because it is both sorted, and supports fast access.

Jason
  • 11,744
  • 3
  • 42
  • 46