Singly Linked List (strings only)

Question

This is my attempt at constructing a singly-linked-list with basic functions. I initially tried to build the whole list as a series of nodes, but ran into problems when trying to remove or pop index-0. This time I created a series of Node structs and a single List struct as their head. This allowed me to modify the list in place without risk of losing the first pointer.

Anyway, it's not for production. This was written on my own time. I have no interest in optimizing this code and am simply trying to understand c programming before I start my first computer science class this next year. If anything I'm doing seems like a bad approach, or worse, dangerous, let me know.

linkedlist02.h:

#ifndef LINKED_LIST_02 #define LINKED_LIST_02 typedef struct NodeTag { char *data; struct NodeTag *next; } Node; Node *Node_create(); void Node_destroy(Node *node); typedef struct ListTag { struct NodeTag *first; } List; List *List_create(); void List_destroy(List *list); void List_append(List *list, char *str); void List_insert(List *list, int index, char *str); char *List_get(List *list, int index); int List_find(List *list, char *str); void List_remove(List *list, int index); char *List_pop(List *list, int index); int List_length(List *list); void List_print(List *list); #endif 

linkedlist02.c:

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include "linkedlist02.h" int main() { List *l = List_create(); List_append(l, "jim"); List_append(l, "bob"); List_append(l, "joe"); List_append(l, "bean"); List_append(l, "junior"); List_insert(l, 3, "HAROLD"); List_insert(l, List_length(l), "CARL"); List_insert(l, 0, "MIKE"); List_remove(l, 2); List_print(l); printf("Length: %i\n", List_length(l)); printf("Pop 3: %s\n", List_pop(l, 3)); printf("Get 3: %s\n", List_get(l, 3)); printf("Find \"junior\": %i\n", List_find(l, "junior")); List_destroy(l); return 0; } Node *Node_create() { Node *node = malloc(sizeof(Node)); assert(node != NULL); node->data = ""; node->next = NULL; return node; } void Node_destroy(Node *node) { assert(node != NULL); free(node); } List *List_create() { List *list = malloc(sizeof(List)); assert(list != NULL); Node *node = Node_create(); list->first = node; return list; } void List_destroy(List *list) { assert(list != NULL); Node *node = list->first; Node *next; while (node != NULL) { next = node->next; free(node); node = next; } free(list); } void List_append(List *list, char *str) { assert(list != NULL); assert(str != NULL); Node *node = list->first; while (node->next != NULL) { node = node->next; } node->data = str; node->next = Node_create(); } void List_insert(List *list, int index, char *str) { assert(list != NULL); assert(str !=NULL); assert(0 <= index); assert(index <= List_length(list)); if (index == 0) { Node *after = list->first; list->first = Node_create(); list->first->data = str; list->first->next = after; } else if (index == List_length(list)) { List_append(list, str); } else { Node *before = list->first; Node *after = list->first->next; while (index > 1) { index--; before = before->next; after = after->next; } before->next = Node_create(); before->next->data = str; before->next->next = after; } } char *List_get(List *list, int index) { assert(list != NULL); assert(0 <= index); assert(index < List_length(list)); Node *node = list->first; while (index > 0) { node = node->next; index--; } return node->data; } int List_find(List *list, char *str) { assert(list != NULL); assert(str != NULL); int index = 0; Node *node = list->first; while (node->next != NULL) { if (strlen(str) == strlen(node->data)) { int cmp = strcmp(str, node->data); if (cmp == 0) { return index; } } node = node->next; index++; } return -1; } void List_remove(List *list, int index) { assert(list != NULL); assert(0 <= index); assert(index < List_length(list)); if (index == 0) { Node *node = list->first; list->first = list->first->next; Node_destroy(node); } else { Node *before = list->first; while (index > 1) { before = before->next; index--; } Node *node = before->next; before->next = before->next->next; Node_destroy(node); } } char *List_pop(List *list, int index) { assert(list != NULL); assert(0 <= index); assert(index < List_length(list)); if (index == 0) { Node *node = list->first; list->first = list->first->next; char *data = node->data; Node_destroy(node); return data; } else { Node *before = list->first; while (index > 1) { before = before->next; index--; } Node *node = before->next; before->next = before->next->next; char *data = node->data; Node_destroy(node); return data; } } int List_length(List *list) { assert(list != NULL); Node *node = list->first; int length = 0; while (node->next != NULL) { length++; node = node->next; } return length; } void List_print(List *list) { assert(list != NULL); printf("["); Node *node = list->first; while (node->next != NULL) { printf("%s", node->data); node = node->next; if (node->next != NULL) { printf(", "); } } printf("]\n"); } 

Answer 1

Nice code, compiles almost cleanly. I'm impressed that this is your code before starting courses. I've met people with years of experience who couldn't write such good code.

I have a few comments, starting with the concept. You have a list structure that you initialise to hold an empty node. I don't see what this gives you that a simple Node* pointer would not. The List structure might be of more use if you kept a pointer to the beginning and end of the list and maybe some metadata, like the length of the list. But really I think the List structure is redundant and complicates the functions and that the empty node is confusing.

General points

• Add a void parameter list for functions with no parameters.

• Use const in parameter lists where the function does not change the parameter, eg.

  int List_find(const List *list, const char *str); 

• handling of malloc failure with an assert is wrong. Adding an assert is much easier than handling the errors correctly, but asserts are for detecting logic failures, not runtime resource/data failures. For malloc failure you either print an error and exit (yes, that is what assert does, but asserts can be disabled with NDEBUG) or you return an error to the caller. Of course if you handled malloc failure by returning a NULL to the caller, you complicate your program throughout. That is why it is often ignored (though clearly it should not be).

• handling other conditions with assert is debatable. It is attractive because it is so easy, but it is lazy and is not universally applicable. For example, you can do it if you have a shell to return to - assert prints a message and exits; you see the message in the shell and maybe restart the process. But there are applications where there is no shell, for example embedded systems where it is not possible just to exit - you have to handle the error somehow. And then when you compile with NDEBUG, your error handling disappears completely. Best to use assert only for logic failures and handle data errors correctly with error returns.

• counting down in while- or for-loops is much less common than counting up. It can be done, but it saves nothing, is less intuitive and is more error-prone. Best to count up. Also for-loops are preferable when you have a loop variable like this:

  while (index > 0) { ... index--; } 

  So I would prefer to see:

  for (int i = 0; i < index; ++i) { .... } 

• a detailed point is that the strings you are adding to the list are almost certainly constant strings (eg in List_append(l, "jim");). So the functions returning strings from the list as char * are almost certainly wrong - they should be const. You can fix that by duplicating (ie. allocating) the strings when you create nodes - and freeing them later. This might be safer anyway, in case the caller passes your list function a string that is non-permanent (eg it is on the stack or temporarily allocated). So either make the return strings const or allocate a copy.

List_insert

This is rather complicated. Essentially what must be done is: create a node; hang it in the list. So creating and setting the data in the node is common and can be done first for all cases. Then you can insert it. Note that it is not clear why inserting beyond the end of the list must be considered an error - why not call it appending? Then list_append() can just call

list_insert(l, INT_MAX, str); 

List_find

Don't compare strings using first strlen and then strcmp - that is pointless. Just use strcmp. Also this:

int cmp = strcmp(str, node->data); if (cmp == 0) { return index; } 

is more concisely written as

if (strcmp(...) == 0) { /* or even if (!strcmp(...)), though some don't like that */ return index; }