Creating a Nested List from a Flat List in C#

Question

I currently have the following classes:

public class NavigationItem
{
    public int ID { get; set; }
    public string Title { get; set; }
    public int ParentID { get; set; }
    public List<NavigationItem> Children { get; set; }
}

public class FlatItem
{
    public int ID { get; set; }
    public string Title { get; set; }
    public int ParentID { get; set; }
}

I have a sample data as follows:

+====+============+==========+
| ID |   Title    | ParentID |
+====+============+==========+
|  1 | Google     |          |
+----+------------+----------+
|  2 | Microsoft  |          |
+----+------------+----------+
|  3 | Oracle     |          |
+----+------------+----------+
|  4 | Gmail      |        1 |
+----+------------+----------+
|  5 | Sheets     |        1 |
+----+------------+----------+
|  6 | Adsense    |        1 |
+----+------------+----------+
|  7 | Azure      |        2 |
+----+------------+----------+
|  8 | SharePoint |        2 |
+----+------------+----------+
|  9 | Office     |        2 |
+----+------------+----------+
| 10 | Java       |        3 |
+----+------------+----------+
| 11 | Word       |        9 |
+----+------------+----------+
| 12 | Excel      |        9 |
+----+------------+----------+
| 13 | PowerPoint |        9 |
+----+------------+----------+

I already have the code to pull all the information from the sample data above and turn it into a List<FlatItem> object.

What's the best approach so that I can have a List<NavigationItem> object which will look like something below:

Google
- Gmail
- Sheets
- AdSense
Microsoft
- Azure
- SharePoint
- Office
  - Word
  - Excel
  - PowerPoint
Oracle
- Java

I'm thinking of creating a recursive method to loop through my List<FlatItem> then structure it in a way to be a nested list of NavigationItem.

Is `ParentID` `int` or `int?`? Your table suggests it is `int?` but your code says `int`. — Enigmativity, Jun 05 '18 at 11:25

ViRuSTriNiTy · Accepted Answer · 2018-06-05T12:37:44.847

3

No need for recursion. You could use LINQ to build the structure easily:

List<FlatItem> flatItems = ...;

var navigationItems = flatItems.Select(
    i => new NavigationItem { ID = i.ID, Title = i.Title, ParentID = i.ParentID }
).ToList();

foreach (var i in navigationItems)
    i.Children = navigationItems.Where(n => n.ParentID == i.ID).ToList();

// get Google, Microsoft, Oracle items
var rootNavigationItems = navigationItems.Where(n => n.ParentID == 0);

edited Jun 05 '18 at 12:37

answered Jun 05 '18 at 10:50

ViRuSTriNiTy

5,017
2
32
58

This does not give the correct output. Did you test it? – Enigmativity Jun 05 '18 at 11:23
@Enigmativity Yes it works, unfortunately i forgot the last line, fixed it. – ViRuSTriNiTy Jun 05 '18 at 12:34

Enigmativity · Answer 2 · 2018-06-05T11:21:53.320

Try this:

List<FlatItem> source = new List<UserQuery.FlatItem>()
{
    new FlatItem() { ID = 1, Title = "Google", ParentID = null },
    new FlatItem() { ID = 2, Title = "Microsoft", ParentID = null },
    new FlatItem() { ID = 3, Title = "Oracle", ParentID = null },
    new FlatItem() { ID = 4, Title = "Gmail", ParentID = 1 },
    new FlatItem() { ID = 5, Title = "Sheets", ParentID = 1 },
    new FlatItem() { ID = 6, Title = "Adsense", ParentID = 1 },
    new FlatItem() { ID = 7, Title = "Azure", ParentID = 2 },
    new FlatItem() { ID = 8, Title = "SharePoint", ParentID = 2 },
    new FlatItem() { ID = 9, Title = "Office", ParentID = 2 },
    new FlatItem() { ID = 10, Title = "Java", ParentID = 3 },
    new FlatItem() { ID = 11, Title = "Word", ParentID = 9 },
    new FlatItem() { ID = 12, Title = "Excel", ParentID = 9 },
    new FlatItem() { ID = 13, Title = "PowerPoint", ParentID = 9 },
};

var lookup = source.ToLookup(x => x.ParentID);

Func<int?, List<NavigationItem>> build = null;
build = pid =>
    lookup[pid]
        .Select(x => new NavigationItem()
        {
            ID = x.ID,
            Title = x.Title,
            ParentID = x.ParentID,
            Children = build(x.ID)
        })
        .ToList();

To start the process call build(null). That gives me this:

This does assume that the ParentId property is a int? - which your data table does suggest.

score 2 · Answer 3 · answered Jun 05 '18 at 11:17

If you are ok with using recursion, you can create a function like this:

public List<NavigationItem> ChildrenOf(List<FlatItem> flatItems, int parentId)
{
    var childrenFlatItems = flatItems.Where(i => i.ParentID == parentId);
    return childrenFlatItems.Select(i => new NavigationItem {
        ID = i.ID,
        Title = i.Title,
        ParentID = i.ParentID, 
        Children = ChildrenOf(flatItems, i.ID)})
    .ToList();
}

Then, assuming that your root items have a parent id of 0 (since you aren't using nullable types), you generate the full list with:

ChildrenOf(flatsItems, 0)

score 1 · Answer 4 · answered Jun 05 '18 at 10:42

Untested, however you could try this, should be fairly fast as well

var list = new List<FlatItem>();
var result = new List<NavigationItem>();

// just a helper to remember ids
var dict = new Dictionary<int, NavigationItem>();

foreach (var item in list)
{
   var nav = new NavigationItem()
                  {
                     ID = item.ID,
                     ParentID = item.ParentID,
                     Title = item.Title,
                     Children = new List<NavigationItem>()                                   
                  };

   if (!dict.ContainsKey(nav.ParentID))
      result.Add(nav);       
   else
      dict[nav.ParentID].Children.Add(nav);

   dict.Add(item.ID, nav);
}

score 0 · Answer 5 · answered May 13 '20 at 07:53

no recursive, just GroupBy.

List<NavigationItem> list = ... // map from List<FlatItem> 
// and init Children = new List<NavigationItem>();

var groups = list.GroupBy(x => x.ParentID).ToList();
foreach (var g in groups)
{
    var items = list.Find(x => x.ID == g.Key);
    if (items != null) 
        items.Children = g.ToList();
}

// tops is [Google, Microsoft, Oracle]
var tops = list.Where(x => x.ParentID == null).ToList();

Creating a Nested List from a Flat List in C#

5 Answers5

Linked