Follow the white rabbit

Dynamic list (List<T>) is one of the most popular data structures used in programming. It does not have fixed size like arrays, and allows direct access through index, unlike linked lists (LinkedList<T>). The dynamic array is also known as “array list”, “resizable array” and “dynamic array”. List<T> holds its elements in an array, which has a bigger size than the count of the stored elements. Usually when we add an element, there is an empty cell in the list’s inner array. Therefore, this operation takes a constant time. Occasionally, the array fills, and it has to expand. This takes linear time, but it rarely happens. If we have a large amount of additions, the average-case complexity of adding an element to List<T> will be a constant. If we sum the steps needed for adding 100,000 elements (for both cases – “fast add” and “add with expand”) and divide by 100,000, we will obtain a constant which will be nearly the same for like adding 1,000,000 elements.

This statistically-averaged complexity calculated for large enough amount of operations is called amortized complexity. Amortized linear complexity means that if we add 10,000 elements consecutively, the overall count of steps will be of the order of 10,000. In most cases add it will execute in a constant time. Searching in List<T> is a slow operation because you have to traverse
through all the elements. Removing by index or value executes in a linear time. It is a slow operation because we have to move all the elements after the deleted one with one position to the left.
The indexed access in List<T> is instant, in a constant time, since the elements are internally stored in an array. Practically, List<T> combines the best of arrays and lists, this being the reason for which it is a preferred data structure in many situations. For example if we have to process a text file and to extract from it all words (with duplicates), which match a regular expression, the most suitable data structure in which we can accumulate them is List<T>, because we need a list, the length of which is unknown in advance and can grow dynamically. The dynamic array (List<T>) is appropriate when we have to add elements frequently, as well as keeping their order of addition and access them through index. If we often need to search or delete elements, List<T> is not the right data structure. Use List<T>, when you have to add elements quickly and access them through index.

The way we declare a List is simple. As we learned from the Generics lesson, <T> actually indicated that we can use any type of data we want, because the method, structure, class, etc, doesn’t care what type of data we are sending to it. In our case, List<T> means that our List can store any kind of elements: int, string, float, etc. This is how we declare and initialize a List<T>:

List<int> list = new List<int>();

By replacing <T> with <int>, we told our List that we want to store elements of type integer. The procedure is the same for any other data type. We can even declare a class with methods and members, and then create a List of that classes type:

using System.Collections;

class Program
{
    static void Main()
    {
        //declare a new List of type custom class, declared below
        List<Test> myList = new List<Test>();

        //add a new instance of the custom class as element of our list
        myList.Add(new Test() { myInt = 5, myString = "some string" });

        //access a variable of the custom class element in our list
        int newInt = myList[0].myInt;

        //call the method inside our custom class stored in our list
        myList[0].MyMethod();
    }
}

//declare some custom class
class Test
{
    public int myInt;
    public string myString;

    public void MyMethod()
    {
        Console.WriteLine(myString);
    }
}

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.

The most important methods of Lists are:

Add() – This appends a new element object to the end. We can keep adding elements to the collection until memory runs out. Example:

using System.Collections;

class Program
{
    static void Main()
    {
        List<int> list = new List<int>();
        list.Add(2);
        list.Add(3);
        list.Add(5);
        list.Add(7);
    }
}

AddRange() – for adding many elements at once, like adding an array to a List, we use the AddRange method. This can simplify code that combines collections. Here is how we use it:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> a = new List<int>();
        a.Add(1);
        a.Add(2);
        a.Add(5);
        a.Add(6);

        // Contains:
        // 1
        // 2
        // 5
        // 6

        int[] b = new int[3];
        b[0] = 7;
        b[1] = 6;
        b[2] = 7;

        a.AddRange(b);

        // Contains:
        // 1
        // 2
        // 5
        // 6
        // 7 [added]
        // 6 [added]
        // 7 [added]
        foreach (int i in a)
        {
            Console.WriteLine(i);
        }
    }
}

Clear() – You can call the instance method Clear() on your List. Example:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<bool> list = new List<bool>();
        list.Add(true);
        list.Add(false);
        list.Add(true);
        Console.WriteLine(list.Count); // 3

        list.Clear();
        Console.WriteLine(list.Count); // 0
    }
}

Sort(), Reverse() – these methods do exactly what their name says: they sort a List, or reverse the order of their elements. In case of sorting, for strings it orders alphabetically; for integers (or other numbers) it orders from lowest to highest. Example:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<string> list = new List<string>();
        list.Add("tuna");
        list.Add("velvetfish");
        list.Add("angler");

        // Sort fish alphabetically, in ascending order (A - Z)
        list.Sort();

        foreach (string value in list)
            Console.WriteLine(value);

        var reverse = list.Reverse();
        // Write contents of list to screen.
        foreach (string value in reverse)
            Console.WriteLine(value);
    }
}

Insert(), Remove(), RemoveAt() – methods used to add or remove elements into a List. RemoveAt() uses a numeric index to specify which element you want to remove. Example:

using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> list = new List<int>();
        for (int i = 0; i < 100000; i++)
        {
            // Insert before first element
            list.Insert(0, i); // SLOW
        }

        //clear list
        list.Clear();
        for (int i = 0; i < 100000; i++)
        {
            // Add to end
            list.Add(i); // FAST
        }

        //declare a new int array
        int[] b = new int[3];
        b[0] = 7;
        b[1] = 6;
        b[2] = 7;

        //insert the new array into the list, at position 1
        list.InsertRange(1, b);

        //remove speciffic element
        list.Remove(5);
        //remove at certain index
        list.RemoveAt(2);
    }
}

IndexOf() – This determines the element index of a certain value in the List collection. It searches for the first position (from the start) of the value. IndexOf has two overloads. It works in the same way as string’s IndexOf. It searches by value and returns the location. Example:

sing System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> primes = new List<int>(new int[] { 19, 23, 29 });

        int index = primes.IndexOf(23); // Exists.
        Console.WriteLine(index);

        index = primes.IndexOf(10); // Does not exist.
        Console.WriteLine(index);
    }
}

Contains(), Exists(), Find(). These methods 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. Example:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        // Create List with three elements.
        var list1 = new List<string>();
        list1.Add("cat");
        list1.Add("dog");
        list1.Add("moth");

        // Search for this element.
        if (list1.Contains("dog"))
            Console.WriteLine("dog was found");

        // Search for this element in any string case.
        // ... This is the LINQ method with the same name.
        if (list1.Contains("MOTH", StringComparer.OrdinalIgnoreCase))
            Console.WriteLine("MOTH was found (insensitive)");

        // This element is not found.
        Console.WriteLine(list1.Contains("fish"));

        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);

        List<int> list3 = new List<int>(new int[] { 19, 23, 29 });

        // Finds first element greater than 20
        int result = list3.Find(item => item > 20);

        Console.WriteLine(result);
    }
}

ToArray() – returns an array composed of the list’s elements. Example:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // List of cities we need to join.
        List<string> cities = new List<string>();
        cities.Add("New York");
        cities.Add("Mumbai");
        cities.Add("Berlin");
        cities.Add("Istanbul");

        // Join strings into one CSV (comma separated values) line.
        string line = string.Join(",", cities.ToArray());
        Console.WriteLine(line);
    }
}

Distinct() – removes duplicates from a list. Example:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        // List with duplicate elements.
        List<int> list = new List<int>();
        list.Add(1);
        list.Add(2);
        list.Add(3);
        list.Add(3);
        list.Add(4);
        list.Add(4);
        list.Add(4);

        foreach (int value in list)
        {
            Console.WriteLine("Before: {0}", value);
        }

        // Get distinct elements and convert into a list again.
        List<int> distinct = list.Distinct().ToList();

        foreach (int value in distinct)
        {
            Console.WriteLine("After: {0}", value);
        }
    }
}

Equality() – Sometimes we need to test two Lists for equality, even when their elements are unordered. We can sort and then compare, or use a custom List equality method. Example:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        List<Cube> cubes = new List<Cube>();

        cubes.Add(new Cube(8, 8, 4));
        cubes.Add(new Cube(8, 4, 8));
        cubes.Add(new Cube(8, 6, 4));

        if (cubes.Contains(new Cube(8, 6, 4))) 
            Console.WriteLine("An equal cube is already in the collection.");
        else 
            Console.WriteLine("Cube can be added.");
        //Outputs "An equal cube is already in the collection."
    }
}

public class Cube : IEquatable<Cube>
{
    public int Height { get; set; }
    public int Length { get; set; }
    public int Width { get; set; }

    public Cube(int h, int l, int w)
    {
        this.Height = h;
        this.Length = l;
        this.Width = w;
    }

    public bool Equals(Cube other)
    {
        if (this.Height == other.Height && this.Length == other.Length && this.Width == other.Width) 
            return true;
        else 
            return false;
    }
}

The most important properties of List are:

Capacity – We can use the Capacity property on List, or pass an integer to the constructor (which sets an initial capacity) to improve allocation performance.
Count – To get the number of elements, access the Count property. This is fast – just avoid the Count extension method. Count, on the List type, is equal to Length on arrays.