Singly linked list implementation in pure C

Question

Is there a way to improve this code? Any suggestions are highly appreciated.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define DEBUG
#undef DEBUG
typedef struct Node
{
 int data;
 struct Node *next;
} Node;
typedef struct LinkedList {
 Node *head, *tail;
 int size;
} LinkedList;
LinkedList *list;
void swap(int *a, int *b)
{
 int tmp = *a;
 *a = *b;
 *b = tmp;
}
void init()
{
 list->head = NULL;
 list->tail = list->head;
 list->size = 0;
}
void add(Node* node)
{
 if(list->head!=NULL)
 {
 list->tail->next = (struct Node*)node;
 list->tail = node;
 }
 else
 {
 list->head = node;
 list->tail = list->head;
 }
 ++list->size;
}
Node* createNode(int data)
{
 Node *tmp = (Node*)malloc(sizeof(Node));
 tmp->data = data;
 tmp->next = NULL;
 return tmp;
}
void show()
{
 Node *tmp = list->head;
 while(tmp != NULL)
 {
 printf("%d\t",tmp->data);
 tmp = (Node*)tmp->next;
 }
 printf("\n");
}
void pushFront(Node* node)
{
 node->next = (struct Node*)list->head;
 if(list->head!=NULL)
 {
 list->head = node;
 }
 else
 {
 list->head = node;
 list->tail = list->head;
 }
 ++list->size;
}
int getDataAt(int index)
{
 Node *tmp = list->head;
 int count = 0;
 if(index >= 0 && index < list->size)
 {
 while(tmp!=NULL)
 {
 if(count == index) return tmp->data;
 ++count;
 tmp = (Node*)tmp->next;
 }
 }
 return 0;
}
Node *getNode(int index)
{
 Node *tmp = list->head;
 int count = 0;
 if(index >= 0 && index < list->size)
 {
 while(tmp!=NULL)
 {
 if(count == index) return tmp;
 ++count;
 tmp = (Node*)tmp->next;
 }
 }
 return NULL;
}
void deleteLast()
{
 Node *tmp = list->head;
 int i;
 Node *beforeLast;
 if(list->size>0)
 {
 for (i = 0; i < list->size; ++i)
 {
 if(i == list->size-2)
 {
 beforeLast = tmp;
 }
 if(tmp!=NULL)
 {
 tmp =(Node*) tmp->next;
 }
 }
 free(beforeLast->next);
 beforeLast->next = NULL;
 list->tail = beforeLast;
 }
 else
 {
 free(list->head);
 init();
 }
 if(list->size>0)
 {
 --list->size;
 }
#ifdef DEBUG
 printf("Actual size -> [%d]\n",size);
#endif // DEBUG
}
bool found(int toFind)
{
 Node *tmp = list->head;
 while(tmp!=NULL)
 {
 if(toFind==tmp->data) return true;
 tmp = (Node*)tmp->next;
 }
 return false;
}
void reverse()
{
 int len, i;
 for (i = 0, len = list->size-1; i < len; ++i, --len)
 {
 swap((int*)getNode(i), (int*)getNode(len));
 }
}
void clear()
{
 while(list->head!=NULL)
 {
 deleteLast();
 }
}
void insertAt(int index, int data)
{
 Node *tmp = list->head;
 Node *newNode = createNode(data);
 Node *left, *right;
 int count = 0;
 if(index == 0) pushFront(createNode(data));
 else if (index == list->size-1) add(createNode(data));
 else if(index > 0 && index < list->size)
 {
 {
 while(tmp!=NULL)
 {
 left = tmp;
 right = tmp->next;
 if(count == index - 1)
 {
 left->next = newNode;
 newNode->next = right;
 ++list->size;
 break;
 }
 ++count;
 tmp = (Node*)tmp->next;
 }
 }
 }
}
void deleteAt(int index)
{
 Node *left, *right;
 Node *tmp = list->head;
 int count = 0;
 if(index > 0 && index < list->size-1)
 {
 while(tmp!=NULL)
 {
 left = tmp;
 right = tmp->next;
 if(count == index-1)
 {
#ifdef DEBUG
 printf("left -> %d right -> %d\n", left->data, right->data);
#endif
 left->next = right->next;
 break;
 }
 ++count;
 tmp = tmp->next;
 }
 --list->size;
 }
 else if (index == list->size-1)
 {
 deleteLast();
 }
 else
 {
 list->head = list->head->next;
 free(tmp);
 tmp = NULL;
 }
}
int main(int argc, char const *argv[])
{
 list = (LinkedList*)malloc(sizeof(LinkedList));
 init();
 add(createNode(1));
 add(createNode(2));
 add(createNode(3));
 add(createNode(4));
 pushFront(createNode(5));
 deleteAt(1);
 reverse();
 show();
 clear();
 free(list);
 list = NULL;
 return 0;
}

Answer 1

Global list

The first issue that bothers me is the fact that you declared the list pointer as global. This leads to the fact that if another client programmer operates on your implementation, he interferes with exactly the same list as you do.

Instead, I suggest you go for the next design:

LinkedList my_list;
LinkedListInit(&my_list);
LinkedListAdd(&my_list, 1);
LinkedListAdd(&my_list, 2);
...
LinkedListAdd(&my_list, n);
LinkedListGet(&my_list, 2);
LinkedListRemove(&my_list, 2);
LinkedListFree(&my_list);
...

Compilation issue

In my Xcode, clear() triggers a compilation error message: "Conflicting types for 'clear'"

Library pattern

In case you have code that is worth using outside of your personal project, you could do the next:

1. Add the declarations to a header file; call it "funky_utils.h",
2. Add the implementation to a C file; call it "funky_utils.c",
3. Whenever your friend wants to reuse your code, he just #include "funky_utils.h"

Hope that helps.

• user116545: thanks for the suggestion on the design, however I don't get absolutely no error on clear(), I'm compiling on Linux
• coderodde: @OlegNykolyn I don't doubt that your compiler compiles your code, just letting you know that we might have a "portability" issue.

Answer 2

A couple of things stand out.

init

Since init doesn't take a parameter my assumption would have been that it would take care of initializing the global list. It doesn't, this has to be done first and init doesn't perform any checking to make sure that the global has been initialized / that init hasn't previously been called.

clear

You clear the list by repeatedly calling deleteLast. This means that you have to traverse the entire list, remove the last item and then repeat for each item in the list. It would be more efficient to remove from the head. With your existing interface, it looks like you could just call deletaAt(0).

• user116545: you are perfectly right, clear() this way is more efficient, thanks for pointing that out