By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,213 Members | 2,108 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,213 IT Pros & Developers. It's quick & easy.

Nested linklist

P: n/a
I don't really know how to say it so I just say it a nested linklist.

How do you make LinkLists inside LinkList?
Can anyone help me for this?
I think an example program will help me a lot.

thank you.

Nov 14 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a


jwvai316 wrote:
I don't really know how to say it so I just say it a nested linklist.

How do you make LinkLists inside LinkList?
Can anyone help me for this?
I think an example program will help me a lot.


Let's build this from the ground up. Suppose you have
a struct containing some kind of "payload" -- a pair of
`double' values, let's say -- and you wish to put a bunch
of such structs into a linked list. One common way to do
this is to augment the struct with a `next' pointer:

struct node { /* a node in a list: */
double x, y; /* payload data */
struct node *next; /* next node in list */
};

So far, so good. You may also want to define another
kind of struct that keeps track of useful information about
a linked list -- pointers to the first and last nodes, maybe
some other data:

struct list { /* info about an entire list: */
struct node *head; /* pointer to first node */
struct node *tail; /* pointer to final node */
unsigned int length; /* number of nodes in list */
};

So far, we've started from a struct with some payload
data and built up the machinery to hold such structs in a
list: we added a link to each struct, and we defined a new
struct type to manage the list as a whole. (The examples
above are illustrations; linked lists need not necessarily
be implemented in exactly this way. Adjust your definitions
to match your needs.)

All right, now you want to form a sort of super-list whose
individual nodes are linked lists as above. How? By repeating
the exact same operations that took you from an x-and-y pair to
a linked list, only this time treating the `struct list' as
the payload for the super-list. The first step is to add a
`next' pointer along with the payload:

struct list { /* info about an entire list: */
struct node *head; /* pointer to first node */
struct node *tail; /* pointer to final node */
unsigned int length; /* number of nodes in list */
struct list *next; /* next list in super-list */
};

This is a node that can be part of a linked list (thanks to its
own `next' pointer) and whose payload happens to describe a
linked list containing another style of node. If you like, you
can define another struct type to keep track of this super-list:

struct super_list { /* info about an entire super-list: */
struct list *head; /* first list in super-list */
struct list *tail; /* final list in super-list */
};

You could continue in this manner, building more and more
levels: equip a `struct super_list' with its own `next' pointer,
define a new `struct super_duper_list' to keep track of a list
of `struct super_list's, and so on. However, things will soon
become rather unwieldy if you pursue this too far: I'd suggest
that if you find yourself using more than two levels as shown
here you might want to consider different data structures like
trees.

Once again, the examples above are just illustrations. The
name "linked list" applies to more than just the singly-linked
structures I've shown; you might use double linkage (a `prev'
along with each `next' link), circular linkage (the tail node
points back to the head instead of to NULL), a list that
operates as a stack, or as a queue, or as a general deque,
sorted lists, priority lists, ... The main point is that if
you have a "list-describing structure" of some kind, then you
can make that structure be the payload for a super-list in just
the same way that the list's own nodes became part of the list.

--
Er*********@sun.com

Nov 14 '05 #2

P: n/a
jwvai316 wrote:

I don't really know how to say it so I just say it a nested linklist.

How do you make LinkLists inside LinkList?
Can anyone help me for this?
I think an example program will help me a lot.


Lets deal with a general purpose node:

struct node {
struct node *next;
struct node *sublist;
whatever *data;
}

so we can use *data to attach any sort of data to any node. Now we
can tie them together something like this:

(NULL) (NULL) (NULL)
^ ^ ^
| | |
NODE -----> NODE -----> NODE -->(NULL)
^
| (NULL) (NULL) (NULL)
| ^ ^ ^
| | | |
NODE -----> NODE -----> NODE -----> NODE -->(NULL)
^
| (NULL)
| ^
| |
NODE -----> NODE
^
| (NULL) (NULL) (NULL)
| ^ ^ ^
| | | |
NODE -----> NODE -----> NODE -----> NODE -->(NULL)
^
| (NULL) (NULL) (NULL)
| ^ ^ ^
| | | |
NODE -----> NODE -----> NODE -----> NODE -->(NULL)
^
|
root

where we can cut things off towards the right and top. The upwards
pointing arrows represent the field 'next', and the right pointing
arrows represent the field 'sublist'. Many of those pointers are
NULL, and we may be able to find another use for those if we add
some sort of descriptor field to the node. Meanwhile we can
preserve access to the whole thing by a single pointer in root (of
type struct node *).

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html
Nov 14 '05 #3

P: n/a
jwvai316 wrote:

I don't really know how to say it so I just say it a nested linklist.

How do you make LinkLists inside LinkList?
Can anyone help me for this?
I think an example program will help me a lot.


/* BEGIN listolists.c output */

Man number 1
Name: Iofo
Age : 32
Phone numbers:
163-4945
434-9890
785-6541
432-9672

Man number 2
Name: Eblf
Age : 36
Phone numbers:
945-4349
890-7856
541-4329
672-3216

Man number 3
Name: Fjut
Age : 24
Phone numbers:
349-8907

Man number 4
Name: Vsfg
Age : 24
Phone numbers:
907-8565
414-3296
723-2165
238-3036
381-0527

Man number 5
Name: Wfgn
Age : 20
Phone numbers:
565-4143
296-7232
165-2383

/* END listolists.c output */

/* BEGIN listolists.c */

#include <stdio.h>
#include <stdlib.h>

#define PEOPLE_MAX 5
#define NUMBERS_MAX 3
#define NAME_LENGTH 5
#define UPPER "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LOWER "abcdefghijklmnopqrstuvwxyz"
#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) * 69069LU + 362437 & 0xffffffff)

struct list_node {
struct list_node *next;
void *data;
};

typedef struct list_node list_type;

struct person {
char name[NAME_LENGTH + 1];
int age;
list_type *phone_numbers;
};

list_type *list_make(long unsigned count);
list_type *man_init(list_type *node, long unsigned seed);
list_type *number_init(list_type *node, long unsigned seed);
void make_name(char *name, size_t length, long unsigned seed);
void man_print(list_type *node);
void number_print(list_type *node);
void list_free(list_type *node, void (*free_data)(void *));
void person_free(void *data);

int main(void)
{
list_type *head;
long unsigned seed = LU_RAND_SEED;

puts("/* BEGIN listolists.c output */");
head = list_make(1 + seed % PEOPLE_MAX);
if (head == NULL) {
fputs("No list\n", stderr);
}
seed = LU_RAND(seed);
head = man_init(head, seed);
man_print(head);
list_free(head, person_free);
puts("\n/* END listolists.c output */");
return 0;
}

list_type *list_make(long unsigned count)
{
list_type *node, *list;

list = count != 0 ? malloc(sizeof *list) : NULL;
if (list != NULL) {
node = list;
while (--count != 0) {
node -> data = NULL;
node -> next = malloc(sizeof *node -> next);
if (node -> next == NULL) {
list_free(list, free);
return NULL;
} else {
node = node -> next;
}
}
node -> data = NULL;
node -> next = NULL;
}
return list;
}

list_type *man_init(list_type *node, long unsigned seed)
{
list_type *head;
struct person man;

head = node;
while (node != NULL) {
node -> data = malloc(sizeof man);
if (node -> data == NULL) {
fputs("man_init malloc problem\n", stderr);
head = NULL;
break;
}
seed = LU_RAND(seed);
make_name(man.name, NAME_LENGTH, seed);
seed = LU_RAND(seed);
man.age = 20 + seed % 20;
seed = LU_RAND(seed);
man.phone_numbers = list_make(1 + seed % PEOPLE_MAX);
if (man.phone_numbers == NULL) {
fputs("man.phone_numbers == NULL\n", stderr);
head = NULL;
break;
}
seed = LU_RAND(seed);
if (number_init(man.phone_numbers, seed) == NULL) {
fputs("man_init(man.phone_numbers, seed) == NULL\n",
stderr);
head = NULL;
break;
}
*(struct person *)node -> data = man;
node = node -> next;
}
return head;
}

list_type *number_init(list_type *node, long unsigned seed)
{
list_type *head;
size_t count;
char *string;

head = node;
while (node != NULL) {
node -> data = malloc(sizeof "xxx-xxxx");
if (node -> data == NULL) {
fputs("number_init malloc problem\n", stderr);
head = NULL;
break;
}
string = node -> data;
count = sizeof "xxx-xxxx" - 1;
while (count-- != sizeof "-xxxx" - 1) {
seed = LU_RAND(seed);
*string++ = (char)('0' + seed % 10);
}
*string++ = '-';
while (count-- != 0) {
seed = LU_RAND(seed);
*string++ = (char)('0' + seed % 10);
}
*string = '\0';
node = node -> next;
}
return head;
}

void man_print(list_type *node)
{
long unsigned count;
struct person *man;

for (count = 1; node != NULL; ++count) {
man = node -> data;
printf(
"\n%5c Man number %lu\n"
"Name: %s\n"
"Age : %d\nPhone numbers:\n",
' ', count, man -> name, man -> age
);
number_print(man -> phone_numbers);
node = node -> next;
}
}

void number_print(list_type *node)
{
while (node != NULL) {
printf(" %s\n", (char *)node -> data);
node = node -> next;
}
}

void make_name(char *name, size_t length, long unsigned seed)
{
length = length / 2 + seed % (length / 2);
*name++ = UPPER[seed % sizeof UPPER];
while (length-- != 0) {
seed = LU_RAND(seed);
*name++ = LOWER[seed % sizeof LOWER];
}
*name = '\0';
}

void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;

while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}

void person_free(void *data)
{
list_free(((struct person *)data) -> phone_numbers, free);
free(data);
}

/* END listolists.c */

--
pete
Nov 14 '05 #4

P: n/a
pete wrote:

head = man_init(head, seed);
man_print(head);
/* The above doesn't really do what I want */
if (man_init(head, seed) != NULL) {
man_print(head);
} /* This is better */
list_free(head, person_free);
puts("\n/* END listolists.c output */");
return 0;
}


--
pete
Nov 14 '05 #5

P: n/a
thanks a lot for all. your answer really helps me.

Nov 14 '05 #6

P: n/a

"jwvai316" <jw******@gmail.com> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.com...
I don't really know how to say it so I just say it a nested linklist.

How do you make LinkLists inside LinkList?
Can anyone help me for this?
I think an example program will help me a lot.

thank you.


If you make a mistake in writing all the linkages, an easy way to debug it
is make it all doubly linked and have your code traversed it from the last
"tail".
Nov 14 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.