1

I would like to know what is the best data structure for storing the following information:

Let's say we have this string:

1.2.0.0.15.4.22.3.0.0.0.2

The string will also count values with more than 1 one digit. The dots aren't actually necessary, it's just to make clearer what I want.

where every digit in the string represents a counter for something we have to count every minute. So, the 1st minute we counted 1, the 2nd 2, the 3rd 0 and so on. There is no predefined size and also I'd like to make insertions or alterations only when I count something, so the zero's will be actually represented in the structure by nulls. The counting will be incrementally.

Initially the structure will be empty for the first minute.

Improve this question
5
  • 1
    Can the count per minute be more than one digit (ie > 9)? Commented Jan 20, 2011 at 14:05
  • Would it be single digit numbers ie '1' or '2' and no double / triple numbers ie '20' etc ? Commented Jan 20, 2011 at 14:05
  • @thecoop @Steve No it won't be single digit numbers but maybe more than one digit Commented Jan 20, 2011 at 14:09
  • 1
    Then you need a better notation: "010200000504..." Commented Jan 20, 2011 at 14:12
  • @Henk Holterman Yes you are right. Commented Jan 20, 2011 at 14:15

6 Answers 6

Reset to default
6

A List<int?> would work well. It will retain the order that you added the elements in and allows accessing elements at any point and will automatically grow where required.

You could also do List<KeyValuePair<int, int?>> where the Key is the minute and the Value the value.

Another alternative (thanks fearofawhackplanet) is using a Dictionary which means you can reference the data by the minute. The Value of the Dictionary is not nullable as you do not have to add entries for minutes that have no data.

E.g.

Dictionary<int, int> datalist = new Dictionary<int, int>();
int minute = 5;
int data = 3;
datalist.Add(minute, data);
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

agreed but needs to be List<int?>
I like your second idea even more, but this one should surely be List<KeyValuePair<int,int>> (no need to store the null values now). Sorry to be picky :)
Possibly, depends if he wants to record that nothing happened for that minute by the presence of an entry or by no entry. :)
i agree, but if he wants to explicitly store "nothing happened" entries then imho that negates the advantage of the Dictionary and may as well stick with List anyway. I prefer the Dictionary idea precisely because I prefer to not explicitly store the null values.
Consider using smaller number types if possible. If your log grows large enough then the difference can become huge (byte vs int = 4x)
|
1

You could use a Dictionary, it would have the advantage of not having to store any information for the times when you don't have any data. For example:

Dictionary<int, int> data = new Dictionary<int, int>();
data.Add(1,1);
data.Add(2,2);
data.Add(5,5);
data.Add(6,4);

and so on. The downside of this is that if you iterate over the data structure you'll only know what times had zero by the fact that they didn't appear

Improve this answer

1 Comment

+1 Personally I think this is more likely to be what the questioner actually wants than a list of nullable ints.
1

It looks to me like a List<int?> (which is the shorthand syntax for List<Nullable<int>>) would suffice.

That should give you an easily expandable data structure to store your values (including nulls) and allow you to easily iterate over the values.

If you need to do any kind of lookup based on what minute you are trying to find a value for, you might want to switch to Dictionary<int, int?> so you can use the minute as the key.

Improve this answer

3 Comments

(Assuming that each count will be a single digit (0 - 9)).
Might be worth pointing out for those unaware that the two are essentially the same thing.
@Davy8 - Re-worded to make a little more sense.
0

Well, first, you clearly want a data structure that can grow easily. Arrays do not fit that bill. So, I'd first think about using a List<int>. Then you mention that you need to store nulls, so I'd refine this to List<int?>. Additionally, you probably want to query the counter for a given minute, and with a List<int?>, you can do this in O(1) time. Without additional information, this is what I would use.

Improve this answer

4 Comments

Could you please explain the difference between List<int> and List<int?>. I know what List<int> is.
@user579674: A List<int?> is the same as a List<Nullable<int>>. It's a list that can hold nullable ints so that you can store ints and null.
int? is a nullable integer. As you said you need to store nulls, this is more appropriate. Int will always initialize to 0 whereas int? is null. You have a little more complexity with int? as well. For instance, you can test to see if your int? variable has a value (.HasValue) and get the value (.Value).
I tried the List<int?> but I can't make an insertion at any index. Am I doing something wrong?
0

It sounds like you could use a List<int> for your entries, or a List<int?> which allows you to store null values.

Improve this answer

Comments

-1

I'd probably just use a char[] (character array)... You can set them up to be unbounded so you wouldn't have a length problem...

Improve this answer

6 Comments

@ John K. What happens when I have values at points let's say 0,1,2,6,7 and at 3,4,5 there are no values? Will I be able to iterate the null values too?
Sure... A char array could hold a blank value so you could have an array like '0', '1', ' ', '5', '4', ' '...
@John K Yes but don't I have to predefine the size of the array and also define the blank values?
In C# you can define an array as "myArray char[]". This will create an unbounded array of characters... If you want to actually store the "null" rather than "blank" they you could define a variable as '\0' (null character) and then use that whenever you need a null... To add items to the list you can use myArray[myArray.count()] = '0' or whatever number needed... C# arrays index from 0 (not 1) so you'd need to handle the case of an empty array... You'd need to test this, but since array items index from 0 it should work...
@John K Are you sure that this works? Because I'm trying it and I cannot declare an array without assigning anything to it. I get "Use of unassigned local variable myArray". Also AFAIK you must specify the size like this: char[] myArray = new char[10];
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.