Thread: Linked lists - deleting a list

Originally Posted by laserlight

My objection to that sort of loop is that cur->next != NULL kind of makes the "next" sound like the "current". I guess that cannot be helped if you want to avoid otherwise unnecessary checks, but then head should be checked before the entire loop is run, just in case.

I tested my program with a 1 letter word and it crashed. Why though? I thought my for loop's break accounted for it.

If we have a 1 letter word, then head->next = NULL, hence it should never go into the for loop?

This is my current program:

Code:

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

#define ALPHABET 26

typedef struct Node {
    char letter;
    struct Node *next;
} NodeT;

int isNum(char *);
NodeT *addNode(NodeT *);
NodeT *addLetter(NodeT *);
void printList(NodeT *);
NodeT *removeDupes(NodeT *);
void freeList(NodeT *);

int main(int argc, char **argv) {
    int length = 0;
    int seed = 0;
    NodeT *head1 = NULL;
    NodeT *head2 = NULL;
    int i = 0;
    
    if (argc != 3 || !isNum(argv[1]) || !isNum(argv[2])) {
        fprintf(stderr, "Usage: ./llrandword "
                "wordlength randomseed\n"); 
        return EXIT_FAILURE;  
    }
    
    length = atoi(argv[1]);
    seed = atoi(argv[2]);
    srandom(seed);
    
    for(i=0; i<length; i++) {
       head1 = addNode(head1);
    }
    
    head1 = addLetter(head1);
    printList(head1);
    putchar('\n');
    
    head2 = head1;
    head2 = removeDupes(head1);
    printList(head2);
    putchar('\n');
    
    freeList(head1);
    freeList(head2);

    return EXIT_SUCCESS;
}

int isNum(char *string) {
    int isNum = 1;
    
    while(*string != '\0') {
        if (*string < '0' || *string > '9') {
            isNum = 0;
        }
        string++;
    }
    
    return isNum;
}

NodeT *addNode(NodeT *list) {
    NodeT *new = NULL;
    NodeT *cur = NULL;
    
    new = malloc(sizeof(NodeT));
    if (new == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    
    if (list == NULL) {
        list = new;
    } else {
        cur = list; 
        while (cur->next != NULL) {
            cur=cur->next;
        }
        cur->next = new;
    }
    
    new->next = NULL;
    
    return list;
}

NodeT *addLetter(NodeT *head) {
    NodeT *cur = NULL;
    int r = 0;
    int rand = 0;
    
    for(cur = head; cur != NULL; cur = cur->next) {
        r = random();
        rand = r % ALPHABET;
        cur->letter = 'a'+rand;
    }
    
    return head;
}

void printList(NodeT *head) {
    NodeT *cur = NULL;
    
    for (cur=head; cur != NULL; cur=cur->next) {
        printf("%c", cur->letter);
        if(cur->next != NULL) {
            printf("->");
        }
    }
}

NodeT *removeDupes(NodeT *head) {
    NodeT *cur = NULL;
    NodeT *tmp = NULL;
    
    for(cur=head; cur->next != NULL; cur = cur->next) {
        if (cur->letter == cur->next->letter) {
            tmp = cur->next->next;
            free(cur->next);
            cur->next = tmp;
        }
    }
    
    return head;
}

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

So the bugs for the moment are that it crashes when I input a 1 letter word, or when the duplicate letters are located at the end of the list. I suppose adding in some testcases would fix that, but this last bug I have is what's puzzling me the most.

What my expected output should be:

$ ./llrandword 10 4747
e->p->h->h->b->t->t->t->t->o
e->p->h->b->t->o

What I get:

$ ./llrandword 10 4747
e->p->h->h->b->t->t->t->t->o
e->p->h->b->t->t->o

Notice the consecutive t's. This one has me stumped...

Originally Posted by laserlight

Ah, that's because the loop considers each "next" node in turn. The problem is, when you have more than two consecutive duplicates, this means that the "current" node is not considered again. For example:
t1 -> t2 -> t3 -> u
t1 == t2, so we remove t2 to get:
t1 -> t3
But on the next iteration of the loop, the current is now t3, and since t3's next node is not a duplicate, there is no removal, hence you get the output:
t -> t -> u

To fix this, you will need to avoid changing the current node unless there is no duplicate. I think changing the for loop to a while loop would be appropriate.

Nice work spotting that!

I have that bug fixed now with my removeDupes function currently as

Code:

NodeT *removeDupes(NodeT *head) {
    NodeT *cur = head;
    NodeT *tmp = NULL;
    
    while (cur->next != NULL) {
        if (cur->letter == cur->next->letter) {
            if (cur->next->next != NULL) {
                tmp = cur->next->next;
                free(cur->next);
                cur->next = tmp;
            } else {
                cur->next = NULL;
            }
        } else {
            cur = cur->next;
        }
    }
    
    return head;
}

But I'm still getting a crash when I ask for a 1 letter word...

Originally Posted by Mentallic

So the bugs for the moment are that it crashes when I input a 1 letter word

It should also crash if your list contains more than one letter (although it doesn't crash on my computer either for cases >1 letter).

The reason is the following:

Code:

head2 = head1;
head2 = removeDupes(head1);
printList(head2);
putchar('\n');
    
freeList(head1);
freeList(head2);

head1 and head2 point to the same list. With "freeList(head1)" you free all allocated memory. With "freeList(head2)" you want to free the same memory a second time (you never allocate any new memory for head2). Using free a second time is undefined behavior.

Look also at the output of valgrind:

Code:

$ valgrind -q ./test 3 4747 
e->p->h
e->p->h
==2314== Invalid read of size 4
==2314==    at 0x804890B: freeList (test.c:137)
==2314==    by 0x80486E1: main (test.c:49)
==2314==  Address 0x41ec02c is 4 bytes inside a block of size 8 free'd
==2314==    at 0x402AE46: free (vg_replace_malloc.c:427)
==2314==    by 0x804891B: freeList (test.c:138)
==2314==    by 0x80486D5: main (test.c:48)
==2314== 
==2314== Invalid free() / delete / delete[] / realloc()
==2314==    at 0x402AE46: free (vg_replace_malloc.c:427)
==2314==    by 0x804891B: freeList (test.c:138)
==2314==    by 0x80486E1: main (test.c:49) 
==2314==  Address 0x41ec028 is 0 bytes inside a block of size 8 free'd
==2314==    at 0x402AE46: free (vg_replace_malloc.c:427)
==2314==    by 0x804891B: freeList (test.c:138)
==2314==    by 0x80486D5: main (test.c:48)
==2314==

You don't have to free head2.

Bye, Andreas

Originally Posted by laserlight

Personally, I tested with this implementation:

Code:

NodeT *removeDupes(NodeT *head) {
    NodeT *current = head;
    if (current) {
        NodeT *next = current->next;
        while (next) {
            if (current->letter == next->letter) {
                current->next = next->next;
                free(next);
            } else {
                current = next;
            }
            next = current->next;
        }
    }
    return head;
}

Well, my own makes more sense to me, but I do appreciate some of the techniques you've used, such as letting next = cur->next.

Originally Posted by laserlight

Set breakpoints and step through your code until you find where the crash happens. The mistake should be somewhere before that point.

Originally Posted by AndiPersti

The reason is the following:

Code:

head2 = head1;
head2 = removeDupes(head1);
printList(head2);
putchar('\n');
    
freeList(head1);
freeList(head2);

head1 and head2 point to the same list. With "freeList(head1)" you free all allocated memory. With "freeList(head2)" you want to free the same memory a second time (you never allocate any new memory for head2). Using free a second time is undefined behavior.

I also found it crashes after my first freeList, which makes sense. I'm unsure with how to change it though. Yes, removing freeList(head2) would make it work, but I'm still seeing a problem with it If I make head2 the duplicate removed version of head1, then when I go to free head1 (since it's now head2), I'll only be freeing up to the new NULL pointer in head2 - so I'll have memory leaks.

Originally Posted by AndiPersti

It should also crash if your list contains more than one letter (although it doesn't crash on my computer either for cases >1 letter).

Yeah it's weird that it works for >1.

Originally Posted by Mentallic

I also found it crashes after my first freeList, which makes sense. I'm unsure with how to change it though. Yes, removing freeList(head2) would make it work, but I'm still seeing a problem with it If I make head2 the duplicate removed version of head1, then when I go to free head1 (since it's now head2), I'll only be freeing up to the new NULL pointer in head2 - so I'll have memory leaks.

Sorry, I don't understand what you mean.
"head2" isn't really necessary at all in your program because it is just a copy of "head1".
In "removeDupes()" you free the memory of all the nodes you remove from the list. In "freeList()" you free all nodes which are still in the list. Where do you see a memory leak?

Yeah it's weird that it works for >1.

That's what "undefined behavior" means. It may work or it may not, nobody knows :-).

Bye, Andreas

Originally Posted by AndiPersti

Sorry, I don't understand what you mean.
"head2" isn't really necessary at all in your program because it is just a copy of "head1".
In "removeDupes()" you free the memory of all the nodes you remove from the list. In "freeList()" you free all nodes which are still in the list. Where do you see a memory leak?

Oh yeah... Staring at the terminal and seeing all those outputs of my program has given me the wrong idea

Originally Posted by AndiPersti

That's what "undefined behavior" means. It may work or it may not, nobody knows :-).

Bye, Andreas

I would've guessed that undefined behaviour means that it will do different things in varying situations, but once you pinpoint the situation you're dealing with, you can surely reason as to why it's doing it the way it's doing it.

At least, that's sometimes the case in the mathematical sense of the word "undefined".

Originally Posted by iMalc

Yeah most people feel that way, and it's not wrong to feel that way. However, there is a big advantage to putting in the effort to understand code which someone else has written when it is simpler than your own. The benefit is far beyond ending up with better code; If you can get yourself to think a little differently about the problem, in a way that is simpler, then you really start to understand what you're doing a whole lot better. It can be very unexpectedly enlightening.

Speaking personally, it is doing precisely that, many years ago, which got me to where I am, in my ability to write very simple code about anything right from the outset. I'm known at work as being one of the fastest churners of code, without compromising on quality. It's not just the raw programming knowledge, it's definitely the mindset also.

Actually, I often do that. I did read through his code but the problem was that I don't understand what the

Code:

if (current) {
while (next) {

lines do, so I kind of gave up (a little prematurely I suppose).