List of Lists

Printable View

10-07-2012
Isnalla

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.
10-07-2012
Subsonics

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; };
10-07-2012
Nominal Animal

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?
10-07-2012
Subsonics

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.
10-07-2012
Nominal Animal

Quote:

Originally Posted by Subsonics

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.
10-07-2012
Subsonics

Quote:

Originally Posted by Nominal Animal

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.
10-07-2012
Nominal Animal

Quote:

Originally Posted by Subsonics

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?
10-07-2012
Subsonics

Quote:

Originally Posted by Nominal Animal

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.
10-07-2012
Nominal Animal

Quote:

Originally Posted by Subsonics

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-07-2012
Subsonics

Quote:

Originally Posted by Nominal Animal

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).
10-08-2012
iMalc

The OP said:

Quote:

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.
10-08-2012
Nominal Animal

Quote:

Originally Posted by Subsonics

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

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.