patterncMinor
Data Structures in C (Single Linked List)
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
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
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:
Similarly, in a general case the
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.