Linked Lists

[Mentallic]

I'm getting a seg fault in this program on linked lists, and frankly, I'm not surprised because this topic has been giving me a hell of a lot of trouble.

What I have so far is

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

typedef struct _Node {
    int value;
    struct _Node *next;
} NodeT;

NodeT *makeNode(int data);
NodeT *joinList(NodeT *head1, NodeT *head2);
void printList(NodeT *head);
void freeList(NodeT *head);

int main(int argc, char *argv[]) {
    NodeT *l = NULL;
    NodeT *head = NULL;
    NodeT *prevl = NULL;
    int data = 0;
    int numScanned = 1;
    int count = -1;
    
    while (numScanned) {
        printf("Enter an integer: ");
        numScanned = scanf("%d", &data);
        if (numScanned) {
            count++;
            l = makeNode(data);
            if (count == 0) {
                head = l;
            } else {
                prevl = l;
            }
            l->next = joinList(prevl, l);
            
        }
    }
    for (l = head; l!=NULL; l = l->next) {
        printList(l);
    }
    
    return EXIT_SUCCESS;
}

NodeT *makeNode(int data) {
    NodeT *new;
    new = malloc(sizeof(NodeT));
    if (new == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    new->value = data;
    new->next = NULL;
    return new;
}

NodeT *joinList(NodeT *head1, NodeT *head2) {
    head1->next = head2;
    return head1->next;
}

void printList(NodeT *head) {
    NodeT *cur = head;
    while (cur != NULL) {
        printf("%d", cur->value);
        cur=cur->next;
        if (cur != NULL) {
            printf("->");
        }
    }
    printf("\n");
}

void freeList(NodeT *head) {
    NodeT *cur;
    cur = head;
    while (cur != NULL) {
        NodeT *tmp = cur->next;
        free(cur);
        cur = tmp;
    }
}

I'm fairly comfortable with all functions except the joinList one, and I'm unsure about the way my main has been set out either. If someone can be bothered to scrutinize my program, I'd be very thankful.

[laserlight]

What exactly is joinList supposed to do?

[sana.iitkgp]

When you are calling joinList(); for first time you are passing head1 as NULL, so there is no point of head1->next. That is where program is terminated.
Modify your program accordingly.

[Mentallic]

What exactly is joinList supposed to do?

It's supposed to return the pointer between one node and the next to create the link.

When you are calling joinList(); for first time you are passing head1 as NULL, so there is no point of head1->next. That is where program is terminated.
Modify your program accordingly.

head1 isn't NULL though? I think the problem is that head1 == head2 so that line
head1->next = head2;
is wrong.

[sana.iitkgp]

    NodeT *prevl = NULL;   <<<<<---- prevl is NULL
    int data = 0;
    int numScanned = 1;
    int count = -1;
    
    while (numScanned) {
        printf("Enter an integer: ");
        numScanned = scanf("%d", &data);
        if (numScanned) {
            count++;  <<<--count is '0' now
            l = makeNode(data);
            if (count == 0) {
                head = l;
            } else {
                prevl = l;   <<<<---- still prevl is NULL as this not executes at all
            }
            l->next = joinList(prevl, l);   <<<<------ prevl is head1 so head1 is NULL
            
        }

You got my point?

[laserlight]

It's supposed to return the pointer between one node and the next to create the link.

Are you sure it is not supposed to join the two linked lists, returning a pointer to the first node of the resulting linked list?

[iMalc]

It's supposed to return the pointer between one node and the next to create the link.

Given how unintelligible that description is, it's no wonder it doesn't do anything useful at present.
Currently the way you are using it leaves you with l->next pointing at itself.

I'd advise getting your thoughts straight as to what it is supposed to do, and I agree with laserlight as to what it's probably meant to do.

[Mentallic]

You got my point?

Ahh yes I see now.

Are you sure it is not supposed to join the two linked lists, returning a pointer to the first node of the resulting linked list?

Yeah sorry that is what I meant but you've said it more clearly.

Given how unintelligible that description is, it's no wonder it doesn't do anything useful at present.
Currently the way you are using it leaves you with l->next pointing at itself.

I'd advise getting your thoughts straight as to what it is supposed to do, and I agree with laserlight as to what it's probably meant to do.

That's one of my problems with this topic. I missed the lecture when we were introduced to linked lists and all of a sudden the second lecture makes no sense and I'm now left stranded, twiddling my thumbs as I stare at the code trying to make sense of it all. I definitely need to try and wrap my head around this.

I've made a few changes thus far, and I've changed some variable names too just for it to make a little more sense for me.

int main(int argc, char *argv[]) {
    NodeT *l = NULL;
    NodeT *cur = NULL;
    NodeT *prevl = NULL;
    int data = 0;
    int numScanned = 1;
    int count = -1;
    
    while (numScanned) {
        printf("Enter an integer: ");
        numScanned = scanf("%d", &data);
        if (numScanned) {
            count++;
            cur = makeNode(data);
            if (count == 0) {
                l = cur;
                prevl = cur;
            } else {
                prevl->next = joinList(prevl, cur);
                prevl = cur;
            }
        }
    }
    for (l = cur; cur!=NULL; cur = cur->next) {
        printList(cur);
    }
    
    return EXIT_SUCCESS;
}

NodeT *joinList(NodeT *head1, NodeT *head2) {
    head1->next = head2;
    return head1->next;
}

It's actually not compiling. The error is that my node l is declared but unused, even though it's used in my main (the node l stands for list, it's basically the start of the linked list).

[laserlight]

It's actually not compiling. The error is that my node l is declared but unused, even though it's used in my main (the node l stands for list, it's basically the start of the linked list).

That should not result in an error, though it might result in a warning. By the way, l is generally a poor choice of variable name because of its close resemblance to I and/or 1 on several fonts.

Basically, the idea here is: find the last node (tail) of the first linked list and set its next pointer to point to the head of the second linked list.

[AndiPersti]

    for (l = cur; cur!=NULL; cur = cur->next) {
        printList(cur);
    }

You get the warning because you only assign values to "l" but never use it.
The reason is your for-loop for printing the list. "l" is the root node of your list (and should be called head or root because it is just one node and not the whole list) and you should never overwrite it otherwise you will loose the reference to the list.
You should flip the assignemt inside the for-loop.

Bye, Andreas

[Mentallic]

That should not result in an error, though it might result in a warning.

Oh right, sorry, that's what I was meant to say. Our class requires that we compile all our programs with the flags -Wall -Werror -O.

By the way, l is generally a poor choice of variable name because of its close resemblance to I and/or 1 on several fonts.

I totally agree, I only chose it because one of the class examples used that variable so I've changed it to head.

Basically, the idea here is: find the last node (tail) of the first linked list and set its next pointer to point to the head of the second linked list.

NodeT *joinList(NodeT *head1, NodeT *head2) {
    head1->next = head2;
    return head1->next;
}

Does just that doesn't it?

    for (l = cur; cur!=NULL; cur = cur->next) {
        printList(cur);
    }

You get the warning because you only assign values to "l" but never use it.
The reason is your for-loop for printing the list. "l" is the root node of your list (and should be called head or root because it is just one node and not the whole list) and you should never overwrite it otherwise you will loose the reference to the list.
You should flip the assignemt inside the for-loop.

Bye, Andreas

Thanks for spotting that! What a silly mistake...

Ok so it seems like I've gotten the program working exactly the way I needed it to, and frankly I'm really surprised at how little changes I needed to make. Thanks for all the help guys.

[laserlight]

NodeT *joinList(NodeT *head1, NodeT *head2) {
    head1->next = head2;
    return head1->next;
}

Does just that doesn't it?

No, it doesn't, except for the special case where the first linked list only has exactly one element. Even then, it returns the wrong thing.

[AndiPersti]

No, it doesn't, except for the special case where the first linked list only has exactly one element. Even then, it returns the wrong thing.

I think Mentallic has still problems with the right vocabulary for linked lists.
The last version of the program he has shown us is appending every new node at the end of the list. "prevl" should therefore better be called "tail" and "joinList()" should be called "appendNode()" (there is no second list to join). But this function isn't really necessary because if he changes line 19

prevl->next = joinList(prevl, cur);

to

prevl->next = cur;

the result will be the same.

Bye, Andreas

[Mentallic]

No, it doesn't, except for the special case where the first linked list only has exactly one element. Even then, it returns the wrong thing.

What my program is supposed to do is to create a linked list, not to join two linked lists together from head to tail. Each node needs to be connected to the next node in the list such that when I call my print function

void printList(NodeT *head) {
    NodeT *cur = head;
    while (cur != NULL) {
        printf("%d", cur->value);
        cur=cur->next;
        if (cur != NULL) {
            printf("->");
        }
    }
}

It will print out each node as expected. The output should be as follows:

prompt$ ./llbuild
Enter an integer: 12
Enter an integer: 34
Enter an integer: 56
Enter an integer: a
Finished: list is 12->34->56

I think Mentallic has still problems with the right vocabulary for linked lists.
The last version of the program he has shown us is appending every new node at the end of the list. "prevl" should therefore better be called "tail" and "joinList()" should be called "appendNode()" (there is no second list to join).

Yes that's what I need to be doing - sorry about all the confusion.

But this function isn't really necessary because if he changes line 19

prevl->next = joinList(prevl, cur);

to

prevl->next = cur;

the result will be the same.

Bye, Andreas

Except this is homework and one of the requirements is that I created a function joinList with those parameters given. It may be unnecessary and convoluted on its own, but it's required. Maybe it's possible however to clean up my main somehow? I feel like it could be more succinct.

[AndiPersti]

Except this is homework and one of the requirements is that I created a function joinList with those parameters given. It may be unnecessary and convoluted on its own, but it's required. Maybe it's possible however to clean up my main somehow? I feel like it could be more succinct.

Ok, then joinList is not the best name for the function but you have to live with it.

Currently you maintain in main a pointer to the tail of the list (prevl) and so it's pretty easy to add a new node at the end of the list.
But perhaps the reason for your assingment was to do all the work in the function (with or without a helping tail pointer) and your main should just look like:

int main(void)
{

    NodeT *list = NULL, *new_node;
       
    do 
    {
        // get number
        new_node = makeNode(data);
        list = joinList(new_node);
    } while (breaking condition);

    printList(list);
    freeList(list);
    return 0;
}

But without knowing the exact assignment that's just my guess.

Bye, Andreas