Appending in Different Sized Lists in .Net

Lists are crucial data structures in programming, offering a flexible way to store and manipulate collections of items. Efficiently appending elements to lists is a common operation, but its performance can vary depending on the size of the list. In this article, we’ll focus on measuring the performance of appending the last item to lists of different sizes in the .NET environment, specifically using the List<T> class in C#.

Background

Before diving into performance measurements, let’s briefly review how lists work internally in .NET. The List<T> class uses an array to store its elements. When elements are added to the list and the underlying array's capacity is exceeded, a new array with increased capacity is allocated, and existing elements are copied over. Understanding this resizing process is essential for analyzing the performance of append operations.

Measuring Append Operations to Lists of Different Sizes

To measure the performance of appending the last item to lists of different sizes, we will focus solely on the time taken to perform this operation.

using System.Diagnostics;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        // Create and populate list of 100 elements
        var myList = new List<int>();
        for (int i = 0; i < 100; i++)
        {
            myList.Add(i);
        }

        // Measure append to list of 100 elements
        var watch = Stopwatch.StartNew();
        myList.Add(100); // Append the last item
        watch.Stop();
        var appendToSmallListDuration = watch.ElapsedMilliseconds;
        Console.WriteLine("Append to list of 100 elements Duration: " + appendToSmallListDuration + " milliseconds");

        // Create and populate list of 100000 elements
        myList = new List<int>();
        for (int i = 0; i < 100000; i++)
        {
            myList.Add(i);
        }

        // Measure append to list of 100000 elements
        watch = Stopwatch.StartNew();
        myList.Add(100000); // Append the last item
        watch.Stop();
        var appendToLargeListDuration = watch.ElapsedMilliseconds;
        Console.WriteLine("Append to list of 100000 elements Duration: " + appendToLargeListDuration + " milliseconds");
    }
}

In the code above, we measure the time taken to append the last item to lists of sizes 100 and 100,000 respectively. By appending after adding elements, we focus specifically on the performance of the append operation as the size of the list increases.

Conclusion

Measuring the time taken to append the last item to lists of different sizes provides valuable insights into the performance characteristics of list operations in the .NET environment. In this particular case, the measured append times for lists of 100 elements and 100,000 elements were both negligible, indicating that the append operation is highly efficient regardless of the list size. This demonstrates the effectiveness of the underlying optimizations implemented in the List<T> class for append operations, making it a reliable choice for dynamic collection management in C#.

Edit:

So, after conducting further investigation;

Our argument is partially true. In the scenarios described in our test, it seems that the list had enough spare capacity to accommodate the appended elements without needing to resize the underlying array.

However, it’s important to note that this behavior is specific to the current implementation of List<T> in .NET and may vary depending on factors such as the initial capacity of the list and the growth factor used when resizing. In some cases, when the list's capacity is exceeded, the underlying array will need to be resized, and the elements will be copied to the new array, resulting in a performance overhead.

So, while our observation is accurate for the specific test scenario where spare capacity exists, it’s essential to consider that in other cases, especially when the list’s capacity needs to be increased, the resizing process may incur additional time complexity.

Stackademic 🎓

Thank you for reading until the end. Before you go:

• Please consider clapping and following the writer! 👏
• Follow us X | LinkedIn | YouTube | Discord
• Visit our other platforms: In Plain English | CoFeed | Venture | Cubed
• More content at Stackademic.com