Selection of Appropriate Data Structures We covered a number of different data s

Question

Selection of Appropriate Data Structures We covered a number of different data structures during this course, which leads us to revisit the question of why to avoid using simple arrays, or lists, for storing collections of items, and extend it with the question of which data structure to use for a particular problem. Let's discuss the first of those questions: why use anything other than arrays or lists? It should be relatively easy to see why we might want to avoid arrays:

They require contiguous blocks of memory, which can pose problems if memory becomes fragmented.

Arrays are static in terms of size. If you need to add more items than will fit in the array, you have to resize the array.

There are no iterators for arrays, which means that often the only way to traverse an array is to set up an indexed loop, which is prone to off-by-one errors.

In defense of arrays, contiguous blocks of memory are less problematic now that computers have much greater memory capacities than they used to have. Still, if you are writing software for a device with limited memory, you can still have availability problems with contiguous memory. Resizing an array can be relegated to a static, reusable method, so that you don't have to worry about writing this code every time you need to resize an array. As far as array traversals go, programmers are keenly aware of the off-by-one error and are better at avoiding it. Java has also alleviated this problem with its new for-each syntax.

Lists would seem to be ideal, all-purpose data structures. They are dynamic, meaning items can be freely added and removed without the need for resizing an array. Array resizing is done for you for array-based lists, and is not applicable to linked lists. Linked lists eliminate the problems associated with contiguous memory requirements, since each node in the list can point to a neighboring node anywhere in memory. Lists also have iterators that enable clean traversals using a consistent interface.

So why, then, bother with any structure beyond lists? The two major reasons are:

Some data structures are specially designed to be used for specific types of applications, which are not possible (or at least not as easily done) with general purpose lists.

Strict enforcement of rules that govern how items may be accessed is important.

First of all, some of the data structures we discussed have special structures that enable them to be used for specific applications. Binary search trees, for example, enable us to store items in an ordered way that inherently incorporates binary search capabilities. While the binary search algorithm can be used quite effectively on an ordered array-based list, it is not as effective with a linked list, since retrieving a given node in a linked list by its position has a worst case time of O(N/2), which is significantly greater than the O(logN) time for an array-based list. Higher order trees, which involve greater branching and are thus shorter than binary trees, can provide even faster running times for searches and retrievals. The B tree is specially desgined to deal with data stored outside of main memory, for example on a hard drive. The structure of a B tree is tailored to the block size of the hard drive being used, which minimizes the number of expensive disk access operations.

The graph data structure is also unique in the way ther vertices can be connected to each other. Graphs are basically non-structured, rootless, trees. Any vertex can be the starting point of a traversal or search, and the hierarchy of the vertices in a graph depend on which vertex is chosen as the starting point. Graphs also allow cyclical connections, which trees forbid. None of the shortest path algorithms we discussed will work on any structure other than a graph.

The priority queue data structure is highly specialized because of its reliance on the underlying binary heap. The binary heap, as we discussed, can be implemented as an array by virtue of the fact that a binary heap must be a complete tree. A complete tree ensures there will be no gaps in the tree, and allows any node to be accessed in O(1) time by utilizing mathematical formulas that only work with complete trees. (A full tree is a special case of a complete tree, so whatever is possible with a complete tree is also possible with a full tree).

Data structures that rely on hashing (HashMap, HashSet) are designed to allow, on average, O(1) access of any item. While arrays and array-based lists also allow O(1) random access, they do so only based on position. Hashed structures allow O(1) access based on either the items themselves, or based on keys associated with the items.

This leaves us with the stack, the queue, and the deque, which would seem to have the weakest argument in their favor. The primary distinction of these structures is the way they limit access to items at one end or the other. A secondary distinction is that they are, by definition, not traversable. Array-based lists and doubly-linked lists can both easily function as stacks, queues, or deques. The main argument against using a list in this capacity is that it opens the door for misuse if a library component is designed to use a stack, queue, or deque internally, but the actual implementation uses a list. A developer who uses such a component may, for example, be able to violate the desired restrictions of the component and access an item stored in the middle of the structure. This may or may not be a serious problem, depending on the application, but if a design calls for LIFO mechanics for a collection, and a stack data structure is available, why not use it instead using a list? Perhaps the most confusing thing about using stacks, queues, and deques is that in many cases there may be a predominant need for LIFO ir FIFO mechanics, but also an occasional need for non-LIFO or non-FIFO mechanics. For example, consider the deck of cards in a poker game application. Cards are typically drawn from the top of the deck, and discarded to the bottom of the deck. This obeys FIFO mechanics, suggesting that a queue would be the appropriate structure to use for modeling the deck. But how then, should we deal with shuffling the deck, which requires access to cards between the first and last cards? If we want to strictly enforce the appropriate access rules, we would probably do something like store the cards in a list when shuffling them, then move them into a queue for game play. Granted, moving all the cards to another data structure is a O(N) operation, but for a standard deck of playing cards, O(N) is equivalent to O(52), which is negligible.

A better justification for ensuring the proper access rules are obeyed in the poker example is if we assume the entire deck exists as a component that is part of a toolkit for building games based on a standard deck of playing cards. If the deck is accessible by some function as a list, that function could potentially violate the expected access rules, which could lead to unexpected results. For example, someone could build a poker game that selectively deals cards from the middle of the deck, and could even stack the deck in favor of one player. Users who play the game would have no reason to expect such behavior, and may become disillusioned with the game.

Explanation / Answer

We should be using DEQUEUE and Hashmap for desiging Poker.

HashMap - For maintaing card number as key and it's importance as value.
Dequeue - For maintaing card that have been used in game

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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