2

If I have some arbitrary data structure, what can I say about this structure if the following scenarios hold:

(1) If I put five elements into a data structure, then it is possible to retrieve those same five elements in that same order. For example, if I put the numbers 4, 6, 2, and 7 into an array, and I retrieve the first element, it will be a 4.

(2) If I put five elements (that can be compared) into a data structure, then they will always be sorted by some criteria. That is, if the criteria is increasing magnitude and I put 4, 6, 2, and 7 into this structure, and I retrieve the first element, it will be a 2.

(3) If I put five elements into a data structure, there is no operation that I can perform that will insure that I retrieve back the first element that I put in it.

(4) If I put five elements into it, then adding any elements that are already in the structure will have no impact on the structure.

EDIT: I am not asking for the names of the data structures that would have these properties. One would be like a List, 2 would be a binary search tree or something, 3 would be a Hash, and four would be a HashSet or many other implementions of collections that don't allow duplicates. I'm asking for property names. For example the ability to say "For this problem we need to use an ordered data structure..."

Jeremy
  • 5,365
  • 14
  • 51
  • 80
  • 1
    @OliCharlesworth Nope. I was having a conversation with a friend and I used "ordered" for the first and "sorted" for the second, but he disagreed that those were the right descriptions. – Jeremy Mar 31 '12 at 00:01
  • 1
    (3) is called *garbage collection*. – Kerrek SB Mar 31 '12 at 00:03
  • @Jeremy: for this see http://stackoverflow.com/questions/1084146/what-is-the-difference-between-an-ordered-and-a-sorted-collection – Thilo Mar 31 '12 at 00:04
  • Interesting question, but not really a SO question – Ruan Mendes Mar 31 '12 at 00:04

4 Answers4

4

(1) is ordered;

(2) is probably sorted;

(3) is unordered;

(4) is contains no duplicates

I'm sorry, (4) is something of a cop-out, but it's all I can think of.

Carl Manaster
  • 39,912
  • 17
  • 102
  • 155
  • 1
    Well 4 is basically the definition of a Set. A collection of *distinct* objects. Can't think of any adjective for that either though. `settiveness` has an interesting ring to it, but I fear isn't in any dictionary ;) – Voo Mar 31 '12 at 01:00
2

(1) FIFO: the data structure maintains insertion order

(2) sorting takes place in the data structure

(3) that is not a property, but a lack thereof. Hash-based structures will do that. Unless you mean that you want a guarantee that the elements will be shuffled (your regular HashMap is deterministic in what it does after all). In this case it would be a "randomizing" or "shuffling" collection. A mixer.

(4) a set, the data structure ensures distinct elements (means that comparisons take place, and sorting or hashing)

Thilo
  • 257,207
  • 101
  • 511
  • 656
0

(1) is a queue, (2) a sorted list, I don't quite see what you mean with (3), and (4) is a set.

jimw
  • 2,548
  • 15
  • 12
  • I'd say (2) is "sorted", not just "ordered". http://stackoverflow.com/questions/1084146/what-is-the-difference-between-an-ordered-and-a-sorted-collection – Thilo Mar 31 '12 at 00:03
-1

I don't think there exist a data structure with all scenarios you listed.

Generally, if you were to implement such a structure, it can be called an Abstract Data Type. With such a data type you provide all functionalities i.e. you abstract the working which correspond to the scenarios above.

In Java, List, Queue, and many more are examples of Abstract data types.

ajmartin
  • 2,379
  • 2
  • 26
  • 42
  • I don't think the OP wanted `one structure to rule them all`! (1) and (2) are already mutually exclusive – kaveman Mar 31 '12 at 00:10