CODEWITHSUNDEEP
javaalgorithmlistdata-structures
akhy
akhy

Reputation: 5900

Generate Nested List (Tree) from Flat List

I have a plain class named MenuModel in Java (it's for nested menu as the name suggests) like this:

public class MenuModel {
    public String id;
    public String parentId = null;
    public String title;

    public MenuModel parent = null;
    public List<MenuModel> children = new ArrayList<MenuModel>(); 
 }

My code fetch data from web API and generate a flat list of MenuModel with only id, parentId, and title fields filled with data. However, I need each MenuModel to have references to its parent and (optionally) children for further uses.

I have thought of a method which make a nested loop to pair the models each other and check if they are parent and child. But I think that costs too much (n^2 or n^3 complexity, the itemset is large) and can only fill the parent field.

What is the best way to achieve this in Java? To summarize:

Thanks in advance

Upvotes: 0

Views: 2227

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

Go through all the records and add them to a HashMap<String, MenuModel> (the key being the ID).

Then, for each record record:

  • Look up the parent ID in the above map to get parent.
  • Assign the parent to this record's parent variable - record.parent = parent.
  • Add this record to the parent's list of children - parent.children.add(record).

Running time: Expected O(n).

Upvotes: 7

Related Questions