Like Tree3Likes

Linked lists - deleting a list

This is a discussion on Linked lists - deleting a list within the C Programming forums, part of the General Programming Boards category; Originally Posted by laserlight My objection to that sort of loop is that cur->next != NULL kind of makes the ...

  1. #16
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by laserlight View Post
    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?

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,955
    What is your current program, after incorporating whiteflags' updated suggestion?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    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...

  4. #19
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,955
    Quote Originally Posted by Mentallic
    Notice the consecutive t's. This one has me stumped...
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #20
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by laserlight View Post
    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...

  6. #21
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,955
    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;
    }
    Quote Originally Posted by Mentallic
    But I'm still getting a crash when I ask for a 1 letter word...
    Set breakpoints and step through your code until you find where the crash happens. The mistake should be somewhere before that point.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #22
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Mentallic View Post
    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
    laserlight likes this.

  8. #23
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by laserlight View Post
    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.


    Quote Originally Posted by laserlight View Post
    Set breakpoints and step through your code until you find where the crash happens. The mistake should be somewhere before that point.
    Quote Originally Posted by AndiPersti View Post
    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.

    Quote Originally Posted by AndiPersti View Post
    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.

  9. #24
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by Mentallic View Post
    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

  10. #25
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by AndiPersti View Post
    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


    Quote Originally Posted by AndiPersti View Post
    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".

  11. #26
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by Mentallic View Post
    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.
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #27
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by iMalc View Post
    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).

  13. #28
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,955
    That would be equivalent to:
    Code:
    if (current != NULL) {
    while (next != NULL) {
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  2. Linked List deleting Help
    By StealthRT in forum C++ Programming
    Replies: 6
    Last Post: 10-21-2009, 02:19 AM
  3. Deleting linked lists...
    By shiver in forum C++ Programming
    Replies: 2
    Last Post: 07-09-2006, 10:25 PM
  4. deleting a linked list
    By gordy in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 05:01 PM
  5. Deleting - Linked List
    By TeeTee in forum C Programming
    Replies: 2
    Last Post: 09-16-2001, 07:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21