Freeing double linked list I created

Question

I tried to free the linked list I created , but I failed.

An extension on the previous question I asked "Merge double linked list", it is OK if you don't check it or know nothing about it.
I created two double linked list, and I merged them, and after that, I want to free them all. So I wrote the delete_list() function.
But eventually, I failed, the error is "error for object 0x100404110: pointer being freed was not allocated".
If I only free the first list l, the code works. But if I tried to free all or two, the code crushed.
Can anyone help me with it? Thanks!!

 #include <stdio.h>
 #include<stdlib.h>
typedef struct Node
{
   struct Node* prior;
   struct Node* next;
   int value;
}Node,*list;
list create_list()
{
   list head = (list)malloc(sizeof(Node));
   if(!head) exit(-1);
   list tail;
   tail=head;
   printf("Please enter the length of double linked list:\n");
   int len;
   scanf("%d",&len);
  for(int i=0;i<len;i++)
  {
       list new = (list)malloc(sizeof(Node));
       if(!new) exit(-1);
       new->next=NULL;
       printf("Please enter the value of node:\n");
       int val;
       scanf("%d",&val);
       new->value=val;
       tail->next = new;
       new->prior=tail;
       tail=new;
    }
    return head;
 }
  list merge_list(list a,list b)//合并两个非递减双向链表
  {
     if(a==NULL||b==NULL) exit(-1);
     list p=(list)malloc(sizeof(Node));
     list l=p;
     while(a&&b)
    {
        if(a->value<=b->value)
        {
           p->next = a;
           a->prior=p;
           p=a;
           a=a->next;

        }
       else
      {
          p->next = b;
          b->prior=p;
          p=b;
          b=b->next;

      }
     }
    if(a!=NULL)
    {
        p->next=a;
       a->prior=p;
    }
    if(b!=NULL)
    {
        p->next=b;
     b->prior=p;
    }
   return l;
}
 int delete_List(list l)
   {
       if(l==NULL)
       {
          printf("List is empty!");
          exit(-1);
       }
       list temp;

       while(l)
      {
         temp = l->next;
         free(l);
         l=NULL;
         l=temp;
      }
     return 1;
   }

   int main() {
       list l = create_list();
       l=l->next;//throw away the empty node
       list m = create_list();
       m=m->next;//throw away the empty node
       list n =merge_list(l,m);
       n=n->next;  //throw away the empty node
       delete_List(l);
       delete_List(m);
       delete_List(n);   
       return 0;
   }

NO error.

You missed one very crucial part of code in your [mcve]: The `create_list` function. As well as the `list` type and its definition. — Some programmer dude, Jan 24 '19 at 16:09
Your MCVE is also missing the `merge_list()` function. If you can delete both lists separately without the merge, then the merge is probably the problem (and we need to see both the create and the merge list functions). If you can't delete both lists separately, we don't need the `merge_list()` because it isn't part of the _minimal_ MCVE. You would remove the call to merge. — Jonathan Leffler, Jan 24 '19 at 16:11
I observe that the loop `while(l)` is a good demonstration of why you don't use `l` as a variable name; it is too easily confused with digit `1`, and a `while (1)` loop is an infinite loop. To make it clearer, you could write `while (l != NULL)`, but it might be better to use `lp` (list pointer) or some other name. See also [Is it a good idea to typdef pointers](https://stackoverflow.com/questions/750178/is-it-a-good-idea-to-typedef-pointers) — TL;DR, it generally isn't a good idea. — Jonathan Leffler, Jan 24 '19 at 16:16
`l=l->next;//throw away the empty node` - why aren't you freeing this empty node? Surely it would also make more sense to write your code so you didn't end up with it in the first place? — Chris Turner, Jan 24 '19 at 16:20
because the first node of the list is empty, I should throw it away to pass the list — Liu, Jan 24 '19 at 16:24
But you don't throw it away properly. You need to adjust the previous pointer of the new head of the list. You should also free the node that just ignored; you (should have) allocated it. And you shouldn't need to do that; you should be able to read the first value into the first node. — Jonathan Leffler, Jan 24 '19 at 16:34
OT: for ease of readability and understanding: 1) please consistently indent the code. Suggest each indent level be 4 spaces. 2) variable names (and parameter names) should indicate `content` or `usage` (or better, both) names like 'l' 'p' are meaningless, even the current context. 3) separate code blocks `for` `if` `else` `while` `do...while` `switch` `case` `default` via a single blank line. 4) separate functions by 2 or 3 blank lines (be consistent). 5) follow the axiom: *only one statement per line and (at most) one variable declaration per statement.* — user3629249, Jan 24 '19 at 16:35
OT: when calling any of the `scanf()` family of functions, always check the returned value (not the parameter values) to assure the operation was successful. — user3629249, Jan 24 '19 at 16:39
OT: regarding: `list head = (list)malloc(sizeof(Node));` 1) always check (!=NULL) the returned value to assure the operation was successful. 2) in C, the returned type is `void*` which can be assigned to any pointer. Casting just clutters the code, making it more difficult to understand, debug, etc — user3629249, Jan 24 '19 at 16:42
regarding: `list new = malloc(sizeof(Node)); if(!new) exit(-1);` This abrupt exit results in a memory leak. In this case, the OS will cleanup, however, it is a very poor habit to expect the OS to clean up after sloppy code — user3629249, Jan 24 '19 at 16:47
in function: `create_list()`, the list pointer `tail` is never seen outside of that function, so the declaration and all related code should be removed — user3629249, Jan 24 '19 at 16:54
in function: `delete_list()` this pair of statements: ` l=NULL; l=temp;` seems a bit 'off' the setting of 'l' to NULL, then immediately setting it to 'temp' means the setting of 'l' to NULL is not necessary and just clutters the code. Suggest removing the statement: `l = NULL;` — user3629249, Jan 24 '19 at 17:19
thanks and why I shouldn't ignore the first empty node?? Anything wrong with that?? — Liu, Jan 25 '19 at 16:10

score 2 · Answer 1 · answered Jan 24 '19 at 16:47

I believe your problem lies in calling delete_list on the component lists that you passed to your merge_list function.

If I understand your code correctly, a list is really just a pointer to the first node of the linked list. Your create_list allocates the nodes, and returns the address of the first, which you then discard for whatever reason, resulting in a pointer to the second allocated node.

Something like this:

list l = pointer to [1] -> [2] -> [3] ...
list m = pointer to [5] -> [10] -> [15] ...

Your merge_list performs a merge sort of the two lists, using the same nodes by changing the next/prev pointers.

while(a&&b)
{
    if(a->value<=b->value)
    {
       p->next = a;
       a->prior=p;
       p=a;
       a=a->next;

This means that list pointer l and list pointer m and list pointer n (the merged list) are all pointing to the same nodes. When you do list n = merge_list(l,m) the result is something like:

list n = pointer to [1] -> [2] -> [3] -> [5] -> [10] ...
list l = pointer to ^
list m = pointer to 5 ...................^

(The 'l' and 'm' pointers are not changing, but the nodes that they point to are being modified by the merge function.)

When you try to free the list nodes in your delete function, the first call to delete list 'l' will work. The call to delete list 'm' will either fail immediately (if the first node of 'm' was greater than the first node of 'l', as in my example) or free some nodes and then fail. The delete of 'n' will fail since all the nodes making up 'n' are deleted in the calls to delete 'l' and 'm'.

You can fix this in several ways. The easiest is simply to reset the l and m list pointer to NULL when you call the merge, since in your system merging the two lists "consumes" them, and thus ownership transfers from the parameters to the result.

list n = merge_list(l, m); l = m = NULL;

Another way would be for the merge function to create duplicate nodes, meaning that merge_list would actually produce copies of the two lists, allowing ownership of the parameters to be maintained by the caller.

list n = merge_list(l, m);
// now n, l, m, all exist and are separate

A final solution would be for you to create a true "list" object that sits between the caller and the node objects. This object could be modified to reflect either reality, but it would be separate, and so would not get overwritten during merge operations, etc. (I don't recommend this, btw. It's formal, but inefficient.)

there is one thing I still don't understand. Since you can't change a pointer's final address it pointers to after you pass it to a function. Then why you can free the pointer in a function?? — Liu, Jan 25 '19 at 15:02

score 2 · Answer 2 · answered Jan 24 '19 at 16:48

The obvious answer to why you can't free the 3 lists is because you don't have 3 lists. Your function merge_list is doing exactly what the name (sort of) suggests. It is taking the 2 lists and merging them into 1 list. So you don't have to free the 2 original lists, you only need to free the merged one.

user3629249 · Answer 3 · 2019-01-24T23:02:13.933

the function: create_list() has several problems including not checking for errors and not properly handling the insertion of the new node at the front of the list and not handling the first entry into a linked list correctly.

The formatting/style of the code leaves a lot to be desired.

The single character parameter and local variable names are meaningless Such names should indicate content or usage

The delete_list() should not be returning anything as there is nothing left to return. So the signature changed to:

void delete_List( Node *list )

should not typedef a pointer as that just adds confusion to the code.

The following proposed code fixes the above problems and formats the code for readability

Caveat: it has not been tested yet

struct NODE
{
   struct NODE* prior;
   struct NODE* next;
   int value;
};
typedef struct NODE  Node;

Node * create_list()
{
    Node * head = NULL;

    printf("Please enter the length of double linked list:\n");
    int len;
    if( scanf("%d",&len) != 1 )
    {
        fprintf( stderr, "scanf for length of list failed\n" );
        return NULL;
    }

    for( int i=0; i<len; i++ )
    {
        Node * newNode = malloc(sizeof(Node));
        if ( !newNode )
        {
            perror( "malloc for list nodefailed" );
            // cleanup here
            exit( EXIT_FAILURE );
        }

        if ( !head )
        { // then first entry into linked list
            newNode->next  = NULL;
            newNode->prior = NULL;
        }

        else
        {
            //insert node at front of list
            newNode->next  = head;
            head->prior = newNode;
            newNode->prior = NULL;
        }

        printf("Please enter the value of node:\n");
        int val;
        if( scanf("%d",&val) != 1 )
        {
            fprintf( stderr, "scanf for node value failed\n" );
            // clean up here
            exit( EXIT_FAILURE );
        }

        newNode->value = val;
        head = newNode;
    }
    return head;
}


Node * merge_list( Node *left, Node *right )//合并两个非递减双向链表
{
    if( !left || !right)
        exit(-1);

    Node * workNode   = NULL;
    Node * returnNode = NULL;

    while ( left && right ) 
    {
        if( !workNode )
        { // then first loop
            if( left->value <= right->value )
            {
                workNode = left;
                left = left->next;
            }

            else
            {
                 workNode = right;
                 right = right->next;
            }

            // remember address of beginning of merged list
            returnNode = workNode;
        }


        else if( left->value <= right->value )
        {
            workNode->next  = left;
            left->prior = workNode;
            workNode = left;
            left = left->next;
        }

        else
        {
            workNode->next  = right;
            right->prior = workNode;
            workNode = right;
            right = right->next;
        }
    }

    // if more entries in left
    if( left )
    {
        workNode->next = left;
    }

    else if( right )
    {
        workNode->next = right;
    }
    return returnNode;
}


void delete_List( Node *list )
{
    if(list==NULL)
    {
        printf("List is empty!");
        exit(-1);
    }

    Node * temp;

    while(list)
    {
        temp = list->next;
        free( list );
        list = temp;
    }
}

Freeing double linked list I created

3 Answers3