6

I have having trouble figure out how to write this code.

I have a list of items, the items all have an ID. There is also another value that we will call otherID. If otherID is zero or null, we will ignore it. However, if otherID contains the ID of another item in the list, I want to remove that item from the list.

Example:

item1.ID = 5, item1.otherID = null
item2.ID = 6, item2.otherID = 5
item3.ID = 7, item3.otherID = null

so item1 should be removed from the list because it's ID is present in the otherID field of item2

Any one know how I would write this?

MetaGuru
  • 42,847
  • 67
  • 188
  • 294

2 Answers2

11

One way to do this would be a 2-stage process:

  1. Build up a set of Ids that must be removed.
  2. Remove items from the list whose Id's are present in the blacklist.

This will require two passes of the list. Since adding to a HashSet / testing if it contains an item should be a constant-time operation, the entire operation should run in linear time. 

var idsToBeRemoved = new HashSet<int?>(list1.Select(item => item.otherID)
                                            .Where(otherId => otherId.HasValue));

list1.RemoveAll(item => idsToBeRemoved.Contains(item.ID));

EDIT: Updated Id's type to int? after clarification from the OP.

Ani
  • 111,048
  • 26
  • 262
  • 307
  • I'm sure he is using psuedo code. ID is probably type object, guid, or int? – keithwill Oct 27 '10 at 21:04
  • Yes, Id's type was not mentioned in the question. Will edit `int?` into my answer. – Ani Oct 27 '10 at 21:07
  • Why not `new HashSet(list1.Where(item => item.otherID.HasValue).Select(item => item.otherID.Value))`? – Greg Oct 27 '10 at 21:25
  • @Greg: That is also possible, but remember that `Id` is probably *also* of type `int?`. So you would then need change the second lambda to `item => item.ID.HasValue && idsToBeRemoved.Contains(item.ID.Value)`. On balance, I thought my original approach was less verbose. – Ani Oct 27 '10 at 21:30
8

Like this:

list.RemoveAll(r => list.Any(o => o != r && r.ID == o.otherID));
MetaGuru
  • 42,847
  • 67
  • 188
  • 294
SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964
  • you should edid last assightment to == – Ash Oct 27 '10 at 21:00
  • 1
    Ani's solution is O(n), while yours is O(n^2) – Gabe Oct 27 '10 at 21:01
  • Shogun: for every item in the list, this solution will potentially have to look at every item in the list; Ani's solution will only have to look at each item twice: once to build the set of idsToBeRemoved and once to remove them. – Gabe Oct 27 '10 at 21:33
  • @Gabe Good point here Gabe. If I could +1 you here for commenting on "scalable code" I would. Great add! – Zack Jannsen Aug 15 '12 at 11:43