We’ve looked at several different ways of storing a collection of objects, in pa

Question

We’ve looked at several different ways of storing a collection of objects, in particular:

Lists based on arrays

Single- and double-linked lists (including queues and deques)

Trees, particularly binary search trees

Hash tables

For each of the following applications, indicate which data structure would be most appropriate and give a brief explanation justifying your choice in a technical way using, among other possibilities, the O() times needed to perform various operations.

Online telephone directory. Lookups by last name are extremely frequent – hundreds per second. Insert and delete operations are less frequent, but there still are many per minute. Once each year the entire directory needs to be printed out in alphabetical order by last name.

List of students in a class during registration. Students add and drop fairly frequently, and compulsive instructors insist on being able to get up-to-date, sorted alphabetically, class lists via email whenever a student adds or drops.

Computerized waiting line at the Department of Licensing driver’s license examination station. Employees at the reception desk need to be able to record the names of people as they arrive, then call out their names when they get to the head of the line.

Explanation / Answer

Online telephone directory --

Phone Directory can be efficiently implemented using Trie Data Structure. We insert all the contacts into Trie.

Generally search query on a Trie is to determine whether the string is present or not in the trie, but in this case we are asked to find all the strings with each prefix of ‘str’. This is equivalent to doing a DFS traversal on a graph. From a Trie node, visit adjacent Trie nodes and do this recursively until there are no more adjacent. This recursive function will take 2 arguments one as Trie Node which points to the current Trie Node being visited and other as the string which stores the string found so far with prefix as ‘str’.

User will enter the string character by character and we need to display suggestions with the prefix formed after every entered character.
So one approach to find the prefix starting with the string formed is to check if the prefix exists in the Trie, if yes then call the displayContacts() function. In this approach after every entered character we check if the string exists in the Trie.

It takes O(1) to create a new node. It is not necessarily O(1) but O(C) where C is a constant.

Waiting line --

A queue is a data structure that is best described as "first in, first out". A real world example of a queue is people waiting in line at the bank. As each person enters the bank, he or she is "enqueued" at the back of the line. When a teller becomes available, they are "dequeued" at the front of the line.

Perhaps the most common use of a queue within a topcoder problem is to implement a Breadth First Search (BFS). BFS means to first explore all states that can be reached in one step, then all states that can be reached in two steps, etc. A queue assists in implementing this solution because it stores a list of all state spaces that have been visited.

class StateNode {
int xPos;
int yPos;
int moveCount;
}

class MyQueue {
StateNode[] queueData = new StateNode[2500];
int queueFront = 0;
int queueBack = 0;

void Enqueue(StateNode node) {
queueData[queueBack] = node;
queueBack++;
}

StateNode Dequeue() {
StateNode returnValue = null;
if (queueBack > queueFront) {
returnValue = queueData[queueFront];
QueueFront++;
}
return returnValue;
}

boolean isNotEmpty() {
return (queueBack > queueFront);
}
}

The time complexity for insertion is O(1) while deletion is O(n) (in the worst case) for a single operation.

List of students in a class during registration --

This can be done using Linked list
A linked list is a data structure that can hold an arbitrary number of data items, and can easily change size to add or remove items. A linked list, at its simplest, is a pointer to a data node. Each data node is then composed of data (possibly a record with several data values), and a pointer to the next node. At the end of the list, the pointer is set to null.

By nature of its design, a linked list is great for storing data when the number of items is either unknown, or subject to change. However, it provides no way to access an arbitrary item from the list, short of starting at the beginning and traversing through every node until you reach the one you want. The same is true if you want to insert a new node at a specific location. It is not difficult to see the problem of inefficiency.

class ListNode {
String data;
ListNode nextNode;
}
ListNode firstNode;

complexity is O(n).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.