Page 1 of 1

Basic Collections

#1 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4574
  • View blog
  • Posts: 8,014
  • Joined: 08-June 10

Posted 12 July 2011 - 01:40 PM

*
POPULAR

Learning C# Series
Basic Collections

Often we find that, rather than a single value, we must keep track of several. We could create a variable for each value we want to keep track of, but this leads to an impossible solution very quickly. So what do we use?

Collections, of course. Collections can contain an arbitrary number of values in a single container.

Why is this important to learn about?

Because rarely do we ever work with single instances of objects, in programming or life itself. It's very important to learn how to group data together in a proper collection so that it can be processed as a group.

Definitions of terms used.

Collection: a programming construct that can contain an arbitrary number of other constructs.
Arrays: http://msdn.microsof...y/9b9dty7d.aspx
Lists: http://msdn.microsof...y/6sh2ey19.aspx
Queues: http://msdn.microsof...y/7977ey2c.aspx
Stacks: http://msdn.microsof...y/3278tedw.aspx
FIFO: First In, First Out
LIFO: Last In, First Out

Note: All examples were created using Visual Studio 2010, targetting the .NET Framework 4.0. We'll do our best to point out anything that might not work in older versions.

Basic Collections

Arrays

We'll start with the simplest, and most basic of collections: the Array. Here's the basic structure of an array declaration:

Type[] variableName = new Type[capacity];


Here's a few more concrete examples:

int[] a = new int[10];
string[] b = new string[5];


The array named a, can hold 10 integer values. The array named b can hold 5 strings. Note that arrays are type-safe; you can't store strings in an int[], or vice-versa.

Now, when we initialize an array, it's important to understand that we haven't initialized the values of the array. a holds 10 integers, but they've all been set to int's default value (0). b holds 5 strings, but they're all null, since that's the default value for strings, as well as all other reference types.

You can access each individual value contained in an array using it's index.
important note: arrays and other collections in C# are zero-based, meaning that the first value is always at index 0, not 1.

int[] a = new int[10];
a[0] = 1;
a[1] = 5 + 3;
a[2] = 50;
a[3] = a[0];


In the previous example, I assigned a value to the first four values in the array. Reminder, arrays are zero-based.

Sometimes we want to cycle through all an array's values. For this, we can use loops. Check the tutorial written by CodingSup3rnatur@l-360 called Control Structures for more information about using loops.

There's also a shortcut method to initialize arrays:

string[] names = { "Curtis", "Clint", "Jason" };


The compiler can inferr from the statement on the right that we want to create a string[3]. This is a shortcut, short for this:

string[] names = new string[3];
string[0] = "Curtis";
string[1] = "Clint";
string[2] = "Jason";


Now, what happens if we try to access a value outside of an array's bounds, either below 0 or above the largest index? We get an exception, of course. The following:

string[] names = { "Curtis", "Clint", "Jason" };
names[3] = "Bob";


Produces this exception:

Attached Image

So this means that our arrays have explicit bounds, and we cannot move outside them. What do we do when we need a more dynamic container, for when we don't know how many items we're going to add?

Lists

We use Lists, of course. Lists are similar to arrays, except that they allow for dynamic sizing. When you create a list, you don't provide a size:

List<string> names = new List<string>();


This creates an empty list. Now, we can add to it:

List<string> names = new List<string>
names.Add("Curtis");
names.Add("Clint");
names.Add("Jason");



Note we can also initialize Lists similar to arrays. The difference is that we have to specify that we're using a list:

List<string> names = new List<string> { "Curtis", "Clint", "Jason" };


We can add as few or as many values as we want. Like arrays, Lists are also type-safe. There is a construct called ArrayList that does not have a type parameter, so you can store any type of object in it. This is dangerous, and I suggest you not use it. It's a holdover from .NET 1.1, when C# didn't have Generics (read the link for more info on generics).

We can add many values at once using AddRange:

List<string> names = new List<string> { "Curtis", "Clint", "Jason" };
List<string> otherNames = new List<string> { "Tom", "Dick", "Harry" };
names.AddRange(otherNames);



Now names contains the names from both lists. AddRange will work with any collection that implements the IEnumerable interface, which is most of them.

We can also force a value to occupy a particular spot using Insert:

names.Insert(0, "Adam");


Instead of simply adding "Adam" to the end, this code puts "Adam" at index 0 (the very beginning, since Lists are also zero-based), and pushes all other names one index up.

There's also an InsertRange method. InsertRange is to Insert as AddRange is to Add.

Now, we may want to remove a particular name:

names.Remove("Curtis");


The List no longer has my name. Note that you will not get an Exception if you try to remove a value that does not exist.

There is also a way to remove whatever element resides in a specific index: RemoveAt:

names.RemoveAt(0);


That will remove the name at the beginning of the list.

There is a third method for removal, RemoveRange. This works slightly differently than the other Range methods. With this, you provide a start index, and a count. It will start at that index and remove that many items from the List.

Note that when you delete from a list, the list collapses down. It does not leave empty spaces. So if I have a list with three values, and delete the middle one, the list collapses down to two values, not three with one empty.

Note that we can also access a list through it's indexer, just like an array.

names[0] = "Bob";


Now, the name that used to be "Curtis" is "Bob". Of course, this leads us to the question again, "what happens if I access an element outside the existing bounds?" Well, you get the same exception.

A List won't resize itself when you try to use an index that doesn't exist. It will only expand when you use Add, AddRange, Insert, or InsertRange. And it will only shrink when you use one of the Remove methods.

Now, there are two specialized collections related to a List. They both grow dynamically, but have a few special properties. First:

Queue

If you're American, you may not have heard this word much. It's far more commonly used in the UK. You can think of a Queue as a line of people at a restaurant. When a person gets in line, he gets in a the rear. When the next table is ready, the person at the front of the line gets it, and leaves the line. Everyone else moves up.

The Queue collection is much the same. When you add items (called "Enqueueing"), they are added at the end, and when you remove them (called "Dequeueing"), you remove them from the front. This is a principle known as FIFO (or First In, First Out).

Here's a declaration of a Queue of strings, as well as queueing a few into it.

Queue<string> queue = new Queue<string>();
queue.Enqueue("Curtis");
queue.Enqueue("Clint");
queue.Enqueue("Jason");



Now the queue contains "Curtis", "Clint", and "Jason". So far, very similar to a List. Let's take something out of the queue:

string next = queue.Dequeue();


Now the varible next contains "Curtis", and queue contains "Clint" and "Jason".

Ok, what if I want to see who's next, but I don't want to call them out of line yet? There's a method for that: Peek:

string waiting = queue.Peek();


Now, the variable waiting contains "Clint", and queue still contains "Clint" and "Jason".

That's all there is to queues. They're quite useful when you need to process a batch of things in a specific order, especially when you're actively adding to the queue as well.

Next, the logical opposite of a queue:

Stack

Stacks are like queues, but opposite. Where queues are FIFO, Stacks are LIFO (or Last In, First Out). To visualize this, imagine a tray for papers on your desk. When you add a paper to the tray, you add it on the top of the Stack. When you reach in for a paper, you pull the top one off, which was the last one added to the tray (LIFO!).

Thus, the first element added to the stack is the last one removed, and the most recent one is the first removed.

The methods are different than for a queue. Instead of Enqueue, it's called Push:

Stack<string> stack = new Stack<string>();
stack.Push("Curtis");
stack.Push("Clint");
stack.Push("Jason");



"Jason" is at the top of the stack, followed by "Clint", followed by "Curtis".

Removing from the stack is called Pop:

string top = stack.Pop();


Now, top contains "Jason", while stack still contains "Clint" and "Curtis".

Peek works similarly to the way it does for a queue: it returns the top value without removing it from the stack.

Stacks are useful for mathematic operations (I did a RPN Calculator tutorial a while back). It's also important to at least understand the concept of stacks if you're going to use recursion, or debug a program (stack trace).

In Conclusion

There are many, many more collections that you can use in the .NET Framework; these are a list of common collections that will be easy and useful for a beginner. I want to leave you with a reminder that all collections in C# are zero-based, so if you ever find yourself out of bounds, make sure you didn't start at 1.

See all the C# Learning Series tutorials here!

Is This A Good Question/Topic? 11
  • +

Replies To: Basic Collections

#2 AdoTheLimey  Icon User is offline

  • D.I.C Head

Reputation: 23
  • View blog
  • Posts: 99
  • Joined: 28-June 10

Posted 12 July 2011 - 02:21 PM

Thanks for the explanation of Queues - I finally understand them now
Was This Post Helpful? 0
  • +
  • -

#3 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4574
  • View blog
  • Posts: 8,014
  • Joined: 08-June 10

Posted 12 July 2011 - 02:43 PM

Glad to help. If anyone else is interested, here's a sample console application that you can paste in and run to see a better explanation of stacks and queues.

Make sure to add breakpoints and inspect values, so you can actually see what's going on inside.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;

namespace CollectionsExample {
    class Program {
        static void Main(string[] args) {
            Console.WriteLine("Press Enter To See Queue Examlpe.");
            Console.ReadLine();
            Console.Clear();
            PrintQueueExample();
            
            Console.WriteLine("\r\nPress Enter To See Stack Examlpe.");
            Console.ReadLine();
            Console.Clear();
            PrintStackExample();

            Console.WriteLine("\r\nPress Any Key to Exit.");
            Console.ReadKey();
        }

        private static void PrintQueueExample() {
            Console.WriteLine("Creating new queue.");
            Queue<int> queue = new Queue<int>();
            PrintCollection(queue, "queue");

            Console.WriteLine("Enqueueing several values.");
            queue.Enqueue(1);
            queue.Enqueue(2);
            queue.Enqueue(3);
            PrintCollection(queue, "queue");

            Console.WriteLine("Dequeueing value.");
            int temp = queue.Dequeue();
            Console.WriteLine("Value Dequeued: {0}", temp);
            PrintCollection(queue, "queue");

            Console.WriteLine("Enqueueing \"4\"");
            queue.Enqueue(4);
            PrintCollection(queue, "queue");

            Console.WriteLine("Dequeueing value.");
            temp = queue.Dequeue();
            Console.WriteLine("Value Dequeued: {0}", temp);
            PrintCollection(queue, "queue");
        }

        private static void PrintStackExample() {
            Console.WriteLine("Creating new stack.");
            Stack<int> stack = new Stack<int>();
            PrintCollection(stack, "stack");

            Console.WriteLine("Pushing several values.");
            stack.Push(1);
            stack.Push(2);
            stack.Push(3);
            PrintCollection(stack, "stack");

            Console.WriteLine("Popping value.");
            int temp = stack.Pop();
            Console.WriteLine("Value Popped: {0}", temp);
            PrintCollection(stack, "stack");

            Console.WriteLine("Pusing \"4\"");
            stack.Push(4);
            PrintCollection(stack, "stack");

            Console.WriteLine("Popping value.");
            temp = stack.Pop();
            Console.WriteLine("Value Popped: {0}", temp);
            PrintCollection(stack, "stack");
        }

        private static void PrintCollection<T>(IEnumerable<T> collection, string collectionName) {
            StringBuilder sb = new StringBuilder();
            foreach (T t in collection)
                sb.Append(string.Format("{0}, ", t.ToString()));
            if(sb.Length > 2)
                sb.Remove(sb.Length - 2, 2);
            string toPrint = sb.ToString();
            Console.WriteLine("{0} contains:", collectionName);
            Console.WriteLine(string.IsNullOrWhiteSpace(toPrint) ? "<<NOTHING>>" : toPrint);
            Console.WriteLine();
        }
    }
}


Was This Post Helpful? 3
  • +
  • -

#4 Jianju  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 15
  • Joined: 11-July 11

Posted 19 July 2011 - 10:12 PM

Very well written. Now I know I should be using a queue instead of an array. Cheers, British person.
Was This Post Helpful? 0
  • +
  • -

#5 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4574
  • View blog
  • Posts: 8,014
  • Joined: 08-June 10

Posted 19 July 2011 - 11:22 PM

Technically, either can work. There's really nothing you can do with a Queue that you can't do with an array (or list) and an index variable. It's just simpler to use for some tasks. Stacks too, but it's even harder to maintain the state yourself. It's just easier to use the appropriate tool for the task. Sometimes, it just makes more semantic sense, and that helps you and others understand your program better.
Was This Post Helpful? 0
  • +
  • -

#6 eLeMeNOhPi  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 06-November 11

Posted 14 December 2011 - 10:17 AM

Thanks for the guide so simple yet useful :)
Was This Post Helpful? 0
  • +
  • -

#7 JizzaDaMan  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 139
  • Joined: 23-May 11

Posted 19 December 2011 - 10:05 AM

Great tutorial, really learnt something new here. Thanks!

also great to see there's someone british out there aswell!
:bigsmile:

:boat:
Was This Post Helpful? 0
  • +
  • -

#8 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4574
  • View blog
  • Posts: 8,014
  • Joined: 08-June 10

Posted 20 December 2011 - 07:36 AM

Ok, who's British?
Was This Post Helpful? 0
  • +
  • -

#9 OhScee  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 12-May 12

Posted 12 May 2012 - 09:52 AM

Great collection!
Thanks for the info~
Was This Post Helpful? 0
  • +
  • -

#10 synlight  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 89
  • View blog
  • Posts: 582
  • Joined: 14-September 11

Posted 10 October 2013 - 08:38 AM

This is an excellent explanation of something I've been trying to wrap my mind around for a few days. Thank you!
Was This Post Helpful? 0
  • +
  • -

#11 dsimer  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 26
  • Joined: 04-August 14

Posted 04 August 2014 - 11:52 AM

View PostCurtis Rutland, on 19 July 2011 - 11:22 PM, said:

Technically, either can work. There's really nothing you can do with a Queue that you can't do with an array (or list) and an index variable. It's just simpler to use for some tasks. Stacks too, but it's even harder to maintain the state yourself. It's just easier to use the appropriate tool for the task. Sometimes, it just makes more semantic sense, and that helps you and others understand your program better.


+1 on the original post - a great explanation that filled in some gaps!

Question: does the use of queues and stacks make a positive impact on memory usage as enqueue/dequeue/push/pop is used? If so, does that mean that they are more beneficial in many iterative cases where one is just looking at each element once? I'm trying to understand the use case.
Was This Post Helpful? 0
  • +
  • -

#12 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4574
  • View blog
  • Posts: 8,014
  • Joined: 08-June 10

Posted 04 August 2014 - 12:30 PM

I'm not absolutely sure about the internals of the built-in Stack<T>/Queue<T> classes, but I'd assume that once an item has been popped/dequeued, the collection is resized. Possibly not for each pop/dequeue, just when it makes the most sense.

For example, List<T> does not resize by one every time you add an element. It seems to double its size when necessary, as shown by this example:

var l1 = new List<int>();
var l2 = new List<int>() { 1 };
var l3 = new List<int>() { 1, 2, 3, 4, 5 };
var l4 = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Console.WriteLine(l1.Capacity);
Console.WriteLine(l2.Capacity);
Console.WriteLine(l3.Capacity);
Console.WriteLine(l4.Capacity);


Capacity shows what the internal collection's size is, not how much the list is currently holding. So I'd assume that Queue and Stack behave similarly.

Now, whether or not that's a potential performance increase depends entirely on the use case and environment. That's why it's hard to make definitive statements about performance these days; there's so much going on at any one time. Resizing a collection is an expensive operation that involves copying all elements from one array into another, which is why you wouldn't want to resize for every add/push/queue, same for removing elements.

You'd have to profile your application to determine which is the most efficient collection to use.

But really, the use case is more for your efficiency than for the computer's efficiency. If using a Stack<T> models your real-life use-case better, you should use it, because it will make the code that much easier to understand at a glance. Basically, what I was saying in that quote is that a big reason to use Stacks and Queues rather than a list and an index/counter is that it's easier for you to comprehend the code when it describes what it's doing at a more high level.

It's easier to see this:

queue.Push(1);
value = queue.Dequeue();


Than it is to see this:

arr[max++] = 1;
value = arr[0];
for(var i = 0; i < max - 1; i++)
  arr[i] = arr[i + 1];
--max;

And know exactly what it does and why.
Was This Post Helpful? 1
  • +
  • -

#13 dsimer  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 26
  • Joined: 04-August 14

Posted 04 August 2014 - 12:40 PM

That makes sense. I didn't consider that there might be a lot to re-sizing the array. That considered, it seems like it would be a negligible savings to use it specifically for the purpose I mentioned, and the bigger the collection the worse the overhead would likely become.

Thanks for a great reply.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1