none
How to implement linkedlist with several pointers, not just next/prev? RRS feed

  • Question

  • I noticed the linkedlist class and methods.

    What if the implementation has several pointers in a node? 

    In a regular linked list there is the "next" (i.e. right), sometimes with "prev" (i.e. left). But what if i want to allow connectivity up and downas well?

    Is there a way to use/modify the linkedlist? or another class?


    Tuesday, March 12, 2019 7:29 PM

Answers

  • The UI layout shouldn't dictate the structure of the data at this point. When you get to the UI you might use a graph-like UI library to render the data but it will still just be bouncing off the list of relationships you have now so it should be pretty easy and efficient to do. There isn't a need to adjust how you store the data on the backend to accommodate the UI layout (which can change in the future as well).

    Michael Taylor http://www.michaeltaylorp3.net

    • Marked as answer by YigalB Wednesday, March 13, 2019 2:58 PM
    Wednesday, March 13, 2019 2:52 PM
    Moderator

All replies

  • To clarify, the next/previous part of the node is the metadata the linked list needs to implement the standard list operations. This metadata is not generally something that you would deal with outside the linked list itself. A linked list implementation can have any additional metadata it needs but, again, you'd never care.

    When you talk about up/down I become confused because a linked list is basically a node pointing to another node after it or before it, hence a linked list. There is no concept of an up or down because it is a list. It sounds like you're really talking about either a tree (B-tree perhaps) or a graph. These are completely different data structures and therefore implement things differently. Again, each implementation can very but the metadata is an implementation detail. A graph may have a set of edges which allows a node to reference all other nodes it is attached to. A tree node might have a parent, left and right nodes (or perhaps a parent and list of children). It depends upon the tree implementation being used.

    There are already either direct implementations of all these data structures in .NET or someone has already written a library to provide them. Unless this is an academic exercise on how to build data structures then you'd never really care as a developer. You just pick the best collection type for what your needs are. Do you need to have fast inserts then a linked list is probably a good choice. Need fast searches on ordered data then a tree would be better. Do you need to represent a network of computers then a tree or graph may be better suited for the job. Once you've identified the type that you then you just use the corresponding implementation. Again, in a real app. For academic purposes a linked list is just next/prev. If you want to build a tree structure then take a look online on how to build a B-tree or similar structure as that is more closely representative of "up" and "down". 


    Michael Taylor http://www.michaeltaylorp3.net

    Tuesday, March 12, 2019 8:07 PM
    Moderator
  • To clarify, the next/previous part of the node is the metadata the linked list needs to implement the standard list operations. This metadata is not generally something that you would deal with outside the linked list itself. A linked list implementation can have any additional metadata it needs but, again, you'd never care.

    When you talk about up/down I become confused because a linked list is basically a node pointing to another node after it or before it, hence a linked list. There is no concept of an up or down because it is a list. It sounds like you're really talking about either a tree (B-tree perhaps) or a graph. These are completely different data structures and therefore implement things differently. Again, each implementation can very but the metadata is an implementation detail. A graph may have a set of edges which allows a node to reference all other nodes it is attached to. A tree node might have a parent, left and right nodes (or perhaps a parent and list of children). It depends upon the tree implementation being used.

    There are already either direct implementations of all these data structures in .NET or someone has already written a library to provide them. Unless this is an academic exercise on how to build data structures then you'd never really care as a developer. You just pick the best collection type for what your needs are. Do you need to have fast inserts then a linked list is probably a good choice. Need fast searches on ordered data then a tree would be better. Do you need to represent a network of computers then a tree or graph may be better suited for the job. Once you've identified the type that you then you just use the corresponding implementation. Again, in a real app. For academic purposes a linked list is just next/prev. If you want to build a tree structure then take a look online on how to build a B-tree or similar structure as that is more closely representative of "up" and "down". 


    Michael Taylor http://www.michaeltaylorp3.net

    I assume I used wrongly the term "linkedlist". As you mentioned, I am looking like to have an implementation of a family: each individual should have 2 links to his parents, one link to the children, and one to the spouse (actually two links, as an ex may exist as well). I think this is called a graph, right?  I am sure this was implemented before, yet I didn't find (yet) C# implementation - perhaps I don't know how/where to search. 
    Tuesday, March 12, 2019 8:25 PM
  • What you're describing is a "tree," although the term "graph" could also be used.

    However, you need to spend some time thinking about this.  Assuming you're really talking about a family tree here, the structure is nowhere near as clean as you have implied.  For example, there's no reason to assume that someone might only have one ex.  With children, you could have mom and dad point to the first child, then have the first child point to the next child, but what happens when a dad with kids marries a mom with kids?  Do you rewrite all of the kids' links to include the new family?  Shouldn't the ex have a pointer to the children, too?  And if someone has three exes, you don't really want ex #1 having a pointer to ex #2.

    I think you're going to end up with lists here.  A child can point back to its mom and dad, but the dad is going to need a "list of spouses" and a "list of children", and the mom is going to have a "list of spouses" and a "list of children".


    Tim Roberts | Driver MVP Emeritus | Providenza & Boekelheide, Inc.

    Tuesday, March 12, 2019 8:46 PM
  • I wouldn't implement it as a linked list or a graph (in the data structure sense) I'd just use properties.

    public class Person
    {
       public string FirstName { get; set; }
       public string LastName { get; set; }
    
       public Person Father { get; set; }
       public Person Mother { get; set; }
    
       public List<Person> Children { get; set; }
    }

    This is ignoring any business rules that you probably need around cyclic relationships. For example it wouldn't make sense for someone in Children to also be listed as a Father/Mother. It wouldn't make sense for the Father of one of the Children elements to not be the same object as the one who's Children list contains it. Etc. You could try to enforce these in the class itself and that would tend to lead you away from having Children as a List<T> but instead using methods to help enforce this. Alternatively perhaps you just have "relationship checker" type that evaluates all these rules instead. At this point we aren't using any linked list/graph structures as they aren't needed.

    When you get to spouses then things get trickier. You mentioned an ex-spouse but an ex-spouse isn't a spouse so I'd lean toward, in the above code, having a Spouse property of type Parent. The same relationship rules would need to be enforced. For ex-spouses you could have a List<Person> but now you're dividing up relationships into separate collections which means you're going to have to keep expanding this type as new relationships come into play (e.g. siblings, uncles, etc). At this point you need to consider how you might treat relationships. Taking a cue to how Azure DevOps stores relationships I might say you should have a single List<PersonRelationship> called RelatedPeople that contains the Person and their relationship (e.g. spouse, child, etc). Then it becomes easier to work with. When you add a new type then you just add the new relationship to the list of supported relationships. If somebody just wants to see all the relationships then they enumerate the collection. If they want to get a specific set of relationships (e.g. children) then they use LINQ to filter. You can expose public getter properties for some common relationships but they all point to the same collection. Your relationship checker can also more easily do the validation you need by having a single list I believe. Here's an example of what it might look like.

    //Using an enum here to avoid magic strings but you can use anything to define a "relationship"
    public enum Relationship
    {
       Mother,
       Father,
       Child,
       Spouse,
       Sibling
    }
    
    public class PersonRelationship
    {
       public Person Person { get; set; }
       public Relationship Relationship { get; set; }
    }
    
    public class Person
    {
       public List<Person> Relationships { get; set; } = new List<Person>();
    
       //Common relations get special properties
       public Person Father
       {
          get { return Relationships.FirstOrDefault(r => r.Relationship == Relationship.Father); }
       }
    
       public IEnumerable<Person> Uncles
       {
          get 
          {
             var father = Father;
             if (father == null)
                return Enumerable.Empty<Person>();
    
             return father.Relationships.Where(r => r.Relationship == Relationship.Sibling); //&& IsMale
          }
       }
    }
    
    

    A couple of notes about this code besides the fact that I haven't tested it and it isn't production ready.

    1.  When dealing with hierarchial data like this, if you allow anyone to muck with the list of relationships then they can set up invalid states (e.g. 2 fathers). If you lock down the relationships via method calls then you are still dealing with reference types so somebody could add someone as a father and then go back and change it to a mother. You're still going to need some sort of relationship checker that enforces all your rules before you ultimately "save" this stuff somewhere and expect it to be valid. Enforcing this stuff before that point could be difficult and probably not worth the effort unless you use value types or something. Again properly not worth the time so ensure you validate the relationships before persisting the data if you care.
    2. The supported "relationship" types only need to include one side of the equation in most cases. For example in my example code you don't need a relationship for uncle because you can figure that out by looking at the siblings of the mother and father. In this particular case I only demoed looking for siblings of father so you'd need to expand the check but this is a demo of how you can "get to" the other relations.
    3. Again, I used an enum here because it results in shorter code. You can use whatever relationship type you want provided you can do equality checking.
    4. You can add additional properties for the common relationships you want to expose and you can add extension methods for other relationships down the road. For example you may not care about grandparents today but later you can either a direct property or an extension method that returns that based upon the existing relationships.
    5. If you want to add a new relationship in the future (e.g. god-parent) then you just update the Relations object and any code that cares about the relationship (e.g. UI). Unless there are additional relationship rules to be enforced then you don't need to touch most of the other code.


    Michael Taylor http://www.michaeltaylorp3.net

    Tuesday, March 12, 2019 9:01 PM
    Moderator
  • Wow, such a perfect and detailed answer. Thank you!

    I agree with your logic. I think a lot depends on how far am I going to go with this application. At this stage I do it for fun, not beyond. About the input - I plan to use GEDCOM from external sources (e.g. Geni), so I assume they invested efforts to ensure correctness.

    Yet you are 100% correct: input must be checked, to make sure a son is not always a father of his father, or someone is 250 years old, or many others errors. I plan to add checkers later on. At this stage I assume (and hope) that the GEDCOM file is correct.

    The fact I use GEDCOM as input also supports your recommendation not to used linked list or graph. The reason I thought of linkedlist (or Graph) was to provide a delivery towards next stage - printing the tree. I don't have a clue yet how to print it (in a shape of a family tree), yet I was thinking that graph will be a comfortable method.

    I guess I am wrong. am I?

    Wednesday, March 13, 2019 2:47 PM
  • The UI layout shouldn't dictate the structure of the data at this point. When you get to the UI you might use a graph-like UI library to render the data but it will still just be bouncing off the list of relationships you have now so it should be pretty easy and efficient to do. There isn't a need to adjust how you store the data on the backend to accommodate the UI layout (which can change in the future as well).

    Michael Taylor http://www.michaeltaylorp3.net

    • Marked as answer by YigalB Wednesday, March 13, 2019 2:58 PM
    Wednesday, March 13, 2019 2:52 PM
    Moderator
  • Agreed with respect!

    I learned a lot from you and also saved time from going the wrong way. Thank you.

    If you have recommendation how to continue to next level of printing - I will appreciate it. So far I got no answers for that.

    But as for this thread - I am all good.

    Thank you!

    Wednesday, March 13, 2019 2:57 PM