Learning pointers by implementing a basic linked list with tests

I wanted to learn about pointers and someone suggested that I give C a try, so I went through Linked List Basics from Stanford CS library, implemented some of the code (and tried to improve the code a bit as I went), as well as wrote "unit tests" (to the extent you can call them such in C).

I'm using "Microsoft (R) C/C++ Optimizing Compiler Version 19.00.24215.1 for x86" compiler, though I would expect it should work fine with other compilers as well. When run, it prints the following output to stdout:

C:\Scripts\C>linked_list
Success: lengthTest() length was 3
Success: pushTest() length was: 5
[0]: -1
[1]: 0
[2]: 1
[3]: 2
[4]: 3
Success: pushTestEmpty() length was 1 after 1st push().
Success: pushTestEmpty() length was 2 after 2nd push().
[0]: 2
[1]: 1
Success: appendTest() length was: 5
[0]: 1
[1]: 2
[2]: 3
[3]: 4
[4]: 5
Success: appendTestEmpty() length was 1 after 1st append().
Success: appendTestEmpty() length was 2 after 2nd append().
[0]: 1
[1]: 2


C is all new to me, and I've been made aware that there are many pitfalls in particular with pointer code, so I would like to learn as much as I can about the "right" way to do pointers, as well as any other possible improvements.

Note that this is intended to be for learning and there are no plans for this to be deployed in a production environment.

linked_list.h
// linked_list.h

#include

extern struct Node;

extern int length(struct Node* head);

extern void printList(struct Node* head);

extern void push(struct Node** headRefPtr, int data);

extern void append(struct Node** headRefPtr, int data);

extern struct Node* buildTestListWithThreeNodes();

extern void lengthTest();

extern void pushTest();

extern void pushTestEmpty();

extern void appendTest();

extern void appendTestEmpty();

extern int main(int argc, char **argv);


linked_list.c
`// linked_list.c

#include "linked_list.h"

struct Node {
int data;
struct Node* next;
};

/*
Calculates the number of elements that are in the li

-
When declaring a function with an empty parameter list (as below), no information about parameters is known nor tested by the compiler. Instead, use void to explicitly indicate that the function does not take any parameters.

extern void lengthTest();
lengthTest("abc", 123.4);  // appears to be valid code - no warning

// better
extern void lengthTest(void);
lengthTest("abc", 123.4);  // invalid code - warning/error

-
If a function does not modify the pointer's contents, that parameter should be declared const. This allows additional optimizations and improved error checking. It also serves a documentation role, letting users of the function know nothing will be changed.

// extern void printList(struct Node* head);
extern void printList(const struct Node* head);

-
Namespace: The set of function names have little in common. I suggest appending a uniform prefix:

// extern void printList(struct Node* head);
// extern void push(struct Node** headRefPtr, int data);
// extern void append(struct Node** headRefPtr, int data);
extern void ll_print(const struct Node* head);
extern void ll_push(struct Node** headRefPtr, int data);
extern void ll_append(struct Node** headRefPtr, int data);

-
Rather than allocate to the size of a structure, allocate to the size of the referenced object. This is easier to code correctly, to review, and to maintain.

//                    was this the right type?   
// head = malloc(sizeof(struct Node));

// Type specificity not needed.
head = malloc(sizeof *head);

-
Remove redundant code:

newNode->next = NULL;
if (*headRefPtr == NULL) {
    // newNode->next = NULL; // code not needed

-
Good uniform formatting.

-
The following code allocates, assigns, and then ignores that with a subsequent assignment to the same variable. This looks odd—are you sure it is correct?

struct Node* list = malloc(sizeof(struct Node));
list = NULL;  // ??!!

-
Lack of error checking. Code allocates, yet does not check if the allocation was successful. Robust code must check for allocation failures (although they are rare, they can happen). How the code handles and reports errors is a significant component of good design.

struct Node* newNode = malloc(sizeof(struct Node));

// add some error handling
if (newNode != NULL) TBD_ErrorHandler();

newNode->data = data;

-
Header files should use include guards to protect against multiple inclusion. Although not a major issue in this case, it is a good practice to get into.

// linked_list.h

#ifndef linked_list_H
#define linked_list_H 1

#include 
extern struct Node;
....

#endif

-
It is strange to have main() in linked_list.h. Best to remove. Likewise, int main(int argc, char **argv) does not belong in linked_list.c, but perhaps linked_list_test.h. Perhaps move the various test functions there, too.

-
I'd expect functions like void pushTest(); to return an indication of success or error, maybe int pushTest();

-
(Minor:) I would use extern unsigned length(const struct Node* head); rather than int, but that is a larger code design issue.

-
Aside from test code, I see no free(). An ll_free(struct Node** headRefPtr) should be written.

-
I'd also expect an ll_pop() function of some signature to extract a data element, as well as a bool ll_IsEmpty(const struct Node*).

• Now I present an advanced idea. Rather than have the linked-list end with NULL, have the last element point to the first—a circular list. Instead of the header pointing to the first element, point to the last element. Walking a list is still simple: move to the first, and continue until the next field matches the first. The key advantage is that a node can be added to the beginning or end of the list in O(1) time, without needing to traverse the entire list.

StackExchange Code Review Q#151517, answer score: 7