Is there a generic linked list functionality for any structure
First, you separate the domain data of each entry from the managing data.
typedef struct {
char* name;
int food_id;
int price;
int capacity;
int hall_id;
int day;
int reserved;
int profit;
} Food;
typedef struct {
int id;
int percentage;
int capacity;
} Coupon;
Then you can use a union with pointers to the domain data in the entry's structure. Each entry will be of the same size.
typedef struct Entry {
struct Entry* next;
union {
Food* food;
Coupon* coupon;
} data;
} Entry;
You could even place the domain data directly in the union, but this will waste memory if only small sized values are stored.
typedef struct Entry {
struct Entry* next;
union {
Food food;
Coupon coupon;
} data;
} Entry;
Now you are able to add new entries of different data with a generic function.
void add_front(Entry* head, Entry* new_el) {
while (head->next != NULL){
head = head->next;
}
head->next = new_el;
new_el->next = NULL;
}
A possible trick is to use the fact that it is legal to convert a pointer to a struct to a pointer to its initial member, and that it is legal to convert from any pointer type to void * and back. So provided next
is the first member, a number of functions could be independant of the actual class, if they take void *
parameters for any struct for which the first element is a next
pointer. Of course, auxiliary function able to handle a real object should be provided...
Here is an example code showing a possible implementation of add_before
, add_after
, list_remove
(remove
is defined in stdio.h
) and display
and showing an example of use with Coupon
objects:
#include <stdio.h>
typedef struct Food {
struct Food* next;
char* name;
int food_id;
int price;
int capacity;
int hall_id;
int day;
int reserved;
int profit;
} Food;
typedef struct Coupon {
struct Coupon* next;
int id;
int percentage;
int capacity;
} Coupon;
void* add_before(void* list, void* elem) {
*(void **)elem = list;
return elem;
}
void* add_after(void* list, void* elem) {
if (NULL == list) return elem;
void** last = list;
while (*last != NULL) {
last = *last;
}
*last = elem;
return list;
}
// eltdisplay is a pointer to a function able to display an element
void display(void* list, void (*eltdisplay)(void*, FILE *), FILE *out) {
while (NULL != list) {
eltdisplay(list, out);
if (NULL != *(void **)list) {
fprintf(out, " -> ");
}
list = *(void **)list;
}
fprintf(out, "\n");
}
void* list_remove(void* list, void* elem, int(*comp)(void* elt1, void* elt2)) {
if (list == NULL) return NULL;
void** cur = list, **old = NULL;
while (cur != NULL) {
if (0 == comp(cur, elem)) {
if (old == NULL) return *cur;
*old = *cur;
break;
}
old = cur;
cur = *cur;
}
return list;
}
int couponcomp(void* elt1, void* elt2) {
return ((Coupon*)elt1)->id != ((Coupon*)elt2)->id;
}
void coupondisplay(void* elt, FILE *out) {
Coupon* coupon = elt;
fprintf(out, "%d", coupon->id);
}
int main() {
Coupon data[3] = { {NULL, 1}, {NULL, 2}, {NULL, 3} };
Coupon* list = NULL;
for (int i = 0; i < sizeof(data) / sizeof(*data); i++) {
list = addLast(list, data+i);
}
display(list, coupondisplay, stdout);
Coupon data2 = { NULL, 2 };
list = list_remove(list, &data2, couponcomp);
display(list, coupondisplay, stdout);
return 0;
}
It compiles with no warning and displays as expected:
1 -> 2 -> 3
1 -> 3
You could use a macro :
From one of my personal project
#if !defined(CIRCULAR_DOUBLE_LINKED_LIST_H)
#define CIRCULAR_DOUBLE_LINKED_LIST_H
//T must include ->prev and ->next member
#define DECLARE_NAMED_CIRCULAR_DOUBLE_LINKED_LIST(T, name) \
static inline T* name ## _add_after(T* source, T* item) { \
T* last_next = source->next; \
source->next = item; \
item->prev = source; \
item->next = last_next; \
last_next->prev = item; \
return source; \
} \
static inline T* name ## _add_before(T* source, T* item) {\
T* last_prev = source->prev; \
source->prev = item; \
item->next = source; \
item->prev = last_prev; \
last_prev->next = item; \
return source; \
} \
static inline T* name ## _remove(T* item) { \
T* next = item->next; \
item->prev->next = item->next; \
item->next->prev = item->prev; \
return next == item ? NULL : next; \
}
#define DECLARE_CIRCULAR_DOUBLE_LINKED_LIST(T) DECLARE_NAMED_CIRCULAR_DOUBLE_LINKED_LIST(T, list_ ## T)
#endif // CIRCULAR_DOUBLE_LINKED_LIST_H
typedef struct Food {
Food* next;
Food* prev;
char* name;
int food_id;
int price;
int capacity;
int hall_id;
int day;
int reserved;
int profit;
} Food;
DECLARE_CIRCULAR_DOUBLE_LINKED_LIST(Food)
list_Food_add_after(Food*, Food*);
list_Food_add_before(Food*, Food*);
list_Food_remove(Food*);
I think the best way I ever found to do this in C (i.e., without templates) was:
- Make a
SinglyLinkedNode
class that just hasSinglyLinkedNode *next
- Write your list functions based on this class -- every list is a list of
SinglyLinkedNode
- Add
SinglyLinkedNode node
fields toFood
andCoupon
, and use that to link them together. - Additionally provide functions or macros to get the containing
Food
orCoupon
pointer from aSinglyLinkedNode
pointer, likeCoupon *couponFromNode(Node *p);
Note that I would never actually do this for singly-linked lists, because singly-linked list operations are so easy to write that you don't really need list methods. This technique starts to get useful for doubly-linked lists or more complex introspective containers.