2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Use \\ instead of \ in your path \$\endgroup\$ – David Ranieri Sep 7 '16 at 13:47
  • \$\begingroup\$ whats with the define and undef of DEBUG? \$\endgroup\$ – pm100 Sep 7 '16 at 17:53
  • \$\begingroup\$ it was done for debugging purposes \$\endgroup\$ – Oleg Nykolyn Sep 7 '16 at 19:10
  • \$\begingroup\$ Since you've already done a follow up to this question, could you please accept one of the answers here. \$\endgroup\$ – pacmaninbw Sep 10 '16 at 12:39
2
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ thanks for pointing out some of these errors, I'll fix them as fast as possible. \$\endgroup\$ – Oleg Nykolyn Sep 7 '16 at 18:18
1
\$\begingroup\$

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) { … }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.