C# How to Remove Empty Elements from List in O(n)?

In C#, we may use the following method to Remove Null Elements from a List:

static void RemoveNull<T>(List<T> list) {
    for (int i = list.Count - 1; i >= 0; i--) {
        if (list[i] == null) {
            list.RemoveAt(i); // O(n)
        }
    }
}

The overall complexity is O(N^2) as the RemoveAt in List is O(N). We can totally do this in O(N) by moving the non-empty elements forward and then delete the extra spaces.

static void RemoveNull<T>(List<T> list) {
    // Find Fist Null Element in O(n)
    var count = list.Count;
    for (var i = 0; i < count; i++) {
        if (list[i] == null) {
            // Current Position
            int newCount = i++;
            // Copy non-empty elements to current position in O(n)
            for (; i < count; i++) {
                if (list[i] != null) {
                    list[newCount ++] = list[i];
                }
            }
            // Remove Extra Positions O(n)
            list.RemoveRange(newCount, count - newCount);
            break;
        }
    }
}

The inner loop will break once the first Null element is found – despite there are two nested for loops, the overall complexity is O(N).

–EOF (The Ultimate Computing & Technology Blog) —