HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Data Structures in C (Single Linked List)

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
linkedsinglelistdatastructures

Problem

NOTE: Added a follow-up question with the reviewed code

I am trying to get back to basics with C, so I am doing some data structures in it.

The following is my implementation of a Single Linked List (The code is on github with tests).


LinkedList.h

/* 
 * File:   LinkedList.h
 * Author: antoniocs
 *
 * Created on 26 de Setembro de 2015, 19:54
 */

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct LinkedList LinkedList;
    typedef struct LinkedListNode LinkedListNode;

    struct LinkedList {
        LinkedListNode *head;
        LinkedListNode *tail;
    };

    struct LinkedListNode {
        void *data;
        LinkedListNode *next;
    };

    LinkedList *LLInit();

    LinkedListNode *LLAddHead(LinkedList *, void *);
    LinkedListNode *LLAddTail(LinkedList *, void *);
    LinkedListNode *LLAdd(LinkedList *, void *);

    void *LLRemoveHead(LinkedList *);
    void *LLRemoveTail(LinkedList *);
    void *LLRemoveNode(LinkedList *, LinkedListNode *);

    typedef int (*LLFindCompareFuncPtr)(void *, void *);    
    LinkedListNode *LLFindNodeByData(LinkedList *, void *, LLFindCompareFuncPtr);
    LinkedListNode *LLFindNodeByNext(LinkedList *, LinkedListNode *);

#ifdef  __cplusplus
}
#endif

#endif  /* LINKEDLIST_H */



LinkedList.c

```
#include
#include
#include
#include "LinkedList.h"
#include "../../../dbg.h"

enum LLAddStrategy {
HEAD,
TAIL
};

struct LLFindNodeBaseParams {
LinkedList *ll;

void *data;
LLFindCompareFuncPtr compareFunc;

LinkedListNode *node;
LinkedListNode *next;
};

struct FindResult {
LinkedListNode *prev;
LinkedListNode *node;
};

static struct FindResult FindNodeBase(struct LLFindNodeBaseParams );

typedef bool(findByFuncPtr)(struct LLFindNodeBaseParams , struct FindResult , LinkedListNode );
static bool FindByData(struct LLFindNodeBaseParams , struct FindResult , LinkedListNode *);
//To the outside this function is not reall

Solution

When removing a head node:

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


ll->head becomes ll->head->next regardless of its NULLness. Code could be streamlined:

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


Similarly, in a general case the res->prev->next is also well-defined:

} else {
    res->prev->next = node->next;
    if (node == ll->tail) {
        ll->tail = res->prev;
    }
}

Code Snippets

if (node == ll->head) {
    if (ll->head->next == NULL) {
        ll->head = ll->tail = NULL;
    } else {
        ll->head = ll->head->next;
    }
if (node == ll->head) {
    ll->head = ll->head->next;
    if (ll->head == NULL) {
        ll->tail = NULL;
    }
} else {
    res->prev->next = node->next;
    if (node == ll->tail) {
        ll->tail = res->prev;
    }
}

Context

StackExchange Code Review Q#107497, answer score: 2

Revisions (0)

No revisions yet.