Correctly Implementing a Linked List in C

Question

I am trying to implement a linked list from scratch in C:

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

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

void insert(struct node** root, int data){ 

    // Create a Node

    struct node * temp = malloc(sizeof(struct node));
    temp->data = data;
    temp->next = NULL;

    // Either root is NULL or not

    if (*root == NULL){
        *root = temp; // Directly modify the root
    }

    else {
        struct node * t = *root;
        while (t->next!=NULL){
            t = t->next;
        }
        t->next = temp; // Append at the last
    }
}

void printList(struct node * root){

    while(root!=NULL){
        printf("%d\t", root->data);
    }

}

struct node * search(struct node* root, int key){

    while (root!=NULL) {
        if (root->data == key) return root;
    }

    return NULL;
}

int main(){

    struct node * head = NULL;

    insert(&head,0);
    insert(&head,1);
    insert(&head,2);
    insert(&head,3);
    insert(&head,4);

    printList(head);

}

Now, when I run the program, my output is:

0       0       0       0       0       0       0       0       0       0

However, my list doesn't contain all zeroes or 10 elements.

My logic seems correct but somehow code has a bug.

On a side note, is there a way to avoid double pointers, can't I work with only pointers while inserting in a linked list?

@user2079303 linked list is implemented similarly in c plus plus — mourinho
– mourinho, Commented Feb 19, 2018 at 14:10
while(root!=NULL){ root is never changed inside this print-loop. BTW: this is a good reason to prefer for() loops over while() loops. — joop
– joop, Commented Feb 19, 2018 at 14:10
My logic is correct but somehow code has a bug. That's not how it works. At a first glance, your printList function doesn't walk the list, but only prints root->data. — Ivaylo Valchev
– Ivaylo Valchev, Commented Feb 19, 2018 at 14:11
@mourinho in C the only way to avoid a double pointer is if insert returns the head pointer, e.h: struct node *insert(struct node* root, int data) ... — Jabberwocky
– Jabberwocky, Commented Feb 19, 2018 at 14:25

Achal · Accepted Answer · 2018-02-19 14:19:22Z

4

There is a small bug in the printList() function.

In printList() function, root not updated, to iterate whole list you should do root = root->next

void printList(struct node * root){

        while(root!=NULL){
                printf("%d\t", root->data);
                root = root->next; /* you miss this one */
        }

}

Same mistake is repeated in search() function also,

struct node * search(struct node* root, int key){
        while (root!=NULL) {
                if (root->data == key)
                        return root;
                else
                        root = root->next; /* if key not found root should be updated to next one */
        }
        return NULL;
}

edited Feb 19, 2018 at 14:19

answered Feb 19, 2018 at 14:11

Achal

11.9k2 gold badges18 silver badges39 bronze badges

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

Collectives™ on Stack Overflow

Correctly Implementing a Linked List in C

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related