Singly LinkedList in C

Question

I've finalized my (didactic) implementation of a singly LinkedList in C which resides on the Heap.

I've put efford into keeping this as simple as possible and clean - while documenting it nicely. I hope it is as easily understandable as i intended it to be (thought reading code is probably harder than writing it..)

If you guys/gals have the time, please review it.

Here is my implementation:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/********** GLOBALS *******************************/
#define OK 0
#define ERROR -1
/********** STRUCT AND TYPES DEFINTIONS ***********/
/* a node with key, data and reference to next node*/
typedef struct Node {
 int key;
 char string[1024];
 struct Node *next; // pointer to next node
} Node;
/* the actual linked list: ref to first and last Node, size attribute */
typedef struct LinkedList {
 struct Node *first;
 struct Node *last;
 int size;
} LinkedList;
/********** FUNCTION HEADERS **********************/
LinkedList* init_list();
void insert_end(LinkedList *list, int key, char string[]);
void insert_beginning(LinkedList *list, int key, char string[]);
int remove_end(LinkedList *list);
int remove_beginning(LinkedList *list);
int print_list(LinkedList *list);
void free_list(LinkedList *list);
char * get_string(LinkedList *list, int key);
/*********** FUNCTION DEFINITIONS ***************/
/**
 * init_list Returns an appropriately (for an empty list) initialized struct List
 *
 * @return LinkedList * ..ptr to the newly initialized list
 */
LinkedList * init_list() {
 printf("initializing list...\n");
 LinkedList *list = (LinkedList*) malloc(sizeof(LinkedList));
 list->first = NULL;
 list->last = NULL;
 list->size = 0;
 return list;
}
/**
 * Given a List, a key and a string adds a Node containing this
 * information at the end of the list
 *
 * @param list LinkedList * ..ptr to LinkedList
 * @param key int .. key of the Node to be inserted
 * @param string char[] .. the string of the Node to be inserted
 */
void insert_end(LinkedList *list, int key, char string[]) {
 printf("----------------------\n");
 list->size++; // increment size of list
 // intialize the new Node
 Node* newN = (Node*) malloc(sizeof(Node));
 newN->key = key;
 strcpy(newN->string, string);
 newN->next = NULL;
 Node* oldLast = list->last; // get the old last
 oldLast->next = newN; // make new Node the next Node for oldlast
 list->last = newN; // set the new last in the list
 printf("new Node(%p) at end: %d '%s' %p \n", newN, newN->key, newN->string,newN->next);
}
/**
 * Given a List, a key and a string adds a Node, containing
 * this information at the beginning of the list
 *
 * @param list LinkedList * ..ptr to LinkedList
 * @param key int .. key of the Node to be inserted
 * @param string char[] .. the string of the Node to be inserted
 */
void insert_beginning(LinkedList *list, int key, char string[]) {
 printf("----------------------\n");
 list->size++; // increment size of list
 Node* oldFirst = list->first; //get the old first node
 /* intialize the new Node */
 Node* newN = (Node*) malloc(sizeof(Node));
 newN->key = key;
 strcpy(newN->string, string);
 newN->next = oldFirst;
 list->first = newN; // set the new first
 /* special case: if list size == 1, then this new one is also the last one */
 if (list->size == 1)
 list->last = newN;
 printf("new Node(%p) at beginning: %d '%s' %p \n", newN, newN->key,newN->string, newN->next);
}
/**
 * Removes the first Node from the list
 *
 * @param list LinkedList * .. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_beginning(LinkedList *list) {
 printf("----------------------\n");
 if (list->size <= 0)
 return ERROR;
 list->size--;
 Node * oldFirst = list->first;
 printf("delete Node(%p) at beginning: '%d' '%s' '%p' \n", oldFirst,oldFirst->key, oldFirst->string, oldFirst->next);
 free(list->first); //free it
 list->first = oldFirst->next;
 oldFirst = NULL;
 return OK;
}
/**
 * Removes the last Node from the list.
 *
 * @param list LinkedList * .. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_end(LinkedList *list) {
 printf("----------------------\n");
 /* special case #1 */
 if (list->size <= 0)
 return ERROR;
 /* special case #2 */
 if (list->size == 1) {
 free(list->first);
 list->first = NULL;
 list->last = NULL;
 return OK;
 }
 printf("delete Node(%p) at end: '%d' '%s' '%p' \n", list->last,list->last->key, list->last->string, list->last->next);
 list->size--; // decrement list size
 Node * startNode = list->first;
 /* find the new last node (the one before the old last one); list->size >= 2 at this point!*/
 Node * newLast = startNode;
 while (newLast->next->next != NULL) {
 newLast = newLast->next;
 }
 free(newLast->next); //free it
 newLast->next = NULL; //set to NULL to denote new end of list
 list->last = newLast; // set the new list->last
 return OK;
}
/**
 * Given a List prints all key/string pairs contained in the list to
 * the screen
 *
 * @param list LinkedList * .. ptr to the List
 *
 * @return OK | ERROR
 */
int print_list(LinkedList *list) {
 printf("----------------------\n");
 if (list->size <= 0)
 return ERROR;
 printf("List.size = %d \n", list->size);
 Node *startN = list->first; //get first
 /* iterate through list and print contents */
 do {
 printf("Node#%d.string = '%s', .next = '%p' \n", startN->key,startN->string, startN->next);
 startN = startN->next;
 } while (startN != NULL);
 return OK;
}
/**
 * Given a List, frees all memory associated with this list.
 *
 * @param list LinkedList * ..ptr to the list
 */
void free_list(LinkedList *list) {
 printf("----------------------\n");
 printf("freeing list...\n");
 if (list != NULL && list->size > 0) {
 Node * startN = list->first;
 Node * temp = list->first;
 do {
 free(temp);
 startN = startN->next;
 temp = startN;
 } while (startN != NULL);
 free(list);
 }
}
/**
 * Given a List and a key, iterates through the whole List and returns
 * the string of the first node which contains the key
 *
 * @param list LinkedList * ..ptr to the list
 * @param key int .. the key of the Node to get the String from
 *
 * @return OK | ERROR
 */
char * get_string(LinkedList *list, int key) {
 printf("----------------------\n");
 Node *startN = list->first; //get first
 /* if only one node.. */
 if(list->size == 1)
 return startN->string;
 /* iterate through list and find Node where node->key == key */
 while (startN->next != NULL) {
 if (startN->key == key)
 return startN->string;
 else
 startN = startN->next;
 }
 return NULL;
}
/*************** MAIN **************/
int main(void) {
 LinkedList *list = init_list();
 insert_beginning(list, 1, "im the first");
 insert_end(list, 2, "im the second");
 insert_end(list, 3, "im the third");
 insert_end(list, 4, "forth here");
 print_list(list);
 remove_end(list);
 print_list(list);
 remove_beginning(list);
 print_list(list);
 remove_end(list);
 print_list(list);
 printf("string at node with key %d = '%s' \n",2,get_string(list, 2));
 free_list(list);
 return OK;
}

There are still some functions left to implement, e.g. insertAtPosition(..), but the basic LinkedList-functions are done.

...TRY IT ONLINE!

• cat: What documentation generator are you using? Doxygen?
• Gewure: @cat yes, it is doxygen style, but edited. The parameters type aswell as the return value are not generated automatically. I found this style very convincing.

Answer 1

1. Don't comment the obvious.

   Because, you know, it's obvious. People expect something unexpected or tricky there, and it's a letdown when they see that you just wasted their time and concentration.

   The greatest danger though is that those useless comments could get out-of-sync with the code, leading to lots of confusion and even more lost time.

2. The API-documentation belongs to the declaration in the header, not the definition, so users find it without digging in the details.

3. Consider splitting your code into the public header, the list-implementation, and the test-program. Copy-and-paste is a bad method for reuse.

4. Don't cast the result of malloc(). And avoid using sizeof(type).
   Both are error-prone and violate DRY. See: Do I cast the result of malloc?

5. Consider using a flexible-array-member (C99) in your struct Node for the string. It allows you to save space or store larger strings without extra allocation.

   typedef struct Node {
    struct Node* next;
    int key;
    char string[];
   } Node;
   

6. insert_end() will try to modify the non-existent last node if the list was empty. That's somewhat sub-optimal.

   Use a double-pointer or special-case it.

7. remove_beginning() reads the freed ex-node's memory to find the new first node. That's a bit tardy. Read first, then free.

   It also fails to update the last-pointer if the list is now empty.

8. Why does print_list() fail to print an empty list?

9. free_list() also commits use-after-free, and its two local variables duplicate each other.

10. Interesting, why does get_string() ignore the key if the list is exactly one element long?

11. You are generally ignoring allocation-failure. Whether you abort the program or whatever, handle it!

12. Consider directing your debug-output to stderr. And only writing it if NDEBUG is not defined.

    Using C99 variadic macros:

    #ifndef NDEBUG
     #define DPRINT(...) (void)fprintf(stderr, __VA_ARGS__)
    #else
     #define DPRINT(...) (void)0
    #endif
    

    Used like:

    DPRINT("My debug message: %s", somestring);
    

13. If you really want to explicitly return from main() using a preprocessor-constant, use the dedicated EXIT_SUCCESS from <stdlib.h>.
    Of course, return 0; is implicit for main() since C99...

• Muzer: To expand on not using sizeof(type), you should use sizeof variable instead. In this case, you should use malloc(sizeof *list). That way, if you ever need to change the type of *list, the malloc would still work (this is the same reason you shouldn't cast the result).
• Brian Sutherland: Quick question for #5, does this flexible-array-member need to be declared last in the structure?
• Kroltan: @BrianSutherland Yes. And since it has zero length, when allocating the Node, the desired size should be explicitly allocated. So for a string size n, the size to allocate should be sizeof(Node) + n.
• Toby Speight: Any advice on the OK and ERROR macros? I think they are a collision risk with other headers, but don't know what advice to give.
• Jörg W Mittag: @Gewure: by the way, it is always a good idea to listen to your compiler's warnings, and to run linters and static analyzers. For example, the use-after-free mentioned by Deduplicator in #9 is actually detected by the static analyzer built into Clang. (Run Clang twice, once with clang -pedantic -Weverything list.c and once with clang --analyzer-output html --analyze list.c; the latter will generate a directory named list.plist with two HTML files, each of which contains not only the use-after-free warning, but an interactive demonstration of how it can happen.)