Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #59984

Re: Malloc without free in linked list code

Show all headers | View raw

Paul <pepstein5@gmail.com> writes:

> The following code is quoted verbatim from a well-known CS course at
> an extremely prestigious university.
>
> Why is it ok to use malloc without free?  Does this leak memory?  If
> not, why not?

That's answered, so I'll just make a remark about the code.
Re-formatted a little (and with the sizeof altered to my taste) it is:

  struct node *CopyList(struct node *head)
  {
       struct node *current = head;
       struct node *newList = NULL;
       struct node *tail = NULL;
   
       while (current != NULL) {
            if (newList == NULL) {
                 newList = malloc(sizeof *newList);
                 newList->data = current->data;
                 newList->next = NULL;
                 tail = newList;
            }
            else {
                 tail->next = malloc(sizeof *tail->next);
                 tail = tail->next;
                 tail->data = current->data;
                 tail->next = NULL;   
            }
            current = current->next;
       }
       return newList;
  }

Let's rewrite the inner "if" a little and add ()s for emphasis:

            if (newList == NULL) {
                 (newList) = malloc(sizeof *newList);
                 (newList)->data = current->data;
                 (newList)->next = NULL;
                 tail = (newList);
            }
            else {
                 (tail->next) = malloc(sizeof *tail->next);
                 (tail->next)->data = current->data;
                 (tail->next)->next = NULL;   
                 tail = (tail->next);
            }

Now you can see that both arms are really doing exactly the same thing,
but one uses newList as the object to modify (on the first iteration)
and the other arm uses tail->next (on all subsequent iterations).  It's
much neater, to my mind, to combine them, thereby removing the test:

   *tailp = malloc(sizeof **tailp);
   (*tailp)->data = current->data;
   (*tailp)->next = NULL;
   tailp = &(*tailp)->next;

Finally, you might spot that setting the "next" pointer to NULL needs to
be done only once.  You get:

  struct node *CopyList(struct node *head)
  {
       struct node *current = head;
       struct node *newList = NULL;
       struct node **tailp = &newList;
   
       while (current != NULL) {
            *tailp = malloc(sizeof **tailp);
            (*tailp)->data = current->data;
            tailp = &(*tailp)->next;
            current = current->next;
       }
       *tailp = NULL;
       return newList;
  }

though I'd not bother with the extra "current" pointer.

But the clearest method of all is probably to use recursion:

  struct node *CopyList(struct node *list)
  {
       if (list) {
            struct node *new_list = malloc(sizeof *new_list);
            new_list->data = list->data;
            new_list->next = CopyList(list->next);
            return new_list;
       }
       return NULL;
  }

-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Malloc without free in linked list code Paul <pepstein5@gmail.com> - 2015-04-13 11:21 -0700
  Re: Malloc without free in linked list code Lőrinczy Zsigmond <nospam@for.me> - 2015-04-13 20:45 +0200
  Re: Malloc without free in linked list code Richard Heathfield <rjh@cpax.org.uk> - 2015-04-13 19:53 +0100
  Malloc without free in linked list code asetofsymbols@gmail.com - 2015-04-13 12:05 -0700
  Re: Malloc without free in linked list code Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-13 21:58 +0100
    Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 09:26 +0200
      Re: Malloc without free in linked list code Paul <pepstein5@gmail.com> - 2015-04-14 01:45 -0700
        Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 11:39 +0200
          Re: Malloc without free in linked list code Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-14 13:43 +0100
            Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 15:10 +0200
              Re: Malloc without free in linked list code Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-14 16:10 +0100
                Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 17:37 +0200
                Re: Malloc without free in linked list code Keith Thompson <kst-u@mib.org> - 2015-04-14 11:44 -0700
                Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-15 00:00 +0200
                Re: Malloc without free in linked list code Richard Heathfield <rjh@cpax.org.uk> - 2015-04-14 20:12 +0100
                Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-15 00:04 +0200
                Re: Malloc without free in linked list code Richard Heathfield <rjh@cpax.org.uk> - 2015-04-15 00:20 +0100
              Re: Malloc without free in linked list code Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-16 15:46 -0700
                Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-17 10:38 +0200
                Re: Malloc without free in linked list code Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-17 08:30 -0700
        Re: Malloc without free in linked list code James Kuyper <jameskuyper@verizon.net> - 2015-04-14 08:04 -0400
  Re: Malloc without free in linked list code Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-14 05:38 -0700
  Re: Malloc without free in linked list code BGB <cr88192@hotmail.com> - 2015-04-14 10:31 -0500
  Malloc without free in linked list code Chad <cdalten@gmail.com> - 2015-04-14 19:51 -0700
    Re: Malloc without free in linked list code James Kuyper <jameskuyper@verizon.net> - 2015-04-14 23:10 -0400

csiph-web