List of Lists

This is a discussion on List of Lists within the C Programming forums, part of the General Programming Boards category; Can anyone give me an sample code of a linked list of linked lists? or atleast how to make it, ...

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    15

    List of Lists

    Can anyone give me an sample code of a linked list of linked lists?

    or atleast how to make it, I will try my best to convert your words into lines of codes.

    I am trying to make something like a 2d array but in list form.

    //I need to utilize doubly linked lists//

    example:

    Node 1 (head)
    ----subNode 1 (subhead)
    ----subNode 2
    ----subNode 3 (subtail)
    Node 2
    ----subNode 1
    ----subNode 2
    Node 3
    ----subNode 1
    ----subNode 2
    ----subNode 3
    ----subNode 4
    Node 4 (tail)
    ----subNode 1

    example: list of topics and lists of notes for each topic

    thank you in advance . Im currently on my 2nd year of my BS computer science course.

  2. #2
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Do you know how to create a list? If you do, then you should be able to do it. A typical example node consists of a data element and a link element. In this case you need the data to be another list, so it's going to look pretty much like your link element. If you want to reuse the same node in all lists you can use void* to be able to take both nodes and data, for example:

    Code:
    struct node {
        void *data;
        struct node *next;
    };
    Last edited by Subsonics; 10-07-2012 at 11:53 AM.

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    890
    If both your nodes and subnodes can contain data, and you need a doubly linked list, you could use
    Code:
    struct node {
    
        /* Vertical links */
        struct node  *parent;
        struct node  *child;
    
        /* Horizontal links */
        struct node  *prev;
        struct node  *next;
    
        /* Node contents can be anything you need: */
        size_t        size;
        char          data[];
    }
    However, this is not like a 2D table, it is more like a filesystem: parent points to the parent directory, child to the first child directory, prev to the previous item in the same directory as this one, next to the next item in the same directory as this one, and node contents contain at least the file/directory name for this node.

    Implementation is straightforwad: parent,child pointers form a doubly linked list, and prev,next another. They should never cross anywhere else but the current node. (You can form the nodes into a 2D grid, but pointer manipulation becomes exceedingly complex, when removing or adding new nodes. There are much better, more efficient data structures for sparse and dense N-dimensional arrays.)

    There is a very important detail you need to decide for each doubly linked list: how to terminate the list ends. You can use NULL pointers, point the entries to themselves, or form the lists into a ring. NULL pointers may be the easiest choice. Pointing the entries to themselves is useful if you have to use complex traversal schemes (stuff like horse on a chess board: parent->parent->prev or so), as you then don't need to check for NULL pointers; but checking for list start and end is a bit confusing. Forming the list into a ring is very useful if you need to continuously add and remove items from the list (especially if concurrently from multiple threads), as then you can access both the start and the end of the list with a single dereference.

    If you are unfamiliar with doubly linked lists, maybe the Wikipedia article on Doubly linked lists will help?

  4. #4
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    What is the purpose of the parent, child members? If there is no special head struct, surely something like struct node *list; will be enough.

  5. #5
    Registered User
    Join Date
    Oct 2011
    Posts
    890
    Quote Originally Posted by Subsonics View Post
    What is the purpose of the parent, child members? If there is no special head struct, surely something like struct node *list; will be enough.
    That will give you only one list, and a singly-linked list at that.

    Consider the situation when we wish to describe the following structure:
    Code:
    Alice ─ Cecilia ─ David ─ Felicity
     │                 │
    Bob               Erwin
    The root, is obviously Alice: the pointer that we use to manage the entire structure is Alice. If we choose to use NULL to terminate each list, then
    Code:
    Alice:    .parent = NULL,    .child = Cecilia,  .prev = NULL,  .next = Bob
    Bob:      .parent = NULL,    .child = Cecilia,  .prev = Alice, .next = NULL
    
    Cecilia:  .parent = Alice,   .child = David,    .prev = NULL,  .next = NULL
    
    David:    .parent = Cecilia, .child = Felicity, .prev = NULL,  .next = Erwin
    Erwin:    .parent = Cecilia, .child = Felicity, .prev = David, .next = NULL
    
    Felicity: .parent = David,   .child = NULL,     .prev = NULL,  .next = NULL
    If you added Esther under Erwin, then
    Code:
    Erwin:    .parent = Cecilia, .child = Felicity, .prev = David, .next = Erwin
    Esther:   .parent = Cecilia, .child = Felicity, .prev = Erwin, .next = NULL
    As you can see, inserting something between Cecilia and David would mean you need to also reparent Erwin (and Esther, if added under Erwin). On the other hand, you can easily "move" in either direction, when given just one node.

    Often, the .child pointer is left NULL for all but the first child. In that case, to go "down", you use ->parent->child->child if ->child==NULL.
    ___________________________

    I suspect you (Subsonics) refer to another method, where one uses two different structures to describe nodes (without data) and leaves (with data). Doubly-linking, as per the OP's request, that would be for example:
    Code:
    struct leaf {
        struct list *prev;
        struct list *next;
        /* Data fields */
    };
    
    struct node {
        struct node *prev;
        struct node *next;
        struct leaf *list;
    };
    In this case, we'd have one list of nodes, and the data lists hanging off those:
    Code:
    node0: .prev = NULL,  .next = node1, .list = Alice
    node1: .prev = node0, .next = node2, .list = Cecilia
    node2: .prev = node1, .next = node3, .list = David
    node3: .prev = node2, .next = NULL,  .list = Felicity
    
    Alice:    .prev = NULL,  .next = Bob
    Bob:      .prev = Alice, .next = NULL
    
    Cecilia:  .prev = NULL,  .next = NULL
    
    David:    .prev = NULL,  .next = Erwin
    Erwin:    .prev = David, .next = NULL
    
    Felicity: .prev = NULL,  .next = NULL
    The pointer needed to refer to the entire structure would point to node0.
    This is closer to the concept of list of lists rather than 2D arrays. The thing to note is that if given a data node, there is no way to navigate vertically; one must have both the vertical node, and the horizontal leaf, to be able to navigate as one would in an array.

    You can also form either or both lists into rings, where first .prev points to the last item, and last .next points to the first item. Or instead of NULL, have them point to the leaf itself.

    Data structures formed from more than one dimension of linked lists are a bit hard to fathom in the abstract sense. If the Original Poster (Isnalla) could state an example use case -- say, directories and files, or something real-worldly --, I could perhaps show better examples. There are a lot of variations and combinations of the above two structures that are applicable in different situations; there simply is no one structure that would fit all cases best.

    So, Isnalla, give us a real-world use case, and we'll discuss further.

  6. #6
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by Nominal Animal View Post
    That will give you only one list, and a singly-linked list at that.
    No. Where ever you create the list you are going to have 1 reference to it, therefor 1 reference is enough in the nodes as well. It's not going to be a singly linked list because (your) nodes contains a next/prev pointer.

  7. #7
    Registered User
    Join Date
    Oct 2011
    Posts
    890
    Quote Originally Posted by Subsonics View Post
    No. Where ever you create the list you are going to have 1 reference to it, therefor 1 reference is enough in the nodes as well. It's not going to be a singly linked list because (your) nodes contains a next/prev pointer.
    I'm sorry, I don't follow you. What do you mean? Could you please show an actual example?

  8. #8
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by Nominal Animal View Post
    I'm sorry, I don't follow you. What do you mean? Could you please show an actual example?
    The question related to your node and the members parent, child specifically. When you create your list (depending on if you have a special head node or not) could look like this:

    Code:
    struct node list;
    list_add(&list, data);
    After that you will have 1 reference to the list, regardless if it's a singly linked list or not. Therefor if each node should have the potential for another list, 1 reference is enough. A reference to the head node.

    I don't know what kind of examples you want to see, I find it hard to come up with something that is not an entire list. But the bottom line is that the lists inside the list aren't special in any way, you would need 1 reference, to the head node.
    Last edited by Subsonics; 10-07-2012 at 09:40 PM.

  9. #9
    Registered User
    Join Date
    Oct 2011
    Posts
    890
    Quote Originally Posted by Subsonics View Post
    The question related to your node and the members parent, child specifically.
    In this structure,
    Code:
    struct node {
     
        /* Vertical links */
        struct node  *parent;
        struct node  *child;
     
        /* Horizontal links */
        struct node  *prev;
        struct node  *next;
     
        /* Node contents can be anything you need: */
        size_t        size;
        char          data[];
    };
    each node contains data, and there is just that one structure type. I don't normally use handles. Now, consider this structure:
    Code:
    A0─A1─A2─A3
       │  │
       │  D0─D1─D2
       │
    B0─B1─B2
          │
    C0─C1─C2─C3─C4
    You can reach every node from any node, starting with just the node pointer, without extra structure traversals. As long as you do not form any loops, this works fine, and is simple to implement.

    I think I did mention that this is more like a directory tree than a 2D array or a list of lists. (In a directory tree, each horizontal sibling would have the same pointer to their parent, because that makes traversals much simpler. So, B0..B2 would connect to A1, D0..D2 to A2, and C0..C4 to B2.)

    If you don't need the ability to describe this complexity, there are simpler/better structures one can use. But the above structure does need all four pointers in each node (or more than one type of node), if you want to easily traverse between nodes in any direction.

  10. #10
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by Nominal Animal View Post
    In this structure,
    Code:
    struct node {
     
        /* Vertical links */
        struct node  *parent;
        struct node  *child;
     
        /* Horizontal links */
        struct node  *prev;
        struct node  *next;
     
        /* Node contents can be anything you need: */
        size_t        size;
        char          data[];
    };
    each node contains data, and there is just that one structure type. I don't normally use handles. Now, consider this structure:
    Code:
    A0─A1─A2─A3
       │  │
       │  D0─D1─D2
       │
    B0─B1─B2
          │
    C0─C1─C2─C3─C4
    You can reach every node from any node, starting with just the node pointer, without extra structure traversals. As long as you do not form any loops, this works fine, and is simple to implement.

    I think I did mention that this is more like a directory tree than a 2D array or a list of lists. (In a directory tree, each horizontal sibling would have the same pointer to their parent, because that makes traversals much simpler. So, B0..B2 would connect to A1, D0..D2 to A2, and C0..C4 to B2.)

    If you don't need the ability to describe this complexity, there are simpler/better structures one can use. But the above structure does need all four pointers in each node (or more than one type of node), if you want to easily traverse between nodes in any direction.
    You have to ask what the purpose is of not linking to the head node in those sublists however, for the purpose given by the OP. I also have a hard time, (of the top of my head) to figure out any example where that would provide an advantage as opposed to linking to the head specifically. But, given that each node contains a *next and *prev pointer that are NULL terminated, you could still do it with 1 reference. BTW that example structure you provided looks like a tree, you should be able to create it with a node containing, data, *left and *right references only.

    I'll provide a more fleshed out example this time, with a specific head node since there are benefits of having a reference to the tail for example.

    Code:
    struct list;
    
    struct node {
        int data;
        struct list *sublist;
        struct node *next;
        struct node *prev;
    };
    
    struct list {
        struct node *head;
        struct node *tail;
        size_t size;
    };
    
    struct list list;
    memset(&list, 0, sizeof(struct list));
    
    list_add(&list, 123);
    list_add(&list, 456);
    
    /* Now add a sublist */
    list.sublist = calloc(1, sizeof(struct list));
    
    list_add(list.sublist, 789);
    
    /*
     * 123 -> 456
     *  |
     * 789
     *
     */
    Obviously in real world, you would need a search function that retrieves a node where you can insert a new list (or add data to an existing list).
    Last edited by Subsonics; 10-08-2012 at 12:56 AM. Reason: node -> reference

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    The OP said:
    like a 2d array but in list form
    That could mean
    1. A grid where each node has an above, below, left, and right node, where you can move through the grid in any direction by one node by following one pointer. A doubly-intrusive list such as Nominal shows does this. One might use such a thing in a sudoku solver, for example.
    OR
    2. That the OP wants a plain old list-of-lists with only the ability to go through say along a "horizontal" list, and then down through a "vertical" list, in that order. I would be more inclined to think this was more the intention, but it has probably unintentionally been phrased more like the other way.

    Anyway, to the OP, as you are in your second year, the above examples should help you get started. Ask more questions if you want more answers, and clarify which of the above two you are actually after.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Oct 2011
    Posts
    890
    Quote Originally Posted by Subsonics View Post
    You have to ask what the purpose is of not linking to the head node in those sublists however, for the purpose given by the OP.
    I think you're right. To be honest, I'm just trying to throw stuff at the OP to see what sticks.

    Quote Originally Posted by iMalc View Post
    That could mean [snip]
    I fully agree; well put.

    To OP, I'd recommend starting with a program that reads and stores a directory tree in a linked list structure. Either approach will work for this -- and the differences in approaches may become easier to see if you try it out in code yourself. While a tree is not exactly a linked list of linked lists, it is very common in real applications, and may be close enough.

    If you want a real linked list of linked lists problem, perhaps you could use a real-world scenario: students (on only one row) passing around papers, with stacks of papers (of different kinds) scattered here and there. You only need a simple logic: if the student starts with a stack, they take one, and pass one half of the rest in one direction, and the rest in the other direction. When a student receives a stack, they take one, and pass the rest forward. Students form one linked list, and the papers that each student has forms another. (Each time step, when students may hand out stacks to the student next to them, you'll need to go through the students list, and decide what each student does based on what papers they have.) For the paper datatype, I suspect it might be best to have both a paper identifier, and a number of copies (of that paper in that stack). Visualization should be simple, and it is close enough to a real world situation to make at least some sense.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A List of Linked Lists
    By kristjon_ciko in forum C Programming
    Replies: 2
    Last Post: 08-15-2012, 09:38 AM
  2. a List of Lists on C++
    By Rafa T. in forum C++ Programming
    Replies: 14
    Last Post: 01-04-2011, 01:47 PM
  3. Need advice about list of lists
    By handytxg in forum C++ Programming
    Replies: 2
    Last Post: 04-18-2009, 06:03 PM
  4. List of lists
    By Kirmie in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2005, 11:30 AM
  5. List-View / Image Lists
    By The Dog in forum Windows Programming
    Replies: 5
    Last Post: 07-25-2002, 08:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21