Implementation of a singly linked list data structure in C

Question

This is a follow-up to the previous question located at Singly linked list implementation in pure C Any suggestions on design and optimization are highly appreciated

LINKEDLIST.H

#ifndef NYO_LINKED_LIST
#define NYO_LINKED_LIST

#include "stdbool.h"
#include "stdio.h"
#include "stdlib.h"

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

typedef struct LinkedList {
    Node *head, *tail;
    int length;
} LinkedList;

void LinkedList_Swap(int*,int*);
void LinkedList_Init(LinkedList*);
void LinkedList_Add(LinkedList*, Node*);
Node* createNode(int);
void LinkedList_Show(LinkedList*);
void LinkedList_PushFront(LinkedList*, Node*);
int LinkedList_GetDataAt(LinkedList*,int);
Node *getNode(LinkedList*,int);
void LinkedList_DeleteLast(LinkedList*);
bool LinkedList_Found(LinkedList*,int);
void LinkedList_Reverse(LinkedList*);
void LinkedList_Clear(LinkedList*);
void LinkedList_InsertAt(LinkedList*,int,int);
void LinkedList_DeleteAt(LinkedList*,int);
void LinkedList_Free(LinkedList*);

#endif

LINKEDLIST.c

#include "C:\Users\___\Desktop\workspace\linkedList.h"
#define DEBUG
#undef DEBUG

void LinkedList_Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void LinkedList_Init(LinkedList *list)
{
    list->head = NULL;
    list->tail = list->head;
    list->length = 0;
}

void LinkedList_Add(LinkedList *list, Node* node)
{
    if(list->head!=NULL)
    {
        list->tail->next = (struct Node*)node;
        list->tail = node;
    }
    else
    {
        list->head = node;
        list->tail = list->head;
    }
    ++list->length;
}

Node* createNode(int data)
{
    Node *tmp = (Node*)malloc(sizeof(Node));
    tmp->data = data;
    tmp->next = NULL;
    return tmp;
}

void LinkedList_Show(LinkedList *list)
{
    Node *tmp = list->head;
    while(tmp != NULL)
    {
        printf("[%d]\n",tmp->data);
        tmp = (Node*)tmp->next;
    }

}

void LinkedList_PushFront(LinkedList *list, Node* node)
{
    node->next = (struct Node*)list->head;
    if(list->head!=NULL)
    {
        list->head = node;
    }
    else
    {

        list->head = node;
        list->tail = list->head;
    }
    ++list->length;
}
int LinkedList_GetDataAt(LinkedList *list, int index)
{
    Node *tmp = list->head;
    int count = 0;
    if(index >= 0 && index < list->length)
    {
        while(tmp!=NULL)
        {
            if(count == index) return tmp->data;
            ++count;
            tmp = (Node*)tmp->next;
        }
    }
    return 0;
}

Node *getNode(LinkedList *list, int index)
{

    Node *tmp = list->head;
    int count = 0;
    if(index >= 0 && index < list->length)
    {
        while(tmp!=NULL)
        {
            if(count == index) return tmp;
            ++count;
            tmp = (Node*)tmp->next;
        }
    }
    return NULL;
}

void LinkedList_DeleteLast(LinkedList *list)
{

    Node *tmp = list->head;
    int i;
    Node *beforeLast;
    if(list->length>0)
    {
        for (i = 0; i < list->length; ++i)
        {

            if(i == list->length-2)
            {
                beforeLast = tmp;

            }
            if(tmp!=NULL)
            {
                tmp =(Node*) tmp->next;
            }


        }

        free(beforeLast->next);
        beforeLast->next = NULL;
        list->tail = beforeLast;
    }
    else
    {
        free(list->head);
        LinkedList_Init(list);
    }
    if(list->length>0)
    {
        --list->length;
    }
#ifdef DEBUG
    printf("Actual length -> [%d]\n",list->length);
#endif 
}

bool LinkedList_Found(LinkedList *list, int toFind)
{
    Node *tmp = list->head;
    while(tmp!=NULL)
    {
        if(toFind==tmp->data) return true;
        tmp = (Node*)tmp->next;
    }
    return false;
}
void LinkedList_Reverse(LinkedList *list)
{
    int len, i;
    for (i = 0, len = list->length-1; i < len; ++i, --len)
    {
        LinkedList_Swap((int*)getNode(list,i), (int*)getNode(list,len));
    }

}

void LinkedList_InsertAt(LinkedList *list, int index, int data)
{

    Node *tmp = list->head;
    Node *newNode = createNode(data);
    Node *left, *right;
    int count = 0;

    if(index == 0)  LinkedList_PushFront(list,createNode(data));

    else if (index == list->length-1) LinkedList_Add(list,createNode(data));

    else if(index > 0 && index < list->length)
    {
        {
            while(tmp!=NULL)
            {
                left = tmp;
                right = tmp->next;
                if(count == index - 1)
                {
                    left->next = newNode;
                    newNode->next = right;
                    ++list->length;
                    break;

                }
                ++count;
                tmp = (Node*)tmp->next;
            }

        }

    }
}

void LinkedList_DeleteAt(LinkedList *list, int index)
{

    Node *left, *right;
    Node *tmp = list->head;
    int count = 0;
    if(index > 0 && index < list->length-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->length;

    }
    else if (index == list->length-1)
    {
        LinkedList_DeleteLast(list);
    }
    else
    {

        list->head = list->head->next;
        free(tmp);
        tmp = NULL;
    }
}
void LinkedList_Free(LinkedList *list){
    free(list);
    list = NULL;
}


void LinkedList_Clear(LinkedList *list)
{
    while(list->head!=NULL)
    {
        LinkedList_DeleteAt(list,0);
    }
}

MAIN.C

#include "C:\Users\___\Desktop\workspace\linkedList.h"

int main(int argc, char const *argv[])
{

    LinkedList *list = (LinkedList*)malloc(sizeof(LinkedList));

    LinkedList_Init(list);
    LinkedList_Add(list,createNode(1));
    LinkedList_Add(list,createNode(2));
    LinkedList_Add(list,createNode(3));
    LinkedList_Add(list,createNode(4));
    LinkedList_DeleteAt(list,1);
    LinkedList_Reverse(list);
    LinkedList_Show(list);
    LinkedList_Clear(list);

    LinkedList_Free(list);

    return 0;
}

Answer 1

• LinkedList_Add

  Regardless of the initial state of the list, the newly added node becomes tail:

  {
      if (list->head == NULL) {
          list->head = node;
      } else {
          tail->next = node;
      }
      list->tail = node;
  }
  

  Same applies to LinkedList_PushFront: the node becomes head no matter what.

  {
      node->next = list->head;
      list->head = node;
      if (node->next == 0) {
          list->tail = node;
      }
  }
  

• LinkedList_DeleteLast

  is overly complicated. Treat a special case first:

      if (list->head->next == 0) {
          delete head and return
      }
  
      Node * current = list->head;
      // At this point you know for sure that current->next is valid.
      while (current->next != list->tail) {
          current = current->next;
      }
      delete_tail()
      current->next = NULL;
      list->tail = current;
  

• LinkedList_Reverse

  has a quadratic time complexity (due to the linear complexity of getNode). Instead of swapping data, consider reversing links in a single linear pass:

  Node * prev = current;
  Node * current = list->head;
  while (current) {
      Node * next = current->next;
      current->next = prev;
      prev = current;
      current = next;
  } 
  

• __LinkedList_DeleteAt

  is buggy. First, if index > list->length, the final else is executed, removing a head. I don't think it is intended behaviour. Second, if the list has just one element (that is, becomes empty after deletion), list->tail is not adjusted and becomes a dangling pointer.

• Misc

  The cast in tmp = (Node*)tmp->next; is totally unnecessary.

  Use curly brackets consistently.

  Insert and delete better return bool to inform the user whether the action completed successfully (e.g. insertion happened) or not.

Answer 2

The function LinkedList_Swap should not be part of the API, since it doesn't take a parameter of type LinkedList.

The function LinkedList_Show should not be part of the API, since it is too specialized (it can only print to stdout).

The function createNode should be static, since it is only used in the same file.

The #include lines should not use absolute paths.

The function LinkedList_Found should be named Find, since all the other names are also in present tense.

Instead of a while loop, a for loop is more idiomatic, e.g.

for (Node *n = head; n != NULL; n = n->next) { … }