Linked list implementation in c without using double-pointer

Question

I have implemented a simple linked list in C language, but can it be implemented without using double-pointer(**).I want to implement same program by using only single pointers.

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

struct node
{
  int data;
  struct node *next;
};


void push(struct node** head_ref, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data  = new_data;
    new_node->next = (*head_ref);
    (*head_ref)    = new_node;
}



void append(struct node** head_ref, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    struct node *last = *head_ref;  /* used in step 5*/
    new_node->data  = new_data;
    new_node->next = NULL;
    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
    return;
}

void printList(struct node *node)
{
  while (node != NULL)
  {
     printf(" %d ", node->data);
     node = node->next;
  }
}
int main()
{
  struct node* head = NULL;
  append(&head, 6);
  push(&head, 7);
  push(&head, 1);
  append(&head, 4);
  printf("\n Created Linked list is: ");
  printList(head);
  getchar();
  return 0;
}

Is it possible to replace "struct node** head_ref" with "struct node* head_ref"?

Changed code after suggestions(still not getting output)

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

struct node
{
  int data;
  struct node *next;
};


struct node* push(struct node* head, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data  = new_data;
    new_node->next = head;
    head   = new_node;
    return head;
}

struct node* append(struct node* head, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    struct node *last = head;  /* used in step 5*/
    new_node->data  = new_data;
    new_node->next = NULL;
    if (head == NULL)
    {
       head = new_node;
       return head;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
    return head;
}


void printList(struct node *node)
{
  while (node != NULL)
  {
     printf(" %d ", node->data);
     node = node->next;
  }
}

int main()
{
  struct node* head = NULL;
  head= append(&head, 6);
  head=push(&head, 7);
  head=push(&head, 1);
  head=append(&head, 4);
  printf("\n Created Linked list is: ");
  printList(head);
  getchar();
  return 0;
}

If you use your function result for something besides void, sure. — WhozCraig
– WhozCraig, Commented Jun 23, 2015 at 18:39
Sure - return the head as a function result instead of all those voids — Martin James
– Martin James, Commented Jun 23, 2015 at 18:40

Sergey Kalinichenko · Accepted Answer · 2015-06-23 18:41:13Z

3

Yes, you can rewrite this code using only single pointers, but you would have to change the semantic of your API and the pattern in which it is used.

Essentially, you replace the second level of indirection in

void push(struct node** head_ref, int new_data)

with a client-side assignment, i.e.

struct node* push(struct node* head, int new_data)

This means that instead of

push(&head, num);

the caller will have to write

head = push(head, num);

Same goes for the implementation of append.

answered Jun 23, 2015 at 18:41

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

dexter Over a year ago

will i have to make head as a global

dexter Over a year ago

what about printList fuction?

Sergey Kalinichenko Over a year ago

@dexter printList has a single asterisk, because it reads the list, never writes it. You do not have to make head global - you would be passing it to the function in the same way, without the & operator, and assign the result back to head. Both APIs let you create as many lists as you'd like.

dexter Over a year ago

i have made all changes as u told, and my code is comiped fine but i am not getting any output

Martin James Over a year ago

@dexter - OK, time to get out your debugger.

|

Deepak · Accepted Answer · 2015-06-23 19:07:52Z

2

Replace (&head,6) with (head,6).As you are not passing the address of the head, on receiving end you have push(struct node* head, int new_data).Rest all have been clarified by above given answer

answered Jun 23, 2015 at 19:07

Deepak

2872 silver badges18 bronze badges

Comments

user3386109 · Accepted Answer · 2015-06-23 19:10:11Z

Another solution is to create an empty node called head, and then create a pointer to that node called list. You can then pass list to all of the functions, like this

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

struct node
{
    int data;
    struct node *next;
};

void push(struct node *list, int new_data)
{
    struct node* new_node = malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = list->next;
    list->next = new_node;
}

void append(struct node *list, int new_data)
{
    while ( list->next != NULL ) 
        list = list->next;
    push( list, new_data );
}

void printList(struct node *node)
{
    for ( node=node->next; node != NULL; node=node->next )
        printf(" %d ", node->data);
    printf( "\n" );
}

int main( void )
{
    struct node head = { 0, NULL };
    struct node *list = &head;

    append(list, 6);
    push(list, 7);
    push(list, 1);
    append(list, 4);
    printf("\n Created Linked list is: ");
    printList(list);
    getchar();
    return 0;
}

Collectives™ on Stack Overflow

Linked list implementation in c without using double-pointer

Changed code after suggestions(still not getting output)

3 Answers 3

7 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Changed code after suggestions(still not getting output)

3 Answers 3

7 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related