CODEWITHSUNDEEP
data-structurestreelinked-listbinary-search-tree
Faheem Rajput
Faheem Rajput

Reputation: 601

What its best link list or BST for my application

I have a task to develop an electronic phone book in which i have to store names and phone numbers of employees of a company. The data structures available to you are linked list and Binary Search Tree (BST) and i have to choose best supported data structure for my project. Moreover, while selecting any data structure, you also have to keep in consideration insertion, deletion and search operations, because, the company can hire some new employees, search for an employee’s phone number and some old employees can also leave this company. Discuss which data structure do you think would be more suitable for the above discussed scenario. Also discuss the reason why would you prefer this data structure over the other?

Upvotes: 0

Views: 269

Answers (1)

yashdosi
yashdosi

Reputation: 1256

BST would be better. because...

  1. Searching which is the most frequently used function in a phonebook is faster in BST than in linked list.

  2. Insertion takes O(log n) time in average case. In case of linked list if a new node is to be inserted finding the correct location takes O(n) time which is again slower than BST.

  3. Deletion : worst case it requires time proportional to the height of the tree. But in case of linked list is takes constant order time. (This is the only case where linked list is better.)

Thus on an average linked list is better.

P.S. : I am assuming you want to store the phonebook in a sorted manner.

Upvotes: 1

Related Questions