Homework Clinic
Science Clinic => Computer Science => Programming and Graphic Design => Topic started by: CBme on Aug 30, 2020
-
Two abstract data types are the ordered list and the unordered list. Explain how these two ADTs are similar and how they will differ. To answer this question, assume that you do not know how they are implemented (that is, whether they are implemented using an array or a linked list).
-
The ordered list will require a mechanism to make sure that new elements are inserted in their appropriate place using some kind of ordering operation, whether this is an ordered insert or a sort. Since items are ordered, searching for and deleting an item might be simplified (for instance, if you are looking for a word in the dictionary and you have reached a word that is alphabetically beyond the word, then you know that you have gone to far or that the word is not in the dictionary). A deletion will have to maintain the ordering of the items in the list. In an unordered list, there is no order at all, so new items can be added at the end, simplifying the add/insert operation, and deleted items can be replaced by the last item in the list so that no "shifting" of elements is needed. Finally, in the unordered list, searching requires looking over every element until the item is found, or the end of the list is reached.