9.4 Introduction to Collections
The .NET Framework Class Library provides several classes, called collections, used to store groups of related objects. These classes provide efficient methods that organize, store and retrieve your data without requiring knowledge of how the data is being stored. This reduces app development time.
You’ve used arrays to store sequences of objects. Arrays do not automatically change their size at execution time to accommodate additional elements—you must do so manually by creating a new array or by using the Array class’s Resize method.
9.4.1 List<T> Collection
The generic collection class List<T> (from namespace System.Collections.Generic) provides a convenient solution to this problem. The T is a placeholder—when declaring a new List, replace it with the type of elements that you want the List to hold. This is similar to specifying the type when declaring an array. For example,
List<int> intList;
declares intList as a List collection that can store only int values, and
List<string> stringList;
declares stringList as a List of references to strings. Classes with this kind of placeholder enabling them to be used with any type are called generic classes. Generic classes are discussed in Chapter 20. Additional generic collection classes are discussed in Chapter 21. Figure 21.2 provides a table of collection classes. Figure 9.5 shows some common methods and properties of class List<T>.
Fig. 9.5 Some methods and properties of class List<T>.
| Method or property | Description |
|---|---|
Add |
Adds an element to the end of the List. |
AddRange |
Adds the elements of its collection argument to the end of the List. |
Capacity |
Property that gets or sets the number of elements a List can store without resizing. |
Clear |
Removes all the elements from the List. |
Contains |
Returns true if the List contains the specified element and false otherwise. |
Count |
Property that returns the number of elements stored in the List. |
IndexOf |
Returns the index of the first occurrence of the specified value in the List. |
Insert |
Inserts an element at the specified index. |
Remove |
Removes the first occurrence of the specified value. |
RemoveAt |
Removes the element at the specified index. |
RemoveRange |
Removes a specified number of elements starting at a specified index. |
Sort |
Sorts the List. |
TrimExcess |
Sets the Capacity of the List to the number of elements the List currently contains (Count). |
9.4.2 Dynamically Resizing a List<T> Collection
Figure 9.6 demonstrates dynamically resizing a List object. Line 11 creates a List of strings, then lines 14–15 display the List’s initial Count and Capacity, respectively:
The
Countproperty returns the number of elements currently in theList.The
Capacityproperty indicates how many items theListcan hold without having to grow.
When the List is created, both are initially 0—though the Capacity is implementation dependent.
Fig. 9.6 Generic List<T> collection demonstration.
Alternate View
1 // Fig. 9.6: ListCollection.cs
2 // Generic List<T> collection demonstration.
3 using System;
4 using System.Collections.Generic;
5
6 class ListCollection
7 {
8 static void Main()
9 {
10 // create a new List of strings
11 var items = new List<string>();
12
13 // display List’s Count and Capacity before adding elements
14 Console.WriteLine("Before adding to items: " +
15 $"Count = {items.Count} ; Capacity = {items.Capacity}");
16
17 items.Add("red"); // append an item to the List
18 items.Insert(0, "yellow"); // insert the value at index 0
19
20 // display List’s Count and Capacity after adding two elements
21 Console.WriteLine("After adding two elements to items: " +
22 $"Count ={items.Count}; Capacity = {items.Capacity}");
23
24 // display the colors in the list
25 Console.Write(
26 "
Display list contents with counter-controlled loop:");
27 for (var i = 0; i < items.Count; i++)
28 {
29 Console.Write($" {items[i]}");
30 }
31
32 // display colors using foreach
33 Console.Write("
Display list contents with foreach statement:");
34 foreach (var item in items)
35 {
36 Console.Write($" {item}");
37 }
38
39 items.Add("green");// add "green" to the end of the List
40 items.Add("yellow"); // add "yellow" to the end of the List
41
42 // display List’s Count and Capacity after adding two more elements
43 Console.WriteLine("
After adding two more elements to items: " +
44 $"Count = { items.Count} ; Capacity = {items.Capacity}");
45
46 // display the List
47 Console.Write("
List with two new elements:");
48 foreach (var item in items)
49 {
50 Console.Write($" {item}");
51 }
52
53 items.Remove("yellow"); // remove the first "yellow"
54
55 // display the List
56 Console.Write("
Remove first instance of yellow:");
57 foreach (var item in items)
58 {
59 Console.Write($" {item}");
60 }
61
62 items.RemoveAt(1); // remove item at index 1
63
64 // display the List
65 Console.Write("
Remove second list element (green):");
66 foreach (var item in items)
67 {
68 Console.Write($" {item}");
69 }
70
71 // display List’s Count and Capacity after removing two elements
72 Console.WriteLine("
After removing two elements from items: " +
73 $"Count = {items.Count}; Capacity = {items.Capacity} ");
74
75 // check if a value is in the List
76 Console.WriteLine("
"red" is "+
77 $"{(items.Contains("red") string.Empty : "not ")}in the list");
78
79 items.Add("orange");// add "orange" to the end of the List
80 items.Add("violet");// add "violet" to the end of the List
81 items.Add("blue");// add "blue" to the end of the List
82
83 // display List’s Count and Capacity after adding three elements
84 Console.WriteLine("
After adding three more elements to items: " +
85 $"Count = {items.Count}; Capacity = {items.Capacity}");
86
87 // display the List
88 Console.Write("List with three new elements:");
89 foreach (var item in items)
90 {
91 Console.Write($" {item}");
92 }
93 Console.WriteLine();
94 }
95 }
Before adding to items: Count = 0; Capacity = 0 After adding two elements to items: Count = 2; Capacity = 4 Display list contents with counter-controlled loop: yellow red Display list contents with foreach statement: yellow red After adding two more elements to items: Count = 4; Capacity = 4 List with two new elements: yellow red green yellow Remove first instance of yellow: red green yellow Remove second list element (green): red yellow After removing two elements from items: Count = 2; Capacity = 4 "red" is in the list After adding three more elements to items: Count = 5; Capacity = 8 List with three new elements: red yellow orange violet blue
Adding and Inserting Elements
The Add and Insert methods add elements to the List (lines 17–18):
The
Addmethod appends its argument to the end of theList.The
Insertmethod inserts a new element at the specified position.
Insert’s first argument is an index—as with arrays, collection indices start at zero. The second argument is the value to insert at the specified index. To make room for the new element, the indices of the elements at the specified index and above each increase by one—in this case, "red" initially was at index 0, but now is at index 1, so that "yellow" can be inserted at index 0.
Count and Capacity
Lines 21–22 display the List’s Count (2) and Capacity (4) after the Add and Insert operations. When line 17 executes, the List grows, increasing its Capacity to 4 so that the List can accommodate four elements. One of these elements is immediately occupied by "red". At this point, the List’s Count is 1. When line 18 executes, there’s still room for three more elements, so "yellow" is inserted and the Count becomes 2.
Iterating Through a List’s Contents
Lines 27–30 display the items in the List. Like array elements, List elements can be accessed by placing the index in square brackets after the List variable’s name. The indexed List expression can be used to modify the element at the index. Lines 34–37 display the List using the preferred foreach statement.
Adding More Elements and Growing the List
Lines 39–51 add more elements to the List, then display its Count, Capacity and contents once again.
Removing Elements
The Remove method deletes the first element with a specific value (line 53), returning true if successful and false otherwise. Lines 57–60 show the List’s contents after line 53 executes. A similar method, RemoveAt, removes the element at the specified index (line 62). When an element is removed through either of these methods, the indices of all elements above that index decrease by one—the opposite of the Insert method. Lines 66–69 show the List’s contents after line 62 executes. Lines 72–73 display the List’s Count (2) and Capacity (4) after the remove operations. At this point, there’s room in the List for two more elements.
Determining Whether an Element Is in the List
Line 77 uses the Contains method to check whether an item is in the List. The Contains method returns true if the element is found in the List and false otherwise. The method compares its argument to each element of the List in order until the item is found, so using Contains on a large List is inefficient.
Adding More Elements and Growing the List
Lines 79–81 add three more elements to the List. Before lines 79–80 execute, Count is 2 and Capacity is 4, so there’s room in the List for the two new elements added by thosestatements. When Line 81 executes, however, Count and Capacity are both 4, so the List doubles its Capacity to 8 and the Count becomes 5, leaving room for three more elements.
Doubling the Capacity
When a List grows, it must (behind the scenes) create a larger internal array and copy each element to the new array. This is a time-consuming operation. It would be inefficient for the List to grow each time an element is added. To minimize the number of memory reallocations, a List doubles its capacity when more memory is required.1
Performance Tip 9.1
Doubling a List’s Capacity is an efficient way for a List to grow quickly to be “about the right size.” This operation is much more efficient than growing a List by only as much space as it takes to hold the element(s) being added. A disadvantage is that the List might occupy more space than it requires. This is a classic example of the space/time trade-off.
Performance Tip 9.2
It can be wasteful to double a List’s size when more space is needed. For example, a full List of 1,000,000 elements resizes to accommodate 2,000,000 elements when one new element is added. This leaves 999,999 unused elements. You can use TrimExcess (as in yourListObject.TrimExcess()) to reduce a List’s Capacity to its current Count. You also can set the Capacity directly to control space usage better—for example, if you know a List will never grow beyond 100 elements, you can preallocate that space by assigning 100 to the List’s Capacity or using the List constructor that receives an initial capacity.