Intro:
There are usually two ways to use linked lists: with a root element and without.
Without a root, your list pointer is NULL when the list is empty:
node *list;
...
if (list == NULL) { /* empty list */ }
With root, there is always one element. But it can be used in two ways:
Either simply to provide a pointer to the first element.
node *root;
...
if (root->next == NULL) { /* empty list */ }
Or to have the last element link back to the root to form a cycle. This concept has the advantage that the "next" element is never NULL and you thus don't need to check for it. In this case, the list is empty if the root points back to itself.
node *root;
...
if (root->next == root) { /* empty list */ }
Answer:
Now, according to your description, you have allocated a node. This either means you want the "root" approach (second or third example). But if you want to go with the first variant, you must not allocate the node, since it doesn't hold data.
For the "root" approach, you indeed have one (and only one) node that doesn't hold data. But for simple linked lists, all nodes must contain data.
Answer from DarkDust on Stack OverflowIntro:
There are usually two ways to use linked lists: with a root element and without.
Without a root, your list pointer is NULL when the list is empty:
node *list;
...
if (list == NULL) { /* empty list */ }
With root, there is always one element. But it can be used in two ways:
Either simply to provide a pointer to the first element.
node *root;
...
if (root->next == NULL) { /* empty list */ }
Or to have the last element link back to the root to form a cycle. This concept has the advantage that the "next" element is never NULL and you thus don't need to check for it. In this case, the list is empty if the root points back to itself.
node *root;
...
if (root->next == root) { /* empty list */ }
Answer:
Now, according to your description, you have allocated a node. This either means you want the "root" approach (second or third example). But if you want to go with the first variant, you must not allocate the node, since it doesn't hold data.
For the "root" approach, you indeed have one (and only one) node that doesn't hold data. But for simple linked lists, all nodes must contain data.
I'd keep it simple.
Check the head pointer - if it is NULL, there's no entry in the list.
int isEmpty( node * list )
{
if( !list )
return 1;
return 0;
}
First of all you don't need double pointer. Initialization with NULL is important here. (Denotes the empty list).
SortedList *list = NULL;
This has the benefit that now if you want to make changes to it pass it's address.
func(&list);
And checking the empty list would be
void func(SortedList **list){
if( *list == NULL )
/* empty */
}
This is usually the way lists are implemented.
In your case you simply allocated to a local variable and instead of returning the memory address you have overwritten the pointer's value with NULL - there is memory leak in the code.
With your code it will be something like. Yes all that the initialization does is assigning it to NULL. This is one easy way out towards checking the NULL. At the very beginning making it NULL
basically denotes that list is empty.(which is the case generally).
list is a pointer to a pointer. The actual list is in the value it points to, so you need to dereference it.
An empty list is just a null pointer, so you don't need to allocate anything in init().
void init(SortedList** list)
{
*list=NULL;
printf("%p\n", *list);
}
void isEmpty(SortedList** list)
{
printf("%p\n", *list);
if(*list == NULL) printf("List is empty\n");]
}
And in the main function, you don't need a double pointer, you use the & (address-of) operator to get the address of a pointer variable.
int main()
{
SortedList *list;
init(&list);
printf("Initialization with succes\n");
isEmpty(&list);
return 0;
}
You only really need double pointers for functions that modify the list. So you could use an ordinary pointer for isEmpty:
void isEmpty(SortedList* list)
{
printf("%p\n", list);
if(list == NULL) printf("List is empty\n");]
}
and then call it as:
isEmpty(list);
But it's probably simplest to be consistent across all your functions.
Why do List not have a general Empty or IsEmpty property?
You can use Enumerable.Any:
bool isEmpty = !list.Any();
if(isEmpty)
{
// ...
}
If the list could be null you could use:
bool isNullOrEmpty = list?.Any() != true;
If the list implementation you're using is IEnumerable<T> and Linq is an option, you can use Any:
if (!list.Any()) {
}
Otherwise you generally have a Length or Count property on arrays and collection types respectively.