I am in the process of rewriting in C all the data structures that I learned about a few years ago to increase my understanding of data structures and the C language. The first one I'm doing is singly-linked-lists, and so I'm designing an API for them. I haven't written any of the implementation yet, but I want to get some feedback on my function prototypes to make sure what I'm doing is sensible and logical.

First some remarks:

  1. I expect that many people will suggest a typedef for the node struct, but this is a personal decision, and I prefer not to typedef structs.

  2. I am most unsure about my choices for return types and values. I have two functions that return a pointer to the data variable of a removed node. These functions remove the node from the list, save a pointer to the data, and free the node. This means that the user is required to free the data that is returned. Is this bad form? I am unsure about how to do it in such a way that would allow the data to be returned statically, because that would require knowing the size of the data in advance, which cripples the usefulness of the library.

  3. I want to make the API such that it supports all useful things that can be done with a singly-linked list, one of which is implementing a stack. One thing that bothers me about push/pop operations on a singly linked list is that it seems like some people have the notion in their heads that pushing/popping should only occur at the end of a list. A stack, being a last-in/first-out mechanism (LIFO), is not suited for singly-linked lists if you require that push/pop operations happen at the tail (the end). This is obviously because it would be very inefficient to use the tail instead of the head of the list because the last element can only be reached by traversing the list. The push/pop functions below imitate the behavior of a stack, but the operations happen at the front of the list. Is this a bad design?

Here is an example of a list with elements:

[SENTINEL]->[0]->[1]->[2]->[3]->NULL

Each node is of type struct node. A struct node is a struct with a data and next field:

struct node {
    void *data;
    struct node *next;
}

This implementation will use sentinel nodes to simplify boundary conditions. There is one sentinel node per list, standing at the front of the list.

An empty list contains one sentinel node that points to null, like so: [SENTINEL]->NULL

A list is of type struct sllist. A struct sllist is has one sentinel field that contains a pointer to the sentinel node:

struct sllist {
    struct node *sentinel;
}

Finally, here is a list of operations and their associated function prototypes (with description):

    //create new list:
    struct *sllist new_sllist();
            //Returns a pointer to a new, empty sllist.

    //destroy list:
    void destroy_sllist(struct sllist *sllist); 
            //Frees the memory of the list struct and all associated nodes.

    //insert after node:    
    int sllist_insert_after(struct sllist *sllist, struct *node, void *data); 
            //Adds a node after the passed node.
            //If allocation fails, returns -1, otherwise returns 0.

    //prepend node to the list:
    int sllist_push(struct sllist *sllist, void *data);
            //Adds a node to the front of the list. If allocation fails, returns -1, otherwise returns 0.
            //Note that the front of the list is defined to be the first node after the sentinel node.

    //extract after node:   
    void* sllist_extract_after(struct sllist *sllist, struct node *node);
            //Removes a node from the linked list, save a pointer to the data, free the node 
            //(but do not the data itself), and return a pointer to the data so that it can be used. 
            //If the node doesn't exist in the list, returns NULL.

    //extract first node:
    void* sllist_pop(struct sllist *sllist);
            //Same as extract after node, but restricted to the first node (first node after sentinel.)
            //Analogous to sllist_push(), the name sllist_pop suggests usage as a stack.

    //destroy after node:
    void sllist_destroy_after(struct sllist *sllist, struct node *node);
            //Removes from the list the node after the passed node and frees all associated memory.

Please let me know if anything seems glaringly out-of-place, strange, or poorly designed.

You say "A struct sllist is has one sentinel field that contains a pointer to the sentinel node:" - does this mean that there is an empty node separate from the sllist instance acting as a 'sentinel'? If so, this would seem unnecessary. And unless struct sllist is going to hold metadata (such as the end of the list, number of elements), I'm not sure that it is really necessary - you can just use a pointer to the first node.

  • On return types, I don't see anything wrong with what you have.

  • For the _after functions, where does the user get the necessary struct node* pointer? None of the functions returns a struct node*. Perhaps you have omitted some functions - such as sllist_find returning a struct node*. Such a function would have to take a compare function as a parameter. Also you are missing an 'append' function.

  • On your question 2, the user must have allocated the data in the first place before adding it to the list (as you don't know its size) so it is reasonable to expect her to free it. Conceivably it might not have been dynamically allocated, so you can't safely free it.

Do you intend the structs to be opaque (ie. the user doesn't get to see what is inside them)? In this case you might need a way to iterate through the list. If the structs are not opaque, you are expecting/allowing the user to traverse the list and to manipulate it without using your functions - this is asking for trouble (particularly if you do choose to maintain any metadata) and partially negates the usefulness for the library.


Some details: there are a few misplaced stars (new_sllist, sllist_insert_after), you have inconsistent naming of new_sllist and destroy_sllist (all others start with 'sllist') and new_sllist is missing void parameter list.

  • Well, about the sentinel node: I actually realized since I posted this that I should probably make the sllist struct more like this: struct sllist { struct node *sentinel; struct node *tail; struct node *current unsigned int size; } The sentinel node is just a "dummy" node that points to the first real node. It is there to allow me to use insert_after to prepend to the list. Do you think it over-complicates things? Also, I do want the structs to be opaque. Can you explain why my stars are wrong? – oddlogic May 19 '13 at 4:44
  • I realize now that int sllist_insert_after(struct sllist *sllist, struct *node, void *data); should probably be int sllist_insert_after(struct sllist *sllist, struct node *node, void *data); Also, about the inconsistent naming: perhaps sllist_create and sllist_destroy would be more fitting? – oddlogic May 19 '13 at 4:45
  • Also, the sentinel is not a separate instance. – oddlogic May 19 '13 at 4:52
  • 1
    So it sounds as if sentinel is misnamed and should be called head, if all it does is point to the 1st node. That is not too complicated. sllist_create/destroy sound much better. ps. try compiling the header to find the errors :-) – William Morris May 19 '13 at 12:23

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.