Lesson 2 - Lists with arrays in C# .NET

In the previous lesson, Introduction to collections and genericity, we formally introduced you all to collections and explained what genericity. In today's C# .NET tutorial, we're going to learn more about Lists, which represent one type of collection that we've already encountered before.

Array

First and foremost, let's take a quick peek back to arrays, which were the first collection we learned about throughout the courses. One of the main characteristics of an array is that it has a fixed number of elements. For this reason, it's not even considered a collection by some sources. The elements in an array are indexed numerically, starting from zero.

The main disadvantage to using arrays is that we can't add or delete items during runtime. Unfortunately, we often need to do this. However, there are situations where an array is the perfect choice. This "disadvantage" is the price paid for the high speed that comes with accessing array items. Since the data is of the same type (either exactly the same or of a common ancestor) they take up the same space in memory. Individual array items are stored in memory as an uninterrupted sequence, like in a row. We can imagine an array of integers as something like this:

If we wanted to access the 5th item, we'd simply access the beginning of the array and then jump forward by 4 times the type size (in this case, the size of an int). Reading and writing at array indexes are done within a constant time complexity. If you are confused by this term, you may see it as a way of writing into array indexes immediately and so that we can read them.

Note: If we create an empty numeric array in C# .NET, it's be automatically filled with zeros.

Lists

Lists are collections that allow us to add and delete items at runtime. They can be indexed numerically as arrays, but they don't have to. There are basically two types of lists.

Lists using an array

Lists often take advantage of the fact that although we cannot change the size of an array during runtime, we are able to create new arrays at runtime.

In this case, the list is a class that contains methods for adding and removing elements (and many other useful methods, which aren't relevant to us at the moment). The class essentially wraps an array and contains an extra variable where the number of elements is stored. When an instance is being created, an array of a given amount of elements is created inside, and the variable carrying the number of elements is set to 0. When we add the first element, it's stored at the 1st index in the array and the number of elements is incremented. We'd be able to add elements like this until we fill the array. Once the array is full, we simply create a new array, let's say, twice as big. We copy the elements from the old array into the new array and then throw away the old one. Once this new array is filled as well, the process will be repeated. The List collection, with which we've worked before, actually works this way internally. We can imagine a List using an array internally sort of like this:

The list in the picture contains eight elements. The elements are stored in an internal array of the size of 12 elements. The last four elements are unused and from the outside look as if they aren't even there.

The advantage here is the fast random access to the elements using numeric indexes thanks to the inner array. The downside to it is the time required to create the new array and copy the elements into it, although this process doesn't occur too often. Another less painful drawback is that the collection occupies more memory than necessary. Anyway, this list type is still the most used collection in the .NET framework and is fairly well optimized.

Furthermore, a list using arrays is represented in .NET as the List class (its non-generic version is ArrayList). Now, let's go over the most important methods of the List class:

List methods

List implements the IList interface, represents the core interface of the collection, and contains the following methods:

• Add() - Adds a new element into the list.
• Clear() - Clears all of the elements.
• Contains() - Returns true if the List contains the given element.
• CopyTo() - We already know this method from its use in arrays. It allows us to copy elements from the List to a new array.
• IndexOf() - Returns the index of the first occurrence of a given element in the List.
• Insert() - Inserts a new element at a given index (and moves the other elements).
• Remove() - Removes the element. This feature is very useful when we store instances of a class in the list (e.g. users). We don't have to keep their numerical indexes, we just call it like this: list.Remove(carl).
• RemoveAt() - Removes the element at a given index.

Despite the fact that we've already used the List class like 1000 times, for completeness' sake, here's an example of its use:

{CSHARP_CONSOLE}
List<int> list = new List<int>();
list.Add(5);
list.Add(10);
Console.WriteLine(list[0]);
{/CSHARP_CONSOLE}

The program's output:

Console application
5

The code above creates a List of the int type, adds two numbers to it, and then prints the first element to the console. We work with indexes like we work with arrays. However, we are also able to add elements and remove them during runtime.

The List class itself adds some more methods. Let's go over some of them:

• AddRange() - Adds elements from a given array to the List. Similarly, we call the InsertRange() and RemoveRange() methods. It's a good idea to use this method since since it saves us from having to use an additional loop. The only pitfall is that it can only add items from an array (we'll sort of work around this in a moment).
• AsReadOnly() - Returns the instance of the List from which the elements can only be read. This method is useful when we need to encapsulate the elements.
• Count - A property carrying the number of elements in the List. Notice that the property is not named Length (as in the array), since the length of the List is slightly larger. The List's actual can be obtained through the Capacity property,l. However, this information isn't of much use to us.
• Find() - Searches for the element using a predicate (which is, as we know, a delegate). It's a very simple and effective approach because it allows us to use lambda expression syntax.

Here's how we'd find a number greater than 25 in a List of the int type:

{CSHARP_CONSOLE}
List<int> numbers = new List<int>();
numbers.AddRange(new int[] {30, 14, 3, 21, 54, 98});
int number = numbers.Find(a => a > 25);
Console.WriteLine(number);
{/CSHARP_CONSOLE}

The result:

Console application
30

Find() will return the first found occurrence or the default value of the type (null for objects).

• FindAll() - We can use the FindAll() method sort of like the Find() method. FindAll() finds all of the matching elements and returns a new List containing these elements:

List<int> numbersGreaterThan25 = list.FindAll(a => a > 25);

All of this is done very easily thanks to delegates and lambda expressions. The List class also provides the FindIndex(), FindLast(), and FindLastIndex() methods. Another interesting method is BinarySearch(), which searches an element sort of like the Find() method does. However, it's much faster. The thing is that you have to understand the fact that the List is sorted. More on that when we get to the binary search algorithm.

• Exists() - Exists() works just like Find(), however, it returns whether it was found (true/false) rather than the actual element.
• LastIndexOf() - Another version of the IndexOf() method which returns the index of the last occurrence of a given element in the List.
• RemoveAll() - Removes all of the elements matching a given predicate.
• Reverse() - Reverses the List so that the first element is the last and vice versa.
• Sort() - Sorts the list. It's important that the elements implement the IComparable interface, otherwise, this method will throw an exception. All of the basic classes and structures in the .NET framework implement IComparable, but we have to implement it manually in our own classes.
• ToArray() - A widely used method which creates an array of elements from the list and returns it. Since the array is a standard exchange structure in .NET, we'll use this method very often. Note that methods like AddRange() also take an array as a parameter, as opposed to a List. This allows it to be universal. If we wanted to copy elements from one List to another, here's what we would have to do:

list1.AddRange(list2.ToArray());

Aside from a few other methods, we just went through all that the List class has to offer.

Make sure to try out other methods like Sort(), searching, and so on. We'll get to more detailed work with collections when we get to the LINQ technology.

In the next lesson, Linked Lists in C# .NET, we'll go over the second type of List, which is the Linked list.

Did you have a problem with anything? Download the sample application below and compare it with your project, you will find the error easily.