Implementation of some functions of a linked list

Question

I have implemented few functions of a linked list. Feedback is welcome. Please note I have specifically avoided using pointer to pointers.

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

// Node data structure inside the linked list.
struct node {
   int data;
   struct node* next;
};

struct node* BuildOneTwoThree(void);
void printList(struct node  * head);
int getListLength(struct node * head);
struct node* insertAtFront(struct node * const head, int value);
int getAt(struct node *  head, int index, int *);
struct node* insertAtBack(struct node* head, int value);

int main() {

  // Create sample linked list and obtain pointer to the head.
  struct node * head = NULL; 
  head = insertAtBack(head, 700);
  head = insertAtFront(head, 12);
  head = insertAtFront(head, 3);
  head = insertAtFront(head, 5);
  head = insertAtFront(head, 55);
  head = insertAtBack(head, 333);

  printList(head);

  printf("List length is: %d\n", getListLength(head));

  return 0;  
}

///
//
// Create a sample linked list with three nodes
// connected to each other.
//
// Parameter:
//  nothing.
// Return
//  pointer to the head of the linked list that was built.
//
struct node* BuildOneTwoThree(void)
{
  struct node * one = NULL;
  struct node * two = NULL; 
  struct node * three = NULL;

  //
  // Allocate memory for (three) nodes
  //
  one = malloc(sizeof(struct node));
  if(one == NULL) return NULL;

  two = malloc(sizeof(struct node));  
  if(two == NULL)
  {
    free(one);
    return NULL;
  }

  three = malloc(sizeof(struct node));
  if(three == NULL)
  {
    free(one);
    free(two);
    return NULL;
  }

  // Set data values for each node
  one->data = 1;
  two->data = 2;
  three->data = 3;

  // Chain nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // Return pointer to head node
  return one;


}

///
//
// Print contents of each node in the linked list.
//
// Parameter:
//  head: pointer to the head of the node
// Return
//  nothing. Prints content of each node on console.
//
void printList(struct node * head)
{

   int i = 0;
   int x = 0;

   // If the list is empty, there is nothing to print.
   if(NULL == head)
     return;    

   // First let's get number of nodes in the linked list.
   int length = getListLength(head);

   // Let's iterate over the nodes now.
   for(i = 0; i<length; i++)
   {
     // Get value of i-th node
     if(-1 == getAt(head, i, &x))
          break;

     printf("%d \n", x);

   }
}


///
//
// Get number of nodes in the linked list.
//
// Parameter:
//  head: pointer to the head of the node
// Return
//  number of nodes in the linked list.
//
int getListLength(struct node * head)
{

   int size = 0;

   // If head pointer is NULL - the size of the list is 0.
   if(NULL == head)
     return size;   


   while(1)
   {
     // Since head is not NULL, there is at least one node in the list.
     size++;

     // Move to the next node
     head = head->next;

     // If the next node is NULL, stop.
     if(head == NULL) 
    return size;
   }


}

///
//
// Insert new node in the beginning of the linked list.
//
// Parameter:
//  head: pointer to the head of the node
//  value: value for the new linked list node
// Return
//  Pointer to the linked list which contains the added node in the beginning.
//
struct node* insertAtFront(struct node * const head, int value)
{

    // Create a new node - and check if creation was success
    struct node* result = malloc(sizeof(struct node));
    if(result == NULL) return NULL;

    result->next = NULL;

    // If head is NULL, just return the new node.
    if(head == NULL)
    {
       result->data = value;
       return result;
    }   

    // Otherwise make the new node point where head was pointing, and return the new node as new head
    result->next = head;
    result->data = value;
    return result;


}


///
//
// Get element at some index. Index starts from 0.
//
// Parameter:
//  head: pointer to the head of the node
//  index: 0 based index of element we wish to retrieve
//  value: [out] parameter where the value of the node found will be written
// Return
//  -1 on error 0 on success.
//
int getAt(struct node  * head, int index, int * value)
{

   int currIndex = 0;

   // Make sure requested index of element is not out of bounds
   if(index >= getListLength(head))
     return -1;

   // If the head pointer is NULL, there is no point in searching further.
   if(head == NULL)
   {
      return -1;
   }

   // Start an infinite loop
   while(1)
   {
     if(index == currIndex)
     {
    *value = head->data; // Return value of the index-th element
        return 0;   
     }

     head = head->next;

     currIndex++;

   }


}



struct node* insertAtBack(struct node* head, int value)
{

    struct node * current = head;

    int length = 0;
    int i = 0;

    // Create a new node - and check if creation was success
    struct node* result = malloc(sizeof(struct node));
    if(result == NULL) return NULL;

    result->next = NULL;
    result->data = value;  

    // If initial list is empty just return the new node.
    if(current == NULL)
    {
        return result;
    }

    // Get list length
    length = getListLength(current);


    for(i = 0; i < length - 1; i++)
    {
      current = current->next;
    }

    current->next = result;

    return head;


}

Answer 1

Doing extra work in printList

The thing that most catches my eye, is that in printList, you first get the length of the list, then iterate over it, calling getAt on every iteration:

 int length = getListLength(head);
 for(i = 0; i<length; i++) {
     if(-1 == getAt(head, i, &x))
          break;

This means that you're iterating starting from the beginning again and again for every node in the list, i.e. doing \$O(n^2)\$ work, instead of \$O(n)\$ which would be enough for simply iterating over the list.

The point of a linked list is that you don't need to know where the end is when you start walking it, and that you can hold valid pointers to the nodes in the middle and do something useful with them. Here, every operation starts from head instead.

For printing, I'd rather make a loop similar to when you count the nodes:

struct node *p = head;
while(p) {
    printf("%d\n", p->value); // or count here
    p = p->next;
}

I changed the while(1) loop on purpose, I feel putting the test in the while statement makes it more readable, since there is only one exit condition anyway. Also, you don't need a separate if for head == NULL, since while does the test first.

Always starting from head

In addition to printList, the other functions you have, also always take the head node. For insertAtFront this is obvious, and you might want an insertAtBack function too that can start from the head. But what about inserting in the middle, in an arbitrary point? The (theoretical) advantage of linked lists is that insertion is \$O(1)\$, and as above, always searching from the beginning thrashes that.

So, in the least, you should add a function for inserting after a given node, something like

struct node *insertHere(struct node *here, struct node *newone) {
    newone->next = here->next;
    here->next = newone;
}

Also, I'd separate the functions of creating a node, and inserting a node at a given point, since there might well be cases where you just want to move a given node from one list to another, and doing a malloc/free pair at that point is a waste.

What if the list is empty

The funny thing is, that having a head pointer that is NULL when the list is empty, seems natural, but it requires always checking if the list is empty. You can see this in that the insertion functions specifically test for head == NULL, and you have to assign to head in the main program after calling them. It also makes adding in the middle a bit difficult, since if the list is empty, you'd need to change the head pointer (to point to the newly added item), but if it isn't empty, you don't want to touch head at all, for efficiency's sake. A bit of a conundrum, I'd say.

One solution would be to make a separate structure for the list in general, which would contain a pointer to the first item, and possibly some metadata about the list. (e.g. it could cache the list size if that is often needed, and a pointer to the last item to make it faster to add at the end.)

That has the downside that all additions would require handing out a pointer to the main structure, and the node being operated on. Having no actual nodes would still be a special case, too.

Another way is to just demand that the list never be empty(!). This is easiest to do by having a node that contains some invalid value (a sentinel node), something that is skipped by all functions actually handling the data. Sounds like a bit of a waste, though it's just a trivial version of a separate main structure, with the advantage that this time all the structs and pointers would be the same type.

(Or rather, build the list functions such that they don't handle empty lists. The application program could of course have a pointer to a list node, that happens to be NULL.)

Answer 2

You are not lazy enough, keep the code slim.

int getListLength(struct node * list)
{
   int size = 0;
   while(list != null)
   {
     size++;
     list = list->next;
   }
   return size;
}

struct node* insertAtFront(struct node * const head, int value)
{
    struct node* result = malloc(sizeof(struct node));
    if(result == NULL) return NULL; // hmmm

    result->next = head;
    result->data = value;
    return result;
}

struct node* insertAtBack(struct node* head, int value)
{
    struct node* result = malloc(sizeof(struct node));
    if(result == NULL) return NULL;

    result->next = NULL;
    result->data = value;  

    if (head == NULL)
    {
         return result;
    }
    struct node * current = head;
    while (current->next != NULL)
    {
         current = current->next;
    }
    current->next = result;
    return head;
}

// For comparison using an alias, pointer to pointer
struct node* insertAtBack(struct node* head, int value)
{
    struct node ** current = &head;
    while (*current != null)
    {
      current = &(*current)->next;
    }
    struct node* result = malloc(sizeof(struct node));
    if(result == NULL) return NULL;

    result->next = NULL;
    result->data = value;  
    *current = result;
    return head;
}

struct node* insertOrdered(struct node* head, int value)
{
    struct node ** current = &head;
    while (*current != null && value < (*current)->value)
    {
      current = &(*current)->next;
    }
    struct node* result = malloc(sizeof(struct node));
    if(result == NULL) return NULL;

    result->next = *current;
    result->data = value;  
    *current = result;
    return head;
}

Answer 3

First of all, I would get rid of struct keyword and append const to constant pointers.

While getAt returns non-value, but successful status, I would name it tryGetAt and change type of result to bool. It makes you intentions clearer.

node* BuildOneTwoThree(void);
void printList(const node* head);
int getListLength(const node* head);
node* insertAtFront(node* head, int value);
bool tryGetAt(const node* head, int index, int *value);
node* insertAtBack(node* head, int value);
node* insertInTheMiddle(node* head, int index, int value);

Well. Functions printList, getListLength contains the list word, but other functions aren't. It's better to name functions with same rules, f.e. list_print, list_get_length, list_insert_at_front and so on. Cause you like camel-case, they may be listPrint, listGetLength etc. BuildOneTwoThree seems test function but anyway — listCreate123. The in InsertInTheMiddle is not necessary.

node* listCreate123(void);
void listPrint(const node* head);
int listGetLength(const node* head);
node* listInsertAtFront(node* head, int value);
bool tryGetAt(const node* head, int index, int *value);
node* listInsertAtBack(node* head, int value);
node* listInsertInMiddle(node* head, int index, int value);

Now, the code of listCreate123 is too complex and volatiles the DRY principle. Let add simple helper function createNode:

static node* createNode(int data, node* next)
{
  node* result = malloc(sizeof(node));

  if(result == NULL)
    return NULL;

  result->data = data;
  result->next = next;

  return result;
}

node* listCreate123(void)
{
    return createNode(1, createNode(2, createNode(3, NULL)));
}

Wow. Shorter and simpler.

Now listPrint. Typical Shlemiel the painter's algorithm. Rewrite to make the implementation O(n) instead of O(n²).

void listPrint(const node* head)
{
   while(head != NULL)
   {
      printf("%d\n", head->data);
      head = head->next;
   }
}

Similar listGetLength:

void listGetLength(const node* head)
{
   int result = 0;

   while(head != NULL)
   {
      result++
      head = head->next;
   }

   return result;
}

More complex tryGetAt:

bool tryGetAt(const node* head, int index, int* value)
{
  if(index < 0 || head == NULL)
    return false;

  while(index-- > 0)
  {
    head = head->next;

    if(head == NULL)
      return false;
  }

  *value = head->data;
  return true;
}

Three insertion function. listInsertAtFront is very simple:

node* listInsertAtFront(node* head, int value)
{
  return createNode(value, head);
}

listInsertAtBack and listInsertInMiddle both are require helper internal function insertAfter:

void listInsertAfter(node* before, int value)
{
  before->next = createNode(value, before->next);
}

node* listInsertAtBack(node* head, int value)
{
  if(head == NULL)
    return NULL;

  node* last = head;

  while(last->next != NULL)
    last = last->next;

  listInsertAfter(last, value);

  return head;
}

node* listInsertInMiddle(node* head, int index, int value)
{
  if(index < 0 || head == NULL)
    return NULL;

  node* current = head;

  while(index-- > 0)
  {
    current = current->next;

    if(current == NULL)
      return NULL;
  }

  listInsertAfter(current, value);

  return head;
}

Finally, listFree. You should free every nodes in list, so:

void listFree(node* head)
{
  while(head != NULL)
  {
    node* tmp = head->next;
    free(head);
    head = tmp;
  }
}