• 1

• 35.2k
• 13
• 134
• 238

Implementing a Linked Listlinked list

• 853
• 1
• 8
• 24

I am studying Data Structures at the moment, so I want to see if there is anything wrong with my implementation of linked lists in C, after I checked the arraylist/vector implementation ..

###This is the header

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H
#include <stddef.h> /* size_t */
#include <stdbool.h> /* _Bool */
#define _LINKEDLIST_DEFAULT_SIZE (1)
typedef struct _linkedlist _LinkedList;
typedef const unsigned int Index;
#define LinkedList _LinkedList *
LinkedList LinkedList_create();
int LinkedList_add(LinkedList, void *);
int LinkedList_get_val_index(LinkedList, void *);
int LinkedList_get_list_index(LinkedList, const LinkedList *);
int LinkedList_remove(LinkedList, const _Bool, const _Bool);
void LinkedList_set_data(LinkedList, void **, const _Bool, const size_t max);
void LinkedList_clear(LinkedList, const _Bool);
void LinkedList_destroy(LinkedList *, const _Bool);
void *LinkedList_get_value(const LinkedList);
LinkedList LinkedList_get(LinkedList, Index);
LinkedList *LinkedList_get_next(LinkedList);
LinkedList *LinkedList_get_previous(LinkedList);
LinkedList *LinkedList_get_pointer(LinkedList *, Index);
inline size_t LinkedList_get_size_of(const LinkedList);
inline size_t LinkedList_get_size(const LinkedList);
#endif /* _LINKEDLIST_H */

.. and this is the source

#include <stdlib.h>
#include "LinkedList.h"
#define VALID_LINKEDLIST_CODE (245)
#define _LinkedList_check(l) \
 if ((l) == NULL || (l)->_Valid != VALID_LINKEDLIST_CODE) \
 abort();
struct _linkedlist {
 size_t depth;
 int _Valid;
 void * value;
 struct _linkedlist *next;
 struct _linkedlist *previous;
};
struct _linkedlist *LinkedList_create(void * initial_value)
{ /* Allocate Memory */
 struct _linkedlist *list = malloc(sizeof(struct _linkedlist));
 if(list == NULL)
 return NULL;
 list->depth = 1;
 list->next = NULL;
 list->previous = NULL;
 list->value = initial_value;
 list->_Valid = VALID_LINKEDLIST_CODE;
 return list;
}
void LinkedList_set_data(struct _linkedlist * list, void ** data, const _Bool freeval, const size_t max)
{ /* Sets the internal array of the arraylist */
 _LinkedList_check(list);
 int length;
 for(length = 0; data[length]; ++length);
 if (length < max || max == 0)
 abort();
 LinkedList_clear(list, freeval);
 list->value = data[0];
 for(unsigned int i = 1; i < max; ++i)
 LinkedList_add(list, data[i]);
 list->depth = max;
}
int LinkedList_add(struct _linkedlist *list, void *elem)
{ /* Adds one linked list to the chain with elem as value */
 _LinkedList_check(list);
 ++list->depth;
 struct _linkedlist ** l;
 for(l = &list->next; ( *l != NULL ); l = &(*l)->next)
 ++(*l)->depth;
 (*l) = LinkedList_create(elem);
 (*l)->previous = *l;
 return ((*l)->next == NULL);
}
struct _linkedlist *LinkedList_get(struct _linkedlist *list, const unsigned int index)
{ /* Gets the index'th linked list in the chain */
 _LinkedList_check(list);
 if (index >= list->depth)
 return NULL;
 for(unsigned int i = 0; i < index; list = list->next, i++);
 return list;
}
struct _linkedlist **LinkedList_get_pointer(struct _linkedlist ** list, const unsigned int index)
{ /* Gets the index'th linked list in the chain as a pointer */
 _LinkedList_check(*list);
 if (index >= (*list)->depth)
 return NULL;
 for(unsigned int i = 0; i < index; list = &(*list)->next);
 return list;
}
inline size_t LinkedList_get_size_of(const struct _linkedlist *list)
{ /* Returns the size of the chain of lists in memory */
 _LinkedList_check(list);
 return (sizeof(struct _linkedlist) * list->depth);
}
inline size_t LinkedList_get_size(const struct _linkedlist *list)
{ /* Returns the number of elements in the arraylist */
 _LinkedList_check(list);
 return list->depth;
}
int LinkedList_remove(struct _linkedlist * list, const _Bool index, const _Bool freeval)
{ /* Removes one element at a chain index */
 _LinkedList_check(list);
 if (index >= list->depth)
 return 2;
 LinkedList_clear(LinkedList_get(list, index), freeval);
 --list->depth;
 return 0;
}
void LinkedList_clear(struct _linkedlist * list, const _Bool freeval)
{ /* Clears the list chain */
 _LinkedList_check(list);
 struct _linkedlist * l, * n;
 for( l = list->next; l; l = n) {
 if (freeval)
 free(l->value);
 n = l->next;
 free(l);
 }
 list->next = NULL;
}
void LinkedList_destroy(struct _linkedlist ** list, const _Bool freeval)
{ /* De-allocates the list and its chains from memory
 No usage of list is allowed after this function call */
 _LinkedList_check(*list);
 LinkedList_clear(*list, freeval);
 free(*list);
 *list = NULL;
}
int LinkedList_get_val_index(struct _linkedlist *list, void *elem)
{ /* Looks for elem in list and returns the index or -1 if not found */
 _LinkedList_check(list);
 for(unsigned int i = 0; i < list->depth; ++i)
 if (elem == (LinkedList_get(list, i)->value))
 return i;
 return -1;
}
int LinkedList_get_list_index(struct _linkedlist *list, const struct _linkedlist ** elem)
{
 _LinkedList_check(list);
 for(unsigned int i = 0; i < list->depth; ++i)
 if (*elem == LinkedList_get(list, i))
 return i;
 return -1;
}
void *LinkedList_get_value(const struct _linkedlist *list)
{ /* Return the list's essence, the value */
 return list->value;
}
struct _linkedlist **LinkedList_get_next(struct _linkedlist *list)
{ /* Return the next list in the chain */
 return &list->next;
}
struct _linkedlist **LinkedList_get_previous(struct _linkedlist *list)
{ /* Return the previous line in the chain */
 return &list->previous;
}

After checking with valgrind, I see that I have no memory leaks, no read/write errors and no functional or logical errors (after testing).

So I want to know if there are any usability or performance problems in the code ..