Linked list in C

Question

I'm trying to get into C, and I was wondering if I messed up regarding correctly implementing a linked list.

node.h

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

code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// struct for linked lists
#include "node.h"
bool searchLinked(node* list, int* value);
void insertLinked(node* list, int* value);
void initList(node* list);
void printList(node* list);
/*This small program shows how to utilize the data structure linked lists*/
/*and append, search and delete data in them*/
int main(int argc, char* argv[])
{
 // nodes
 node* root = malloc(sizeof(node));
 // initilize the list and add dummy values
 initList(root);
 // print the list
 printList(root); 
 // search the list for our value, if not found we try to add it
 int value = 1;
 if (!searchLinked(root, &value))
 {
 insertLinked(root, &value);
 }
 free(root);
 return 1;
}
void initList(node* list)
{
 list->n = 4;
 list->next = malloc (sizeof(node));
 // second node access
 list = list->next;
 list->n = 3;
 list->next = malloc (sizeof(node));
 // third node
 list = list->next;
 list->n = 2;
 // set this to NULL since this is last node
 list->next = NULL;
}
// method used to traverse and search our list
bool searchLinked(node* list, int* value)
{
 node* cond = malloc(sizeof(node));
 cond = list;
 while (cond != NULL)
 {
 if (cond->n == *value)
 { 
 free(cond);
 return true;
 }
 else
 {
 cond = cond->next;
 }
 }
 free(cond);
 return false; 
}
void printList (node* list)
{
 node* cond = malloc(sizeof(node));
 cond = list;
 for (int i = 0; cond != NULL; i++)
 {
 printf("The root no: %d has the data: %d\n", i, cond->n);
 cond = cond->next;
 }
 free(cond);
}
// this method is used when we want to append data to the last element in the list
// please note that if we were to add it to the start of the list then we would need to
// make sure that we dont drop the list by dissconnecting the 2nd member 
void insertLinked(node* list, int* value)
{
 node* cond = malloc(sizeof(node));
 cond = list;
 while (cond != NULL)
 {
 if (cond->next == NULL)
 {
 // assign the last node the adress of the new node
 cond->next = malloc(sizeof(node));
 // assign the last node to the newly new node
 cond = cond->next;
 // assign the values for the last (new) node
 cond->n = *value;
 cond->next = NULL;
 // try to access the next one, which should be null which will break the loop
 cond = cond->next; 
 }
 else
 {
 cond = cond->next;
 }
 }
free(cond);
}

• txtechhelp: There's a couple of issues to note with this code (which I'll address in an answer), and your insertLinked function actually just adds the node to the end of a heap variable that is destroyed. Did you mean to actually insert the nodes such that they are in sequential order (i.e. 1->2->3->..), or merely just insert them at the end if the value isn't found?
• flogram_dev: cond = list; in insertLinked leaks the node you allocated on the previous line. You probably meant *cond = *list;.

Answer 1

Extra mallocs

Neither search nor print should be allocating anything. You don't need to - you're just walking the list in both cases, without actually adding anything. You are careful to free correctly, but simply deleting all the allocation code would make the functions still work and be even better.

Example for print:

void printList (node* list)
{
 for (int i = 0; list != NULL; i++)
 {
 printf("The root no: %d has the data: %d\n", i, list->n);
 list = list->next;
 }
}

I would even move the list advancement into the loop statement itself, to make it clear which part is the "body":

 for (int i = 0; list != NULL; i++, list = list->next)
 {
 printf("The root no: %d has the data: %d\n", i, list->n);
 }

Leaking memory

At the end, you:

free(root);

But you don't free(root->next) or free(root->next->next), etc. You should add another function like deleteList() or freeList() that will free() every node in the list.

inserting

insertLinked should malloc - but just the one node that you're inserting, you don't need the top-level malloc there either. Since we're assuming that the list is non-empty, your logic would be better if you split up the insertion part from the looking-for-the-end part.

Also there is no reason to take the value by pointer:

void append(node* list, int value)
{
 while (list->next != NULL) {
 list = list->next;
 }
 // now, list is pointing to the last element, so we just 
 // add a new one
 list->next = malloc(sizeof(node));
 list->next->n = value;
 list->next->next = NULL;
}

Answer 2

Here are some things that may help you improve your code.

Check the return value of malloc

If the program runs out of memory, a call to malloc can fail. The indication for this is that the call will return a NULL pointer. You should check for this and avoid dereferencing a NULL pointer (which typically causes a program crash).

Don't allocate memory needlessly

The printList routine shouldn't need to allocate memory since all it's supposed to do is iterate over an existing data structure.

void printList (const node* list)
{
 for (int i = 0; list != NULL; ++i, list = list->next) {
 printf("Node %d = %d\n", i, list->n);
 }
}

The searchLinked() routine can be rewritten similarly.

Use const where practical

As shown above, the printList routine shouldn't have any reason to modify the list, so this should be indicated and enforced by declaring that parameter const:

void printList (const node* list)

Use consistent naming

We have searchLinked() and insertLinked() but printList(). It would be easier to use the code if it had consistent naming.

Pass simple variables by value

Simple variables such as ints and char are usually better passed by value than by pointer. It's usually a little bit faster and uses fewer register and memory resources.

Clean up logic for node insertion

The logic for the insertLinked() is not at all clear and once again, the code is pointlessly allocating memory. Here's a cleaner version:

void appendList(node* list, int value)
{
 node* cond = malloc(sizeof(node));
 if (cond == NULL) {
 return; // out of memory
 }
 cond->n = value;
 cond->next = NULL;
 // advance to last node
 for (; list && list->next; list = list->next)
 {}
 list->next = cond;
}

Also, note that I've changed the name of the function to be more descriptive.

Don't leak memory

Right now the program leaks memory because the allocated data items in the list are never deleted. Fix this with a destroyList() function that would be called at the end.

Make the function match the function name

I'd expect a function called initList to initialize the list for use and nothing more, but that's not really what it does. I'd recommend simplifying it like this:

void initList(node* list)
{
 list->n = 0;
 list->next = NULL;
}

Use your functions

Now that the initList function does only that, within main, you can add dummy values by calling your function:

initList(root);
appendList(root, 4);
appendList(root, 3);
appendList(root, 2);

Return 0 except for error

Your program peculiarly ends with return 1 but a nonzero value is typically interpreted by the operating system as an error condition. For that reason, your code should return 0 except on error. However, since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.