Linked List Implementation in C

Question

I am new to Linked LIsts and I am trying to implement a Linked List in C . Below in my code :-

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

struct node {
    int data;
    struct node *next;
};
void insert (struct node *head, int data);
void  print  (struct node *head);
int main()
{
    struct node *head ;
    head= NULL;
    printf("new\n");
    insert(head,5);
    printf("%d\n",head);
    insert(head,4);
    insert(head,6);
    print(head);
    print(head);
    print(head);


} 
void  insert(struct node *head,int data){

    printf("%d\n",head);
    if(head == NULL){
        head =malloc(sizeof(struct node));
        head->next = NULL;
        head->data = data;

    }
    else {
        printf("entered else\n");
        struct node *tmp = head;
        if(tmp->next!=NULL){
            tmp = tmp->next;
        }
        tmp->next  = malloc(sizeof(struct node));
        tmp->next->next = NULL;
        tmp->next->data = data;

    }

}


void print (struct node *head) {
    printf("%d\n",head);
    struct node *tmp = head;
    if (head == NULL) {
        printf("entered null\n");
        return;
    }
    while (tmp != NULL) {
        if (tmp->next == NULL) {
            printf("%0d", tmp->data);
        } else {
            printf("%0d -> ", tmp->data);
        }
        tmp = tmp->next;
    }
    printf("\n");
}

When I run this code the output is :-

new
0
0
0
0
0
entered null
0
entered null
0
entered null

The head is always null and it doesnt update the null . It doesnt enter into the else loop in insert . Can anyone help me fix this please . Point out the mistake I am doing . thanks

There must be a jillion linked list in C tutorials on the web. Why not start with one of those and then modify it to suit your requirements? One of the top hits on Google is cprogramming.com/tutorial/c/lesson15.html — David Grayson
– David Grayson, Commented Sep 11, 2014 at 6:33

juanchopanza · Accepted Answer · 2014-09-11 07:39:13Z

6

There may be other errors in your code, but one big issue is that you are attempting to set a head node in insert, but that only affects a local copy of the pointer passed in, so it has no effect in the caller side:

void  insert(struct node *head,int data){
  ....
  head = malloc(sizeof(struct node)); // head is local, caller won't see this

You also need to ensure that when you pass a node that is not NULL, you actually attatch the new node to the head. You can fix the first problem by passing a pointer to a pointer, or by returning the set pointer. For example,

void insert(struct node **head, int data) {
  if(*head == NULL) {
    // create the head node
    ...
    *head = malloc(sizeof(struct node)); 
    ....
  else {
    // create a new node and attach it to the head
    struct node* tmp = malloc(sizeof(struct node));
    ....
    (*head)->next = tmp;
  }
}

Then, in main, you need to pass a pointer to the head pointer, i.e. use the address-of operator &:

struct node *head = NULL;
insert(&head, 5);

Note part of the problem is that the function is trying to do too much. It is called insert, but it attempts to create a new node if the pointer passed in is NULL. It would be better to separate these responsibilities:

// allocate a node and set its data field
struct node* create_node(int  data)
{
  struct node* n = malloc(sizeof(struct node));
  n->next = NULL;
  n->data = data;
  return n;
}

// create a node and add to end node.
// return the new end node.
// end has to point to a valid node object.
struct node* append_node(struct node* tail, int node_data)
{
  struct node* new_tail = create_node(node_data);
  tail->next = new_tail;
  return new_tail;
}

edited Sep 11, 2014 at 7:39

answered Sep 11, 2014 at 6:37

juanchopanza

228k35 gold badges421 silver badges493 bronze badges

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

4 Comments

Newbie Over a year ago

Why are you doing (*head)->next = tmp ?

juanchopanza Over a year ago

@Newbie Because in that example head is a pointer to a pointer. So *head gives me access to the pointer, and (*head)-> gives access to the element of the object pointed at by the pointer. But I prefer the division of responsibilities approach I suggest in the note.

Newbie Over a year ago

And one more thing , we will have to pass insert(&head,5).Why do we have to pass &head?

juanchopanza Over a year ago

@Newbie Yes, I will add that.

ani627 · Accepted Answer · 2014-09-11 06:54:10Z

I have fixed your insert function:

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

struct node {
    int data;
    struct node *next;
};
#define CREATENODE malloc(sizeof(struct node))
void insert (struct node *head, int data);
void  print  (struct node *head);
int main()
{
    struct node *head ;
    head = CREATENODE;
    printf("new\n");
    insert(head,5);
    insert(head,4);
    insert(head,6);
    print(head);
    print(head);
    print(head);


} 
void  insert(struct node *head,int data){
    struct node *temp, *nn;
    for(temp=head;temp->next!=NULL;temp=temp->next);
    nn=CREATENODE;
    nn->data = data;
    nn->next =temp->next;
    temp->next = nn;
}


void print (struct node *head) {
    struct node *tmp = head->next;
    if (head == NULL) {
        printf("entered null\n");
        return;
    }
    while (tmp != NULL) {
        if (tmp->next == NULL) {
            printf("%0d", tmp->data);
        } else {
            printf("%0d -> ", tmp->data);
        }
        tmp = tmp->next;
    }
    printf("\n");
}

André Slabber · Accepted Answer · 2014-09-11 06:40:39Z

-2

void insert(struct node &head,int data){ // pass reference rather than pointer ^ You passed a pointer, but that will only allow you to change the data it is pointing to. In order to change the pointer itself, you have to pass a reference. Not sure my C isn't a bit rusty, but I'm just pointing you in the right direction....

Regards,

André

answered Sep 11, 2014 at 6:40

André Slabber

11 bronze badge

2 Comments

LoPiTaL Over a year ago

In C, the refrences don't exist. Only pointers. He should use pointer to pointer, or return a pointer from the function. References just don't exist.

André Slabber Over a year ago

Sorry yes, you are correct. But from the sample given I couldn't discern whether the asker was using either C or C++, and it was a while since I last used C.

Collectives™ on Stack Overflow

Linked List Implementation in C

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related