LinkedList of LinkedLists C

Question

Im trying to create a LinkedList that will be populated with LinkedLists. The main LinkedList will hold a characters name and description, as well as how many nodes are held in its inner LinkedList. The inner LinkedList will hold the chapter number they appear in and a brief description for that chapter. So for instance, character Joe(name) is a King(descriptor) and appears in chapters 4 7 and 10. So he would have 3 inner nodes with a description of what he did in those chapters. I don't think Im adding to the lists right though, because when I call to iterate through the lists and print everything, I only get the first person I added.

The two structs I made.

struct Person{
    char * name;
    char * descriptor;
    int count;
    struct Person * next;
    struct Information * info_head;
};
struct Information{
    char * text;
    int chapter;
    struct Information * next;
};

Creating pointers.

struct Person * new_person, *temp_pers, *head_pers;
struct Information * new_info, *temp_info, *head_info;

function used for adding new characters.

void add(char * name, char * descriptor, char * info, int chapter){
new_person = (struct Person *)malloc(sizeof(struct Person));
new_info = (struct Information *)malloc(sizeof(struct Information));

new_info->chapter = chapter;
new_info->text = info;
new_person->name = name;
new_person->descriptor = descriptor;

if(head_pers == NULL){  //List is empty
    head_pers = new_person; //add new person
    new_person->info_head = new_info;//link to information
    head_pers->next = NULL;
    head_info = new_info; //name that information start of information list
    head_pers->count = 1;
    head_info->next = NULL;
}
else{
    temp_pers = head_pers;
    temp_info = head_info;
    while(temp_pers != NULL){ //iterate through list of people
        if(strcmp(temp_pers->name, name) == 0){ //adding a duplicate
            while(temp_info != NULL){ //iterate through that persons info list
                temp_info = temp_info->next;
            } //reached the end of the list
            temp_info = new_info;
            temp_pers->count = temp_pers->count + 1;
            temp_pers->next = NULL;
        }
        temp_pers = temp_pers->next;
    }
    //reached end of persons list with no find
    //add new person to the end of the list
    temp_pers = new_person;
    temp_pers->count = temp_pers->count + 1;
    temp_pers->next = NULL;
}

}

My printing method for testing

void printAll(){
    temp_pers = head_pers;
    temp_info = head_info;
    while(temp_pers != NULL){
        printf("%s, %s %d\n", temp_pers->name, temp_pers->descriptor, temp_pers->count);
        while(temp_info != NULL){
            printf("%d\t%s", temp_info->chapter, temp_info->text);
            temp_info = temp_info->next;
        }
        temp_pers = temp_pers->next;
    }
}

Main method

int main(){
    add("Joe", "the King", "had a child.", 4);
    add("Joe", "the King", "started a war", 7);
    add("Sue", "the Queen", "poisoned Joe", 10);

    printAll();

    return 0;
}

Dealing with a LinkedList of LinkedLists is confusing me and maybe I'm just missing something really small, or maybe something really big, but any help would be great. Almost forgot, the code does compile and outputs this...

    Joe, the King 2
4   had a child.

Because its printing out the count for Joe as 2, I think it's working some what.

You need to actually assign `last_pers->next = temp_pers` in `add` (where `last_pers` needs to point to the last person in the list). — Klas Lindbäck, Oct 14 '15 at 14:32
One correction is, right before the inner while loop, you need to update temp_info to the correct inner linked list's head, like: temp_info = temp_pers->info_head; You shouldn't need a global head_info, assuming the inner lists are independent lists, not connected to each other. — Selçuk Cihan, Oct 14 '15 at 14:41
Oh ok yeah that makes sense @SelçukCihan, I'll make that fix. — John, Oct 14 '15 at 14:44
@KlasLindbäck isn't that what I'm doing by traversing through the list? — John, Oct 14 '15 at 14:46
After traversing the list, `temp_person` points to NULL. Assigning `temp_person` after that does not change the `next` pointer of the last item in the list. — Klas Lindbäck, Oct 14 '15 at 15:07
@Shane, there is no need for casting in malloc, when writing in C: http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc — CIsForCookies, Oct 14 '15 at 18:06

score 3 · Accepted Answer · answered Oct 14 '15 at 17:30

All your global variables except the pers_head should be locals. There is only one head, namely the head of the person list. All other information is contained within this list: Other persons vie the next pointers; information via the person's info. Most importantly, there is no global info head; the info head belongs to each person.

When you print your list of persons and events, you should do so with two loops:

void printAll()
{
    struct Person *pers = head;

    while (pers) {
        printf("%s, %s [%d]\n",
            pers->name, pers->desc, pers->count);

        struct Information *info = pers->info;

        while (info) {
            printf("    %d: %s\n", info->chapter, info->text);
            info = info->next;
        }

        pers = pers->next;
    }
}

Note how pers and info are local variables, not global. They are used and have a meaining only in the scope where they are defined. That's good: It is easy to see that pers just iterates over all persons, nothing else.

When you add a person, you create a new person node right away. But you might not need a new node if the person is already in the list. Create the node only if you really need it.

Your add function does too much stuff: It allocates and populates the nodes and infos and it organises the lists. If you write separate functions to create nodes and to insert an info to a person, the core list code will look cleaner.

A possible implementation (with slightly changed, or rather shortzened, variable names) could be:

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

struct Person{
    char *name;
    char *desc;
    int count;
    struct Person *next;
    struct Information *info;
};
struct Information{
    char *text;
    int chapter;
    struct Information *next;
};

struct Person *head;

struct Information *info_new(char *text, int chapter)
{
    struct Information *info = malloc(sizeof(*info));

    info->text = text;
    info->chapter = chapter;
    info->next = NULL;

    return info;
}

struct Person *pers_new(char *name, char *desc)
{
    struct Person *pers = malloc(sizeof(*pers));

    pers->name = name;
    pers->desc = desc;
    pers->next = NULL;
    pers->info = NULL;
    pers->count = 0;

    return pers;
}

void pers_add_info(struct Person *pers, struct Information *info)
{
    if (pers->info == NULL) {
        pers->info = info;
    } else {
        struct Information *j = pers->info;

        while (j->next) j = j->next;
        j->next = info;
    }

    info->next = NULL;
    pers->count++;
}

void add(char *name, char *desc, char *infotext, int chapter)
{
    struct Information *info = info_new(infotext, chapter);
    struct Person *pers = head;
    struct Person *prev = NULL;

    while (pers) {
        if (strcmp(pers->name, name) == 0
         && strcmp(pers->desc, desc) == 0) {
            pers_add_info(pers, info);
            return;
        }
        prev = pers;
        pers = pers->next;
    }

    pers = pers_new(name, desc);
    pers_add_info(pers, info);

    if (prev) {
        prev->next = pers;
    } else {
        head = pers;
    }
}

void printAll()
{
    struct Person *pers = head;

    while (pers) {
        printf("%s, %s [%d]\n",
            pers->name, pers->desc, pers->count);

        struct Information *info = pers->info;

        while (info) {
            printf("    %d: %s\n", info->chapter, info->text);
            info = info->next;
        }

        pers = pers->next;
    }
}

int main()
{
    add("Joe", "the king", "had a child", 4);
    add("Sue", "the queen", "gave birth to a child", 4);
    add("Ben", "the prince", "is born", 4);
    add("Joe", "the king", "started a war", 7);
    add("Joe", "the king", "returns home victorious", 8);
    add("Ben", "the prince", "is squire to Lord Sam", 8);
    add("Sam", "High Lord", "takes Sam as apprentice", 8);
    add("Ben", "the prince", "goes on a quest", 9);
    add("Sue", "the queen", "poisoned Joe", 10);
    add("Ben", "the prince", "takes revenge", 10);
    add("Sam", "High Lord", "goes on a crusade", 11);
    add("Sue", "the queen", "repents", 14);
    add("Sue", "the hermit", "dies of old age and lonely", 14);

    printAll();

    return 0;
}

Thank you! That makes a lot more sense that everything else should be local! and your right, breaking everything up into more methods makes it easier to read and understand. Your code helped a lot thanks — John, Oct 14 '15 at 17:34

CIsForCookies · Answer 2 · 2015-10-14T16:32:00.040

As you can see, your code prints out the first node and sub-node: ("Joe", "the King", "had a child.", 4) and that means your insertion is working, at least at start. After this line it terminates, meaning temp_pers = temp_pers->next == NULL;

Now, let's look at your second insertion:

else{
temp_pers = head_pers;
temp_info = head_info;
while(temp_pers != NULL){ //iterate through list of people
    if(strcmp(temp_pers->name, name) == 0){ //adding a duplicate
        while(temp_info != NULL){ //iterate through that persons info list
            temp_info = temp_info->next;
        } //reached the end of the list
        temp_info = new_info;
        temp_pers->count = temp_pers->count + 1;
        temp_pers->next = NULL;
    }
    temp_pers = temp_pers->next;
}
//reached end of persons list with no find
//add new person to the end of the list
temp_pers = new_person;
temp_pers->count = temp_pers->count + 1;
temp_pers->next = NULL;
}

You created a temp_pers and assigned it something but after the scope ends, this node isn't connected to your head_pers. So, each time you construct a new struct and assign it to temp_pers you are not entering it to the main linked list (a.k.a head_pers), so each time you check the condition inside your loop (this one: while(temp_pers != NULL)) you check the last node you created, and since it isn't linked to something, it gives you NULL on the next node.

How to fix: head_pers->next = temp_pers; in the else section. Now, this will make sure the 2nd node is connected to the 1st. From now on, each node you create should be connected the the end of the list. You can do that by saving the last node (O(1) time), or by iterating through the list on each add (O(n) time)

Your fix doesn't work. `head_pers` always points to the first item, so your fix limits the list to 2 items. He needs to find the last item (the one where `->next == NULL`) and set its `next` pointer to the new person. — Klas Lindbäck, Oct 14 '15 at 14:38
@KlasLindbäck You are right. That will only fix the second element. I will add the generic fix. thx for pointing that — CIsForCookies, Oct 14 '15 at 16:30

Klas Lindbäck · Answer 3 · 2015-10-15T06:31:11.883

1

In add, after the loop, temp_pers points to NULL. You need to keep a pointer to the last person in the list:

struct Person *last_pers;

last_pers = temp_pers;

while(temp_pers != NULL){ //iterate through list of people
    if(strcmp(temp_pers->name, name) == 0){ //adding a duplicate
        while(temp_info != NULL){ //iterate through that persons info list
            temp_info = temp_info->next;
        } //reached the end of the list
        temp_info = new_info;
        temp_pers->count = temp_pers->count + 1;
        temp_pers->next = NULL;
    }
    last_pers = temp_pers;
    temp_pers = temp_pers->next;
}
//reached end of persons list with no find
//add new person to the end of the list
last_pers->next = new_person;  
new_person->count = 1;
new_person->next = NULL;

edited Oct 15 '15 at 06:31

answered Oct 14 '15 at 15:02

Klas Lindbäck

33,105
5
57
82

I changed it to struct Person *las_pers; and now it works a little bit... it now prints out 'Joe, the King 2 4 had a child. Joe, the King 12 Sue, the Queen 7' – John Oct 14 '15 at 15:54
Thanks, that was a typo on my part. – Klas Lindbäck Oct 15 '15 at 06:32

LinkedList of LinkedLists C

3 Answers3