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:

1
2
3
4
5
6
7
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)
        }
    }
}
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
        }
    }
}
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) —

GD Star Rating
loading...
235 words
Last Post: How to Clone Variables (The Clone Function) in Javascript?
Next Post: The Javascript's Memorization Function to Speed Up Recursion (Dynamic Programming)

The Permanent URL is: C# How to Remove Empty Elements from List in O(n)?

Leave a Reply