My linked list implementation in C

Question

I have been reading about pointers in C and I thought implementing a linked list would be a good exercise to test my knowledge.

Below is my code and it is 100% functional. All I am looking for is some criticism, such as how to make the functions more efficient or defining *pointerToLinkedList in a better spot.

#include <stdio.h>
#include <stdlib.h>

//Structure represents a node of a Linked List
struct node {
    int data;
    struct node* link;
};

//Pointer to the head node
struct node *pointerToLinkedList = NULL;

//Function inserts a new node at the beginning of the linked list
void insertNodeBeginning(int aData){
    //pointer to the new node
    struct node *newNode = (struct node*) malloc(sizeof(struct node));

    //fill in data in new node
    newNode->data = aData;
    //point new node to the previous head (now second node in linked list)
    newNode->link = pointerToLinkedList;

    //adjust pointerToLinkedList accordingly with the new head
    pointerToLinkedList = newNode;
}

//Function inserts a new node at the end of the linked list
void insertNodeEnd(int aData){

    //pointer to the new node
    struct node *newNode = (struct node*) malloc(sizeof(struct node));

    //fill in data in new node
    newNode->data = aData;
    //point new node to NULL, because its last node in list
    newNode->link = NULL;

    //link second last node to the newly created last node of the linked list
    //start at beginning of list
    struct node *secondLastNode = pointerToLinkedList;
    //loop until it becomes second last
    while(secondLastNode->link != NULL){
        secondLastNode = secondLastNode->link;
    }
    //actual linking
    secondLastNode->link = newNode;
}

//Function deletes node at the beginning of the linked list
void deleteHead(){

    //get reference of the head that will be deleted
    struct node *temp = pointerToLinkedList;

    //adjust pointerToLinkedList to the new head (previously the second node)
    pointerToLinkedList = pointerToLinkedList->link;

    //free memory of the old head       
    free(temp);
}

//Function deletes node at the end of the linked list
void deleteTail(){

    //get reference of the head to iterate through linked list
    struct node *temp = pointerToLinkedList;
    struct node *newTail;

    //iterate through linked list
    while(temp->link != NULL){
        newTail = temp;
        temp = temp->link;
    }

    //free memory of old tail
    free(newTail->link);

    //adjust the new tail and point it to NULL
    newTail->link = NULL;
}

Two more things apart from the criticism:

1. Am I using the free() function properly? Is the structure actually being removed from the dynamic memory?

2. What other functions apart from the four currently installed, would you recommend to implement as an exercise?

Answer 1

1. I suggest you rename link to next which is a more conventional name for the next linked list node.

   struct node {
       int data;
       struct node* link;
   };
   

2. Currently, you have to write the type of the node as struct node. However, if you do:

   typedef struct node {
       int data;
       struct node* link;
   } node;
   

   You can allocate a new node simply by writing node my_node;

3. No, no, no and no. Don't you ever use global variables. As the code base grows, if something goes wrong because of a global variable, debugging will be hell.

   struct node *pointerToLinkedList = NULL;
   

4. You should not cast the result of malloc:

   struct node *newNode = (struct node*) malloc(sizeof(struct node));
   

5. What comes to struct node *newNode = (struct node*) malloc(sizeof(struct node)), I suggest you write instead:

   malloc(sizeof *newNode)
   

   That way, if you change the type of *newNode to, say, some_funky_struct, you don't have to rewrite malloc(sizeof(struct node)) to malloc(sizeof(struct some_funky_struct)).

6. There is no pointer to the tail of your list. You define one (called, say, list_tail), you can insertNodeEnd in constant time.

7. I suggest you rename it to list_head, since that is a conventional name for the first node of a linked list.

   struct node *pointerToLinkedList = NULL;
   

8. Normally, what you would do when implementing a singly-linked list is creating a following:

   typedef struct linked_list_node_t {
       void* datum;
       struct linked_list_node_t* next;
   } linked_list_node;
   
   typedef struct linked_list_t {
       linked_list_node_t* head;
       linked_list_node_t* tail;
       size_t size;
   } linked_list_t;
   
   linked_list_t* linked_list_t_alloc() {
       linked_list_t* list = malloc(sizeof *list);
   
       if (!list) {
           abort();
       }
   
       list->head = NULL;
       list->tail = NULL;
       list->size = 0;
       return list;
   }
   
   linked_list_t_operation(linked_list_t* list, ... operands) {
       ... Your implementation.
   }
   

9. Alternative implementation

   You could do:

   singly_linked_list.h

   #ifndef SINGLY_LINKED_LIST_H
   #define SINGLY_LINKED_LIST_H
   
   #include <stdlib.h>
   
   typedef struct singly_linked_list_node_t {
       int datum;
       struct singly_linked_list_node_t* next;
   } singly_linked_list_node_t;
   
   typedef struct singly_linked_list_t {
       singly_linked_list_node_t* head;
       singly_linked_list_node_t* tail;
       size_t size;
   } singly_linked_list_t;
   
   typedef struct singly_linked_list_iterator_t {
       singly_linked_list_node_t* next_node;
   } singly_linked_list_iterator_t;
   
   /******************************************
   * Allocates and returns a new empty list. *
   ******************************************/
   singly_linked_list_t* singly_linked_list_alloc();
   
   /**********************
   * Initializes a list. *
   **********************/
   int singly_linked_list_init(singly_linked_list_t* list);
   
   /*************************
   * Frees the entire list. *
   *************************/
   void singly_linked_list_free(singly_linked_list_t* list);
   
   /***************************
   * Clears the list content. *
   ***************************/
   void singly_linked_list_clear(singly_linked_list_t* list);
   
   /**********************************************
   * Pushes a new datum to the head of the list. *
   **********************************************/
   int singly_linked_list_push_front(singly_linked_list_t* list, int datum);
   
   /**********************************************
   * Pushes a new datum to the tail of the list. *
   **********************************************/
   int singly_linked_list_push_back(singly_linked_list_t* list, int datum);
   
   /*****************************
   * Pops the head of the list. *
   *****************************/
   int singly_linked_list_pop_front(singly_linked_list_t* list);
   
   /*****************************
   * Pops the tail of the list. *
   *****************************/
   int singly_linked_list_pop_back(singly_linked_list_t* list);
   
   /**********************************************
   * Returns the number of elements in the list. *
   **********************************************/
   size_t singly_linked_list_size(singly_linked_list_t* list);
   
   /**************************************
   * Returns the iterator over the list. *
   **************************************/
   singly_linked_list_iterator_t*
   singly_linked_list_get_iterator(singly_linked_list_t* list);
   
   /******************************************************************
   * Returns non-zero value if the iterator has something to remove. *
   ******************************************************************/
   int singly_linked_list_iterator_has_next(singly_linked_list_iterator_t* iterator);
   
   /**************************
   * Returns the next datum. *
   **************************/
   int singly_linked_list_iterator_next(singly_linked_list_iterator_t* iterator);
   
   #endif /* SINGLY_LINKED_LIST_H */
   

   singly_linked_list.c

   #include "singly_linked_list.h"
   #include <stdlib.h>
   
   singly_linked_list_t* singly_linked_list_alloc()
   {
       return calloc(1, sizeof(singly_linked_list_t));
   }
   
   int singly_linked_list_init(singly_linked_list_t* list)
   {
       if (!list)
       {
           return 0;
       }
   
       list->head = NULL;
       list->tail = NULL;
       list->size = 0;
       return 1;
   }
   
   void singly_linked_list_free(singly_linked_list_t* list)
   {
       if (list)
       {
           singly_linked_list_clear(list);
           free(list);
       }
   }
   
   void singly_linked_list_clear(singly_linked_list_t* list)
   {
       singly_linked_list_node_t* current_node;
       singly_linked_list_node_t* next_node;
   
       if (!list)
       {
           return;
       }
   
       current_node = list->head;
   
       while (current_node)
       {
           next_node = current_node->next;
           free(current_node);
           current_node = next_node;
       }
   
       list->head = NULL;
       list->tail = NULL;
       list->size = 0;
   }
   
   int singly_linked_list_push_front(singly_linked_list_t* list, int datum)
   {
       singly_linked_list_node_t* new_node;
   
       if (!list)
       {
           return 0;
       }
   
       new_node = malloc(sizeof *new_node);
   
       if (!new_node)
       {
           return 0;
       }
   
       new_node->datum = datum;
   
       if (list->size == 0)
       {
           list->head = new_node;
           list->tail = new_node;
       }
       else
       {
           new_node->next = list->head;
           list->head = new_node;
       }
   
       list->size++;
       return 1;
   }
   
   int singly_linked_list_push_back(singly_linked_list_t* list, int datum)
   {
       singly_linked_list_node_t* new_node;
   
       if (!list)
       {
           return 0;
       }
   
       new_node = malloc(sizeof *new_node);
   
       if (!new_node)
       {
           return 0;
       }
   
       new_node->datum = datum;
   
       if (list->size == 0)
       {
           list->head = new_node;
           list->tail = new_node;
       }
       else
       {
           list->tail->next = new_node;
           list->tail = new_node;
       }
   
       list->size++;
       return 1;
   }
   
   int singly_linked_list_pop_front(singly_linked_list_t* list)
   {
       int result;
       singly_linked_list_node_t* node;
   
       if (!list)
       {
           abort();
       }
   
       if (list->size == 0)
       {
           abort();
       }
   
       result = list->head->datum;
       node = list->head;
       list->head = list->head->next;
       list->size--;
   
       if (!list->head)
       {
           list->tail = NULL;
       }
   
       free(node);
       return result;
   }
   
   int singly_linked_list_pop_back(singly_linked_list_t* list)
   {
       int result;
       singly_linked_list_node_t* current_node;
       singly_linked_list_node_t* previous_node;
   
       if (!list)
       {
           abort();
       }
   
       if (list->size == 0)
       {
           abort();
       }
   
       current_node = list->head;
       previous_node = NULL;
   
       while (current_node->next)
       {
           previous_node = current_node;
           current_node = current_node->next;
       }
   
       result = current_node->datum;
   
       if (!previous_node)
       {
           list->head = NULL;
           list->tail = NULL;
       }
       else
       {
           previous_node->next = NULL;
           list->tail = previous_node;
       }
   
       list->size--;
       free(current_node);
       return result;
   }
   
   size_t singly_linked_list_size(singly_linked_list_t* list)
   {
       if (!list)
       {
           abort();
       }
   
       return list->size;
   }
   
   singly_linked_list_iterator_t*
   singly_linked_list_get_iterator(singly_linked_list_t* list)
   {
       singly_linked_list_iterator_t* iterator;
   
       if (!list)
       {
           return NULL;
       }
   
       iterator = malloc(sizeof *iterator);
   
       if (!iterator)
       {
           return NULL;
       }
   
       iterator->next_node = list->head;
       return iterator;
   }
   
   int singly_linked_list_iterator_has_next(singly_linked_list_iterator_t* iterator)
   {
       if (!iterator)
       {
           abort();
       }
   
       return iterator->next_node != NULL;
   }
   
   int singly_linked_list_iterator_next(singly_linked_list_iterator_t* iterator)
   {
       int result;
   
       if (!iterator)
       {
           abort();
       }
   
       if (!singly_linked_list_iterator_has_next(iterator))
       {
           abort();
       }
   
       result = iterator->next_node->datum;
       iterator->next_node = iterator->next_node->next;
       return result;
   }
   

   (Demo driver is here.)

10. A weakness of a singly-linked list is that we have to scan the entire list whenever popping the back in order to find the second last node. I suggest you use a doubly-linked list after all since it allows popping the back of the list in \$\Theta(1)\$.

Answer 2

Bugs, so not quite 100% functional.

Bug 1: Consider insertNodeEnd(42);. The following attempts to de-reference NULL. insertNodeEnd() appears to rely on the list having a prior insertion.

struct node *pointerToLinkedList = NULL;
...
struct node *secondLastNode = pointerToLinkedList;
while(secondLastNode->link != NULL){               // !! secondLastNode may be NULL

Bug 2: deleteHead() and deleteTail() have similar problems. Code should handle a deleteHead()/deleteTail() on an empty list.

void deleteHead(){
  struct node *temp = pointerToLinkedList;
  pointerToLinkedList = pointerToLinkedList->link;  // !! pointerToLinkedList may be NULL

Bug 3: (pedantic). Code lacks out-of memory detection and handling.

// struct node *newNode = (struct node*) malloc(sizeof(struct node));
struct node *newNode = malloc(sizeof *newNode);
// add
if (newNode == NULL) TBD_Code();

---

Am I using the free() function properly? Is the structure actually being removed from the dynamic memory?

Yes. Yes.

---

What other functions apart from the four currently installed, would you recommend to implement as an exercise?

void initList(void);  // restore to initial condition (empty the list)
unsigned ListLength(void);
bool ListEmpty(void);  // Is it empty?
bool deleteHead_Save_int(int *); // return success flag (was list not empty?)
bool deleteTail_Save_int(int *); // return success flag (was list not empty?)
bool getHead_Save_int(int *); // return success flag (was list not empty?)
bool getTail_Save_int(int *); // return success flag (was list not empty?)
void printList(FILE *stream, const char *prefix, const char *format, 
    const char *separator, const char *sufffix);
void IterateList(int (*f)(void *, int), void *state); // function on each list node's int

// advanced
void sortList(int (*f)(int,int));

---

... defining *pointerToLinkedList in a better spot.

Rather than support only 1 list, re-architect to support multiple lists.

Consider passing into each function, a pointer to an opaque list type and "hide" implementation details from the user of your functions. Develop a naming convention that begins with the function set's name.

typedef struct F26List_s *F26List;
some_return_type F26List_DoThis(F26List *list,  ...);
some_return_type F26List_DoThat(F26List *list,  ...);

---

[edit]

Re-architecture idea: Presently the single linked list has 4 operations to add to the head/tail and delete form the head/tail. Two of these take O(1) time and 2 of them take O(n) time. By having the tail node point to the head instead of NULL, 3 of these take O(1) time and 1 remains O(n) time. The other change is that rather than keeping track of the head node, code keeps track of the tail node as the head node is then tail->next. No need for a list structure with a head & tail pointer, just a tail pointer.

Answer 3

1. Don't use globals. Currently you rely on the global pointerToLinkedList to be your list head. But that limits you to having only a single linked list. That isn't all the useful. A program may want to have several. It may want to split them, splice them, etc. You can't do that with your design.

2. You have a node type, but no list type. So to go towards having several lists in your program, like I said in #1, let's define one. Fortunately it's fairly simple. The usual abstraction is to just add something like this:

   typedef struct node *list_t;
   

   Now, don't be scared about the fact this hides pointer semantics. We want list_t to be an opaque "value type" of a list handle. The above will do.

3. To continue with #1 and #2, you should pass the list handle to the functions for modifications. I.e.

   void insertNodeBeginning(list_t *list, int aData)
   

   Note the single asterisk. We intend to modify the list. The list handle we design is a value. And we need to pass a pointer to it, in order to allow modification of the handle.

4. Casting the result of malloc is ill-adivsed. Also, don't repeat types so much. A simple newNode = malloc(sizeof *newNode); is correct for whatever pointer type.

5. Rather than have a "delete head" or "delete tail", try going for a "delete position" instead. More general means more uses for it. I.e:

   void deleteAt(list_t *list, struct node* position)
   

   That's not without a price, of course. You must verify the position belongs to the list. But it can also be done as part of looking for the previous node, that you need to preform the deletion.

Answer 4

If insertion/deletion at list end is a thing, you don't want to scan the list from the start each time. Once you keep track of a tail, it makes sense to have a separate list type different from just a pointer to the head. Something like:

struct node {
  struct node *next;
  ...
};

struct list {
  struct note *head, **tail;
};

void init_list (struct list *l)
{
  l->head = NULL;
  l->tail = &head;
}

void insert_at_front (struct list *l, struct node *new_node)
{
  new_node->next = l->head;
  l->head = new_node;
  if (l->tail == &l->head)
    l->tail = &new_node->next;
}

void insert_at_tail (struct list *l, struct note *new_node)
{
  new_node->next = *l->tail; /* or = NULL, but *l->tail can be useful */
  *l->tail = new_node;
  l->tail = &new_node->next;
}

and so on.

Answer 5

@chux and @coderodde did a good job of covering the issues.

The function free() is being used correctly and it is deleting the memory.

The list in the implementation can't be sorted, because the nodes can't be inserted in the middle of the list. The implementation needs a general insertNode() function and a general deleteNode() function. The functions currently in the implementation handle the edge cases or special cases, they don't handle all cases of insertion or deletion. Inserting into the middle or deleting from the middle requires more interesting logic that will keep the linked list intact.