patterncMinor
Designing function prototypes for a singly-linked list API in C
Viewed 0 times
prototypesfunctiondesigningapisinglyforlistlinked
Problem
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:
-
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.
-
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.
-
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
First some remarks:
-
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.
-
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.
-
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
Solution
You say "A
the sentinel node:" - does this mean that there is an empty node separate from
the
And unless
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
have omitted some functions - such as
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 (
parameter list.
struct sllist is has one sentinel field that contains a pointer tothe 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 ofelements), 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 youhave 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 anddestroy_sllist (all others start with 'sllist') and new_sllist is missing voidparameter list.
Context
StackExchange Code Review Q#26331, answer score: 4
Revisions (0)
No revisions yet.