CODEWITHSUNDEEP
c#.net.net-2.0
Leo Vo
Leo Vo

Reputation: 10330

Find functions for Union, Substract, Intersect on a List

Assume I have tow lists: List<int> l1,andList<int>l2

Please help me how to to union, substract and intersect between 2 list. Thanks.

Note: I am using .NET 2.0, so I can't use LINQ. Thanks.

Upvotes: 2

Views: 2118

Answers (2)

Jon Skeet
Jon Skeet

Reputation: 1500255

You can use LINQ - just not the LINQ from .NET 3.5. You can use LINQBridge though, or if you really just want Union / Except / Intersect you could look at the source for Edulinq (my own implementation of LINQ to Objects). The latter uses HashSet<T> which is only in .NET 3.5, but you could use a Dictionary<,> to fake that.

The problem with using List<T>.Contains repeatedly is that each Contains operation is O(N). That's okay if you've got a small amount of data or if you just want this code to see the principle of the three operations, but for "real" work you'd want a more efficient contains check.

Upvotes: 3

Andrew Cooper
Andrew Cooper

Reputation: 32576

Here are the basic algorithms as pseudo-code:

UNION:
    Copy List1 to UnionList
    For each Item in List2
        If Item is not in UnionList 
            Add Item to UnionList
    Next
    Return UnionList

SUBTRACT:
    Copy List1 to DifferenceList
    For each Item in List2
        If Item is in DifferenceList
            Remove Item from DifferenceList
    Next
    Return DifferenceList

INTERSECT:
    Create new IntersectList
    For Each Item in List1
        If Item is in List2
            Add Item to IntersectList
    Next
    Return IntersectList

Upvotes: 4

Related Questions