Designing function prototypes for a singly-linked list API in C [closed]

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.

Closed 9 years ago.

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.

Answer 1

A linked-list is usually an implementation detail to a higher level data structure, i.e. a queue, a list, a stack, etc... So, I would make sure to implement all of the operations needed for each. push_back, push_front, pop_front, pop_back, front, back, and of course, random access.

As to the payload, the user should be responsible for allocation, and deallocation. After all, they may be passing a pointer to memory on the stack, and you certainly do not want to be freeing that memory. An alternate approach would be to make a copy (i.e. memcpy) of the payload upon insertion, then you can make sure your memory is freed on pop, and you will not cause any unexpected behavior to the user: this comes at the cost of a linear copy of the data though.

Also, you may find it helpful to modify your linked-list to the following:

struct sllist {
struct node *head;
struct node *tail;
struct node *current;
unsigned size;
}