Dynamic list, also known as List<T> is a versatile and widely used data structure in programming. Unlike arrays, which have a fixed size, lists can grow and shrink dynamically, making it an ideal choice for situations where you need to manage collections of items without knowing the exact number of elements in advance. It allows for direct access to elements through an index, much like an array, offering a blend of flexibility and efficiency.
Lists are generic data types, and because of that, a list can hold any type of element, from numbers and text, to more complex objects, like instances of custom classes. Here is a quick example of how you can use lists:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
using
System;
using
System.Collections.Generic;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a list of primitive data type, such as string
List<string> stringList = new List<string>();
// add some elements to it
stringList.Add("cat");
stringList.Add("dog");
stringList.Add("man");
// create a list of a more complex type, such as a custom class
List<Student> classList = new List<Student>();
// add a new instance of the custom class as element of the list
classList.Add(new Student() { Surname = "John", Name = "Doe", Age = 18 });
// access a variable of the custom class element in our list
int age = classList[0].Age;
Console.ReadLine();
}
}
class
Student
{
public string Name { get; set; }
public string Surname { get; set; }
public int Age { get; set; }
}
}
|
One of the key advantages of using the list is its ability to dynamically adjust its size. When you add elements to a list, it automatically expands to accommodate new items. This means that you don't need to specify the size of the list upfront, unlike with arrays, but also have the nice feature of accessing elements by their index (like you do with arrays), unlike with linked lists, while also being generic, unlike array lists. So, really, lists are one of the most used data structures because they really are best of all worlds: they eliminate the rigidity of array fixed sizes, eliminate the downside of linked lists not being able to access any element by index at will, and still keep the key feature of being strongly typed generic, and all this while still maintaining a very good performance.
One thing to notice about the List is the fact that once you declare it of a certain type, you cannot add any other types to it. In other words, if you declare a list of type string, you can only add string variables to it, and no other type.
Additional Information
Lists contain internally a normal array. The way lists deal with an unknown number of elements is by doubling the size of their internal array each time it's about to get filled. This means that lists can get to store a lot of items in very few performance steps, thorugh these doublings of their internal container. Even better, lists have an overload constructor where you can specify an int representing the starting size of their internal array, such that they start with the desired number of elements from the beginning.
Adding elements is generally fast, except the times when the internal array must expand to accommodate more elements. This resizing process, although rare, takes more time than simply adding an element to an existing space. However, this impact is mitigated by the fact that such expansions happen infrequently, and over many additions, the time taken per operation averages out to be relatively quick, a concept known as amortized complexity.
Searching for an element or removing elements (by index or value) involves going through the list, making these operations linear in time complexity; they take longer as the list grows.
The most important methods of lists are:
Add(), AddRange() - appends a new element (respectively, a collection of elements) to the end. We can keep adding elements to the collection until memory runs out. Example:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
using
System;
using
System.Collections.Generic;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a list of strings
List<string> list = new List<string>();
// use Add method to add elements
list.Add("cat");
list.Add("dog");
list.Add("man");
// print the elements of the list
Console.WriteLine("Initial values:");
foreach (string value in list);
Console.WriteLine(value);
Console.WriteLine();
// declare another collection of elements
string[] array = new string[2];
array[0] = "cow";
array[1] = "bird";
// use AddRange method to add an entire collection at once
list.AddRange(array);
// loop through the list
Console.WriteLine("Final values:");
foreach (string value in list);
Console.WriteLine(value);
Console.ReadLine();
}
}
}
|
Notice that AddRange() does not necessarily expect another list, it works with different types of collections too, such as raw arrays. This is the output:
Clear() - clears the elements of a list. Example:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
using
System;
using
System.Collections.Generic;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a list of bools
List<bool> list = new List<bool>();
// add few elements
list.Add(true);
list.Add(false);
list.Add(true);
// print the number of elements
Console.WriteLine("Number of elements: " + list.Count);
Console.WriteLine();
// clear the list
list.Clear();
// print the new number of elements
Console.WriteLine("Number of elements after Clear: " + list.Count);
Console.ReadLine();
}
}
}
|
This is the output:
Sort(), Reverse() - sorts a list, or reverses the order of its elements. In case of sorting, for strings it orders them alphabetically; for integers (or other numbers) it orders from lowest to highest. Example:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
using
System;
using
System.Collections.Generic;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a list of strings
List<string> list = new List<string>();
// add a few elements
list.Add("tuna");
list.Add("velvetfish");
list.Add("angler");
// print the elements of the list
Console.WriteLine("Initial values:");
foreach (string value in list);
Console.WriteLine(value);
Console.WriteLine();
// sort fish alphabetically, in ascending order (A - Z)
list.Sort();
// print elements after sorting
Console.WriteLine("Elements after sort:");
foreach (string value in list);
Console.WriteLine(value);
Console.WriteLine();
// reverse the order of elements
list.Reverse();
// print the elements again
Console.WriteLine("Reversed elements:");
foreach (string value in list);
Console.WriteLine(value);
Console.ReadLine();
}
}
}
|
With this result:
Insert(), InsertRange(), Remove(), RemoveAt() - allow adding or removing one element or a collection of elements. With the exception of Remove(), all require a numerical index at which to insert or remove. Example:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
using
System;
using
System.Collections.Generic;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// declare a list
List<int> list = new List<int>();
// add elements at the end, using the Add method
for (int i = 0; i < 100000; i++)
list.Add(i); // fast operation
// clear the list
list.Clear();
// add elements at the start, using the Insert method
for (int i = 0; i < 100000; i++)
list.Insert(0, i); // slow operation
// declare a new int array
int[] array = new int[3];
array[0] = 7;
array[1] = 6;
array[2] = 7;
// insert the new array into the list, at position 1
list.InsertRange(1, array);
// remove element with value 5 (NOT index 5!)
list.Remove(5);
// remove element at index 2
list.RemoveAt(2);
Console.ReadLine();
}
}
}
|
IndexOf() - searches for the provided element in the list, and returns its index, if found. Example:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
using
System;
using
System.Collections.Generic;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// declare a list
List<int> primes = new List<int>() { 19, 23, 29 };
// search for an element that exists
int index = primes.IndexOf(23);
Console.WriteLine(index);
// try to get the index of an element that doesn't exist
index = primes.IndexOf(10);
Console.WriteLine(index);
Console.ReadLine();
}
}
}
|
With this result (-1 representing a "non-existing" index):
Insert(), InsertRange(), Remove(), RemoveAt() - allow adding or removing one element or a collection of elements. With the exception of Remove(), all require a numerical index at which to insert or remove. Example:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
using
System;
using
System.Collections.Generic;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// declare a list
List<int> list = new List<int>();
// add elements at the end, using the Add method
for (int i = 0; i < 100000; i++)
list.Add(i); // fast operation
// clear the list
list.Clear();
// add elements at the start, using the Insert method
for (int i = 0; i < 100000; i++)
list.Insert(0, i); // slow operation
// declare a new int array
int[] array = new int[3];
array[0] = 7;
array[1] = 6;
array[2] = 7;
// insert the new array into the list, at position 1
list.InsertRange(1, array);
// remove element with value 5 (NOT index 5!)
list.Remove(5);
// remove element at index 2
list.RemoveAt(2);
Console.ReadLine();
}
}
}
|
Contains(), Exists(), Find() - they all provide searching. They vary in arguments accepted. With Predicates, we influence what elements match. We haven't learn about LINQ and predicates, but they are not the scope of this lesson. Return to this lesson when you learn them. Example:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
using
System;
using
System.Collections.Generic;
using
System.Linq;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// declare a list with three elements
List<string> list = new List<string>();
list.Add("cat");
list.Add("dog");
list.Add("moth");
// search for some element
if (list.Contains("dog"))
Console.WriteLine("Dog was found");
// search for some element regardless of string casing
// ... this is the LINQ method with the same name
if (list.Contains("MOTH", StringComparer.OrdinalIgnoreCase))
Console.WriteLine("MOTH was found (insensitive)");
// search for an element that doesn't exist
Console.WriteLine(list.Contains("fish"));
// declare another list
List<int> list2 = new List<int>();
list2.Add(7);
list2.Add(11);
list2.Add(13);
// see if any elements with values greater than 10 exist
bool exists = list2.Exists(element => element > 10);
Console.WriteLine(exists);
// check for numbers less than 7
exists = list2.Exists(element => element < 7);
Console.WriteLine(exists);
// find first element greater than 11
int result = list2.Find(element => element > 11);
Console.WriteLine(result);
Console.ReadLine();
}
}
}
|
Output:
There are a ton of other methods that lists have, these are just the most used. Be sure to read the in-depth documentation on the Microsoft website, at least in an informative way, before you start writing your own version of ToArray(), for instance.
The most important properties of lists are:
Capacity - the number of elements of the internal array (filled or empty); you can pass an integer to the constructor of the list (which sets an initial capacity) to improve allocation performance
Count - gets the number of elements of the list. Count, on the list type, is equal to Length on arrays.