Basic Linked List C implementation

Question

I've written a singly-linked list of characters. This is my 3rd C program and I'd like some feedback on what I can improve on in any aspect whatsoever.

If you'd prefer to look at the repo directly it's here:

https://github.com/JosephSBoyle/LinkedList

Thanks in advance for your time :D

linked_list.h

#include <stdbool.h>
// define the node struct here so we can use it within it's own definition
typedef struct Node Node;
struct Node {
 /* A node in a linked list */
 char item; // character at this node
 Node *next; // pointer to the next node
};
size_t NODE_SIZE = sizeof(Node);
/* Create a new list */
Node* list();
/* Destruct a list, freeing it's memory */
void free_list(Node* sentinel);
/* Add an element to the end of a list */
void add(Node* sentinel, char item);
/** Delete an element from a list.
 * @returns true if the operation succeeded, false if there is the list is shorter than
 * the supplied index argument.
 */
bool del(Node* sentinel, size_t idx);
/* Replace the value stored by the node at idx. */
bool replace(Node* sentinel, size_t idx, char item);
/* Get the length of a list */
size_t len(Node* sentinel);
/* Peak the idx'th node, or the last node if there are fewer than
 idx elements in the list. */
Node* peak(Node* sentinel, size_t idx);
/* Pretty-print a list */
void print(Node* sentinel);
/* Print a list as a contiguous string */
void pstring(Node* sentinel);

linked_list.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "linked_list.h"
#include <assert.h>
Node* list(){
 // create a 'sentinel node'.
 Node* sentinel = (Node*)malloc(NODE_SIZE);
 sentinel->next = NULL;
 sentinel->item = '0円';
 return sentinel;
}
Node* peak(Node* sentinel, size_t idx){
 Node* node = sentinel;
 // compare to idx + 1, since we want our peak to be zero-indexed
 // and we have a sentinel node
 for (size_t i=0; i != idx+1; i++){
 if (node->next == NULL){
 // return the sentinel node as there are fewer than idx elements in the list
 return sentinel;
 }
 node = node->next;
 }
 return node;
}
void free_list(Node* sentinel){
 // traverse each node in order and free it's memory.
 size_t i = 0;
 do {
 i++;
 free(sentinel);
 sentinel = sentinel->next;
 } while (sentinel->next != NULL);
}
void add(Node* sentinel, char item){
 // instantiate a new node
 Node* new_node = (Node*)malloc(NODE_SIZE);
 new_node->item = item;
 // traverse each node
 while (true){
 if(sentinel->next == NULL){
 // replace the last node with our new node.
 sentinel->next = new_node;
 break;
 } else {
 // point to the next node
 sentinel = sentinel->next;
 }
 }
}
bool del(Node* sentinel, size_t idx){
 // TODO find a way to leverage peak to simplify this
 for (size_t i=0; i != idx; i++){
 if (!sentinel){
 return false;
 }
 sentinel = sentinel->next;
 }
 if (sentinel->next){
 Node* index_node_ptr = sentinel->next;
 if (index_node_ptr->next){
 sentinel->next = index_node_ptr->next;
 } else {
 free(index_node_ptr);
 sentinel->next = NULL;
 }
 return true;
 }
}
bool replace(Node* sentinel, size_t idx, char item){
 Node* node = peak(sentinel, idx);
 // check if the sentinel and the peaked node are the same
 if (sentinel == node){
 return false;
 } else {
 node->item = item;
 return true;
 }
}
size_t len(Node* sentinel){
 Node* current_node = sentinel;
 size_t nodes = 0;
 while (true){
 // Check if we're at the final node.
 if(current_node->next == NULL){
 return nodes;
 }
 nodes++;
 current_node = current_node->next;
 }
}
void print(Node* sentinel){
 printf("[");
 while (sentinel->next != NULL){
 sentinel = sentinel->next;
 printf("'%c',", sentinel->item);
 }
 printf("]\n");
}
void pstring(Node* sentinel){
 while (sentinel->next != NULL){
 sentinel = sentinel->next;
 printf("%c", sentinel->item);
 }
 printf("\n");
}
/* Tests */
void main(){
 Node* sentinel = list();
 add(sentinel, 'h');
 add(sentinel, 'e');
 add(sentinel, 'l');
 add(sentinel, 'l');
 add(sentinel, 'o');
 print(sentinel);
 replace(sentinel, 4, '0');
 pstring(sentinel);
 // check that deleting works for a valid index
 assert(del(sentinel, 4));
 // and fails when that index becomes invalid.
 assert(!del(sentinel, 4));
 // check peaking an invalid index returns the sentinel node
 assert(sentinel == peak(sentinel, 4));
 pstring(sentinel);
 free_list(sentinel);
}

Running the code (tested on ubuntu linux):

$ gcc -o run linked_list.c
$ ./run

• AShelly: 'peek', not 'peak', perhaps.

Answer 1

Overall: a good code for a "my 3rd C program".

Good formatting

Good documentation in .h file. (Perhaps a bit more to detail expectational cases.)

No need for object NODE_SIZE

Simply use #define NODE_SIZE sizeof(Node).

As is, each .c file that includes linked_list.h makes an object NODE_SIZE, eventually causing multiple definitions. .h files should not define any objects.

Information hiding

The definition of struct Node belongs in the .c file. Users of these functions never need to see the internals. Move struct Node { ...}; to the .c file.

Name space

Code uses common names like Node, list, add, del, peak, print, ... which are likely to collide with the rest of code. Consider a common prefix instead. linked_list_add, linked_list_del, linked_list_peek, ....

Empty arguments in a declaration

No arguments in a declaration matches any argument set. Use void.

// Node* list();
Node* list(void);

This differs from a function definition. This distinction may change in the next C version.

add() may fail

Since add() calls malloc(), that allocation may fail. Consider returning an error flag here too.

// void add(Node* sentinel, char item);
bool add(Node* sentinel, char item);

What if empty list?

peak() does not describe return value in this case.

Exercise *.h include independence

In linked_list.c, include its companion .h file first to help validate that no <xx.h> files are needed.

// #include <stdlib.h>
// #include <string.h>
// #include <stdio.h>
// #include "linked_list.h"
// #include <assert.h>
#include "linked_list.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>

Use const

For function that do not change the *sentinel, use const. This increase functions applicability, conveys code's intent better and allows for some optimizations not seen by lesser compilers.

// Node* peak(Node* sentinel, size_t idx)
Node* peak(const Node* sentinel, size_t idx)

NULL argument

list() may fail to allocate, and should be re-written to return NULL in that case.

free_list(Node* sentinel) should check if sentianl == NULL and does nothing - just like free(NULL) is OK. This simplifies calling code's error handling.

Cast not needed

In C, a cast is not needed to convert a void * to an object *. Further I recommend to size to the reference object and not the type. Easier to code right, review and maintain.

Check allocation success.

// Node* sentinel = (Node*)malloc(NODE_SIZE);
Node* sentinel = malloc(sizeof sentinel[0]);
if (sentinel == NULL) {
 return NULL;
}

Test code

Consider moving main() test code to a 3rd file instead of linked_list.c to allow other application to use/link linked_list.c and not collide with main().

peek() return

I'd expect peak() to return the item and not struct Node. Or to provide an error return, consider returning a pointer to the item and NULL on error (e.g. empty list) or some other interface - anything that does not oblige the user from needing to see Node internals.

Code guards

linked_list.h deserves code guards.

• Joe Boyle: thank you for your kind feedback! I have adopted the changes you recommended :)

Answer 2

There's a use after free in free_list.

None of the functions check that the sentinel argument is not null.

add doesn't insure that the new node's next is null.

I think del fails if you give it the index of the last item. It definitely doesn't have a return call in that path.