singly linked linked list C reverse data reading

Question

I have a linked list which I am trying to read in reverse, however I'm having problems with doing so.

This is my struct.

typedef struct node{
    int x;
    struct  node *next;
}node;

The problem is with my reading function. This is the function:

void read(){
    node *iter;
    while(r->next!=NULL){
        iter=r;
        while(iter->next!=NULL) iter=iter->next;
        printf("%d",iter->x);
        free(iter);
    }
    printf("%d",r->x);
}

I iterate to the end of the list, I then read the data and delete it afterwards. And looping it. But it's not working. Could anyone please explain to me what I'm doing wrong? Also output of the program is:

* Error in `./final': double free or corruption (fasttop): 0x00000000022e24a0 * ======= Backtrace: ========= /lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7faccbe7b7e5] /lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7faccbe8437a] /lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7faccbe8853c] ./final[0x400942] ./final[0x400a06] /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7faccbe24830] ./final[0x4006b9] ======= Memory map: ======== 00400000-00401000 r-xp 00000000 08:01 8257622 /home/r4g3/Desktop/2U/final 00600000-00601000 r--p 00000000 08:01 8257622
/home/r4g3/Desktop/2U/final 00601000-00602000 rw-p 00001000 08:01 8257622 /home/r4g3/Desktop/2U/final 022d0000-02302000 rw-p 00000000 00:00 0
[heap] 7facc4000000-7facc4021000 rw-p 00000000 00:00 0 7facc4021000-7facc8000000 ---p 00000000 00:00 0 7faccb8e5000-7faccb8fb000 r-xp 00000000 08:01 39326162
/lib/x86_64-linux-gnu/libgcc_s.so.1 7faccb8fb000-7faccbafa000 ---p 00016000 08:01 39326162
/lib/x86_64-linux-gnu/libgcc_s.so.1 7faccbafa000-7faccbafb000 rw-p 00015000 08:01 39326162
/lib/x86_64-linux-gnu/libgcc_s.so.1 7faccbafb000-7faccbc03000 r-xp 00000000 08:01 39321605
/lib/x86_64-linux-gnu/libm-2.23.so 7faccbc03000-7faccbe02000 ---p 00108000 08:01 39321605
/lib/x86_64-linux-gnu/libm-2.23.so 7faccbe02000-7faccbe03000 r--p 00107000 08:01 39321605
/lib/x86_64-linux-gnu/libm-2.23.so 7faccbe03000-7faccbe04000 rw-p 00108000 08:01 39321605
/lib/x86_64-linux-gnu/libm-2.23.so 7faccbe04000-7faccbfc4000 r-xp 00000000 08:01 39321685
/lib/x86_64-linux-gnu/libc-2.23.so 7faccbfc4000-7faccc1c4000 ---p 001c0000 08:01 39321685
/lib/x86_64-linux-gnu/libc-2.23.so 7faccc1c4000-7faccc1c8000 r--p 001c0000 08:01 39321685
/lib/x86_64-linux-gnu/libc-2.23.so 7faccc1c8000-7faccc1ca000 rw-p 001c4000 08:01 39321685
/lib/x86_64-linux-gnu/libc-2.23.so 7faccc1ca000-7faccc1ce000 rw-p 00000000 00:00 0 7faccc1ce000-7faccc340000 r-xp 00000000 08:01 13631793
/usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21 7faccc340000-7faccc540000 ---p 00172000 08:01 13631793
/usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21 7faccc540000-7faccc54a000 r--p 00172000 08:01 13631793
/usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21 7faccc54a000-7faccc54c000 rw-p 0017c000 08:01 13631793
/usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21 7faccc54c000-7faccc550000 rw-p 00000000 00:00 0 7faccc550000-7faccc576000 r-xp 00000000 08:01 39321617
/lib/x86_64-linux-gnu/ld-2.23.so 7faccc74f000-7faccc755000 rw-p 00000000 00:00 0 7faccc774000-7faccc775000 rw-p 00000000 00:00 0 7faccc775000-7faccc776000 r--p 00025000 08:01 39321617
/lib/x86_64-linux-gnu/ld-2.23.so 7faccc776000-7faccc777000 rw-p 00026000 08:01 39321617
/lib/x86_64-linux-gnu/ld-2.23.so 7faccc777000-7faccc778000 rw-p 00000000 00:00 0 7ffd85b05000-7ffd85b26000 rw-p 00000000 00:00 0
[stack] 7ffd85b97000-7ffd85b9a000 r--p 00000000 00:00 0
[vvar] 7ffd85b9a000-7ffd85b9c000 r-xp 00000000 00:00 0
[vdso] ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0
[vsyscall] 10Aborted

P.S: "r" is my global root variable

Answer 1

After freeing the node set its previous node next pointer pointing to it to NULL. So, if you are doing:

 free(iter);

The previous node next pointer pointing to iter should be set to NULL.
The free() function does not change the value of the pointer itself, hence the previous node next pointer is still pointing to the same (now invalid) location.

The loop:

while(iter->next!=NULL)

is checking for NULL and it does not find the next pointer NULL and your program ends up freeing the memory already freed in the last iteration of outer while loop if. Hence you are getting the double free error.

To resolve this double free problem, keep track of the previous node of the node you are freeing and after calling free() set the previous node next pointer to NULL. Something like this:

    node *prev = NULL;
    while(iter->next!=NULL) { 
         prev = iter;
         iter = iter->next;
    }
    printf("%d", iter->x);
    free(iter);
    if (prev)
        prev->next = NULL;

Answer 2

you can use recursive function like

    void read(node* p){
       if(p->next != NULL)
           read(p->next);
       printf("%d ", p->x);
    }

This will reach to the end of linked list first and display the values from last to first. It wont free up memory but your issue will be resolve to print linked list in reverse order.

Answer 3

As @Sahyog Vishwakarma has already answered, a simple recursive print function that repeatedly calls itself while the node is not NULL is a clever way to reverse-print your linked list. Since I had already done a short example, I'll provide it as well for whatever additional benefit you may find in it.

The example simply uses a static array of nodes to create the list and a short print function, e.g.

#include <stdio.h>

#define NNODES 5

typedef struct node {
    int x;
    struct  node *next;
} node;

/* simple recursive function to print list in reverse */
void prn (node *l)
{
    if (l) {                    /* if not NULL */
        if (l->next)            /* if next not NULL */
            prn (l->next);      /* call prn (next node) */
        printf (" %d", l->x);   /* print values on way out */
    }       
}

int main (void) {
    /* short example with static array of nodes */
    node a[NNODES] = {{ .x = 0, .next = NULL }};

    /* initialize the linked list */
    for (int i = 0; i < NNODES; i++) {
        a[i].x = i + 1;
        if (i < NNODES - 1)
            a[i].next = &a[i+1];
    }
    prn (a);          /* reverse-print the list */
    putchar ('\n');   /* tidy up with a newline */
    return 0;
}

The node->x values are filled with 1 - 5 and on calling the prn are printed in reverse order.

Example Use/Output

$ ./bin/prnrecrev
 5 4 3 2 1

(note: each recursive call requires its own function-stack be created, so as your list grows, your function call overhead grows with it when using recursive functions. As a general rule of thumb if you have the option between an iterative solution or a procedural solution, you are better off picking the procedural one -- not always, but generally)

Answer 4

You probably want this:

void read() {
  node *iter;
  while (r->next != NULL) {
    iter = r;    
    node *current = NULL;
    while (iter->next != NULL) {
      current = iter;
      iter = iter->next;
    }

    printf("%d ", iter->x);
    current->next = NULL;
    free(iter);
  }

  if (r != NULL)
  {
    printf("%d ", r->x);
    free(r);
    r = NULL;
  }
}

The read function prints the whole list from the back deleting the whole list. Apparenty that's what your original code tries (and fails) to do.

This is of course very inefficient, because you need to find the end of the end of the list over and over again, but with a singly linked list you have no choice.

BTW: having a global variable r is poor design, and choosing a name like r is a bad idea, I'd call it for example listHead.

Answer 5

I just realized that you are new to data structure and probably not so familiar to recursion. Therefore I decided to write a small program which might help you to understand link list and reverse it without a recursion. Please let me know if you need more information in the area if that is not so clear to you.

typedef struct node{
    int x;
    struct  node *next;
}node;

void createList(node *h, int length)
{
   int c = 0;
   node *temp = h;
   while(c < length)
   {
     temp->next = (node *)malloc(sizeof(node));
     temp = temp->next;
         temp->x = ++c;
         temp->next = NULL;
   }
}

void PrintList(node *h) //print all the nodes
{
    while (h != NULL)
    {
       printf("%d\n", h->x);
       h = h->next;
     }
 }

node * reverseList(node *h)
{
  node *p, *q, *l;
  p = h;
  q = p->next;
  l = q->next;
  p->next = NULL;
  while(l != NULL)
  {
    q->next = p;
    p = q;
    q = l;
    l = l->next;
  }
   q->next = p;
   return q;
}

void deleteList(node *h)
{
   node *t = h;
   h = h->next;
   free(t);
   while(h != NULL)
   {
     t = h;
         h = h->next;
     free(t);
   }
}

 int main(void)
 {
   node *head = (node *)malloc(sizeof(node));
   head->x = 0;
   head->next = NULL;
   createList(head,10);//create a list with another 10 node total 11
   PrintList(head);
   printf("Now we are reversing the list\n");
   head = reverseList(head);
   PrintList(head);
   deleteList(head);//finally delete the list
       head = NULL;
       return 0;
 }