Documentation for double linked list object (scl_dlist.h)
In the scl_dlist.h file you have two functions that helps you to create and delete a linked list.
dlist_t* create_dlist (compare_func cmp, free_func frd, size_t data_size);
void free_dlist (dlist_t * const __restrict__ list);create_dlist function will allocate a list on heap and will return a pointer to its location. However you should provide 2 function that are neccessary for maintaing the linked list.
typedef int (*compare_func)(const void * const elem1, const void * const elem2);
typedef void (*free_func)(void *data);
// Check scl_config.h for any function definitionsFunction will take 2 generic pointers and according to user needs will return:
1. 1 - if elem1 > elem2
2. -1 - if elem1 < elem2
3. 0 - if elem1 == elem2
Example of compare_data function for int data type:
int compare_data(const void * const elem1, const void * const elem2) {
const int * const fa = elem1;
const int * const fb = elem2;
return *fa - *fb;
}If you want to print the output in a file, you will have to use freopen on stdout stream to redirect it to another file, and then print your data as usual.
void print_data(void * const elem) {
printf("%d ", *(const int * const)elem);
// You also shall consider calling freopen function of stdout and to use just printf
// these is very good because you do not declare a FILE pointer globally
}free_data function is optional if you do not use dynamically data types. Every thing that you allocate on heap by yourself must be specified in free_data function.
If no free is needed that NULL should be passed in create_dlist function.
Exaple of type:
typedef struct {
char *name;
int *marks;
int GPA;
char first_letter;
double average;
} student;An example of free_data function for this structure should be:
void free_data(void *elem1) {
student *fa = elem1;
if (NULL != fa->name) {
free(fa->name);
}
fa->name = NULL;
if (NULL != fa->marks) {
free(fa->marks);
}
fa->marks = NULL;
}NOTE: If any proccess of
create_dlistfails than an error will be printed into the stderr will be thrown.
If you want to print the entire list than you should call dlist_traverse function.
NOTE: If list is not allocated than nothing will be printed. If list is empty that a set of square paired brackets will be printed [ ] and if list is not empty than every element from the list will be printed according to print_data function provided by the user.
The last function is for freeing memory from heap allocated for the list.
free_dlist will take a list as input and will free every element according to free_data function provided by user. If free_data function is NULL than content of one data will be not removed (because is allocated on stack not on the heap -- No memory leaks will be generated). Every pointer that is freed is also set to NULL pointer.
Example of creating a double linked list containing int data types:
dlist_t *list = create_dlist(&compare_int, NULL, sizeof(int));
dlist_traverse(list, &print_int);
free_dlist(list);In this section we will cover 7 functions dedicated for insertion and deletion from double linked list object.
Insertion in double linked list works just like insertion in vectors from C++.
There are 4 types of insertion:
- dlist_insert - inserts an element to the end of the list
- dlist_insert_front - inserts an element to the beginnign of the list
- dlist_insert_order - insers an element in order in list according to compare_data function rule
- dlist_insert_index - inserts an element to an index in the list
Let's assume that we works with integers and we would like to maintain a double linked list of integers, insertion would show like:
dlist_t *list = create_dlist(...);
int data = 0; // Dummy value not necessary
for (int i = 0; i < 10; ++i) {
scanf("%d", &data); // You could replace with fscanf
if (dlist_insert(list, toptr(data)) != SCL_OK) {
// Something went wrong
scl_error_message(err); // To print verbose explanation of the current error
}
}NOTE: If you will want to use the
toptrandltoptrmacros you will have to include scl_func_types.h. You can use istead the toptr and ltoptr their definition, but i find it more fancy to use them.
If you have dynamic elements in a structure and want to store the strucutre in the list you shouls do as follows:
typedef struct {
char *name;
int age;
} person;
int compare_person(const void * const data1, const void * const data2) {
const person * const f1 = data1;
const person * const f2 = data2;
return (f1->age - f2->age);
}
void free_person(void *data) {
if (NULL == data) {
return;
}
person *t_data = data;
if (NULL != t_data->name) {
free(t_data->name);
t_data->name = NULL;
}
}
....
dlist_t *list = create_dlist(&compare_person, &free_person, sizeof(person));
for (int i = 0; i < 10; ++i) {
char *name = malloc(SET_A_WORD_SIZE);
int age = 0;
scanf("%d", &age);
scanf("%s", name);
dlist_insert(list, ltoptr(person, { make_pair(.name = name, .age = age) })); // Returns a scl_error_t for you to check
}
// OR
for (int i = 0; i < 10; ++i) {
person pers;
pers.name = malloc(SET_A_WORD_SIZE);
pers.age = 0;
scanf("%d", pers.age);
scanf("%s", pers.name);
dlist_insert(list, toptr(pers)); // Returns a scl_error_t for you to check
}
// It is very important not to free manually pers.name
// This will be done in freeing the entire list
free_dlist(list); // Returns a scl_error_t but it is not so important as in insertion or deletion
// Will free every allocation made for list including data.nameNOTE: In this case if no free_data function is provided the program will result in memory leaks. If we change from
char *name, intochar name[SIZE_OF_A_WORD]then no free_data should be provided.
NOTE: dlist_insert_front, dlist_insert_order and dlist_insert_index works just like dlist_insert, but have different proprieties.
NOTE: in dlist_insert_index if provided index is greter or equal to list size than element will be inserted at the end of the list.
If you want to delete some elements from a list you have 3 choices:
- Delete element by data - provide a data for function to find and delete (dlist_delete_data)
- Delete element by index - provide an index for function to find and delete (dlist_delete_index)
- Delete a range of elements - provide a left and a right index for function to erase (dlist_erase)
Let's take the above example of insertion with integers and let remove some elements:
scl_error_t err = SCL_OK;
// By data
data = 4;
if ((err = dlist_delete_data(list, toptr(data))) != SCL_ERR)
scl_error_message(err);
// By index
if ((err = dlist_delete_index(list, 4)) != SCL_ERR)
scl_error_message(err);
// By range
if ((err = dlist_erase(list, 1, 3)) != SCL_ERR)
scl_error_message(err);;NOTE: It is a good practise to embrace an if statement around deletion elements but you can do same pattern when inserting an element in the list.
NOTE: for dlist_erase, you can provide different left and right index even in a random form. For example if you will pass left and right index out of bound then the last element will be removed, if left index is greater than right one, they both will be swapped.
I also provided two functions that can find and return pointers to nodes from list
- dlist_find_data - returns a pointer to first occurence of data node that contains data value
- dlist_find_index - returns a pointer to data node positioned at provided index in the list
NOTE: If no data node is found than NULL pointer will be returned
Example of using list finds:
// list = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
int data = 3;
// By data
const int *node1 = dlist_find_data(list, toptr(data));
// When changing the value of one data from list you shall not find it
// the function will by itself find data pointer and will modify it's value
// By index
const int *node2 = dlist_find_index(list, 4);
// Now you cand do stuff with nodes for example swap them You easily can modify a value of a node data, but you CANNOT change it's data type.
If you try to change data between typed that have different size you can encounter a memory leak even a segmentation fault. If types have the same size that program may result into an unknown behavior.
Two functions that change data of nodes are:
- dlist_change_data - changes data of a node with another value
- dlist_swap_data - interchanges data from two valid nodes
Example of changing and swapping two data:
// list = 1 -> 2 -> 3 -> 4 -> 5
const int * node1 = dlist_find_index(list, 0);
const int * node2 = dlist_find_index(list, list->size - 1);
dlist_swap_data(list, node1, node2); // Also returns a scl_error_t
dlist_change_data(list, node1, ltoptr(int, 20)); // Also returns a scl_error_t
// In this case we didn't know the values in the list but if we know
// that list[0] = 4 and list[list->size - 1] = 7; we could do
// dlist_swap_data(list, ltoptr(int, 4), ltoptr(int, 7));
// Same applies to change data function
// list = 20 -> 2 -> 3 -> 4 -> 5Two important functions provided in scl_dlist.h are:
- Filter function - creates a new list and selects some elements based of filter rule
- Map function / Action function - modifies in-place the current list by mapping every element into a new element of the same type
NOTE: Filter function must return 1 for true and 0 for false. When true, element is added in the new list.
Examples of list filter and mapping
int filter(const void * const elem) {
const int * const fa = elem;
if (1 == *fa) return 1;
return 0;
}
void map(void * const elem) {
int * const fa = elem;
*fa = (*fa) % 2;
}
...
// list = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
dlist_traverse(list, &map); // Check here for SCL_OK
// list = 1 -> 0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 0
dlist_t *new_list = dlist_filter(list, &filter);
// newList = 1 -> 1 -> 1 -> 1 -> 1 -> NULL
printf("We have %lu odd numbers\n", get_dlist_size(new_list));
// Do not forget to free space
free_dlist(new_list);
free_dlist(list);NOTE: If filter function return 0 for every element then NULL pointer will be returned and no new_list will be created, however you can pass a NULL double linked list pointer to free_dlist, but it will have no effect.