how to check if a linked list is empty

user_2948535 0
Viewed 64600

I'm new to C and have a question.

How would I check if a linked list is empty?

I have a struct _node 

typedef struct _node{
    int data;
    struct _node *next;
}node;

If I have initialized node *list, but didn't do anything to it (i.e didn't assign list->data a value), how would I check if it's empty?

I tried if (node == NULL){break} but didn't work.

Thanks for the help!

linked-list c
4 Answers

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.

user_4000560

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;
 }
user_29972510

Sometimes when you create a variable, C will zero out all the data for you. Other times, the variable will contain garbage. You need to learn the rules that govern this, but as a beginner, you should simply be certain always to initialize your variables explicitly.

For a linked list, when you append a node to a list, you should always be certain to set a NULL into the next pointer, so that the list will be properly terminated.

Your linked list should have a "head" pointer. If the head is set to NULL then you have a zero-length linked list; if the head has any value other than NULL you must have at least one node in the linked list, so the list must have length of at least 1.

So, as long as you have been careful about initializing your head pointer to NULL you can trivially tell whether the list is empty by checking to see if the head pointer is NULL.

But your question was really about the data member variable. There will always be some sort of value in there. As I said, sometimes C will set it to zero for you, but other times it will be unpredictable garbage (a value that could be any integer value). You need to initialize that to a sensible default when you allocate a new node. For example, the valid values of data might all be greater than zero, so you might set data to zero to indicate that it is currently empty.

You can write a simple loop that traverses your linked list and checks each data member, and return true if it finds any data that is not zero (or whatever special value flags that it is unused). It should return false if it finds only default data or if the list is zero length.

user_1669490
Related