Reversing a linked list and adding/removing nodes

Question

I am new to C and have written this code just to teach myself how to work with linked lists and was hoping someone could review it and give me any comments or tips for efficiency, etc. The code just creates a list, adds and removes nodes from the list, and can reverse the list.

/* Creates a linked list, adds and removes nodes and reverses list */
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
typedef bool;
#define false 0
#define true 1 
typedef struct node {
 int value;
 struct node *next;
} node;
node *head = NULL; //Contains entire list
node *current = NULL; //Last item currently in the list
// Initialize list with input value
struct node* create_list(int input)
{ 
 node* ptr;
 printf("Creating a LinkedList with head node = %d\n", input);
 ptr = (node*)malloc(sizeof(node)); // Allocating 8 bytes of memory for type node pointer
 if (ptr == NULL) // Would occur is malloc can't allocate enough memory
 {
 printf("Node creation failed \n");
 return NULL;
 }
 ptr->value = input;
 ptr->next = NULL;
 head = current = ptr;
 return ptr;
}
// Add input value to the end of the list
struct node* add_to_end(int input)
{
 node* ptr;
 if (head == NULL)
 {
 return create_list(input);
 }
 ptr = (struct node*)malloc(sizeof(struct node));
 if (ptr == NULL)
 {
 printf("Node creation failed \n");
 return NULL;
 }
 else
 {
 ptr->value = input;
 ptr->next = NULL; // End value in list should have NULL next pointer
 current -> next = ptr; // Current node contains last value information
 current = ptr;
 }
 printf("%d Added to END of the LinkedList.\n", input);
 return head; 
}
// Add input value to the head of the list
struct node* add_to_front(int input)
{
 node* ptr;
 if (head == NULL)
 {
 return create_list(input);
 }
 ptr = (struct node*)malloc(sizeof(struct node));
 if (ptr == NULL)
 {
 printf("Node creation failed \n");
 return NULL;
 }
 else
 {
 ptr->value = input;
 ptr->next = head; // Point next value to the previous head
 head = ptr; 
 }
 printf("%d Added to HEAD of the LinkedList.\n", input);
 return head;
}
// Return the number of items contained in a list
int size_list(node* ptr)
{
 int index_count = 0;
 while (ptr != NULL)
 {
 ++index_count;
 ptr = ptr->next;
 }
 return index_count;
}
// Add an input value at a user-specified index location in the list (starting from 0 index)
struct node* add_to_list(int input, int index)
{
 node* ptr_prev = head;
 node* ptr_new;
 int index_count; // Used to count size of list
 int index_track = 1; // Used to track current index
 ptr_new = (struct node*)malloc(sizeof(struct node));
 // Check that list exists before adding it in
 if (head == NULL)
 {
 if (index == 0) // Create new list if 0 index is specified
 {
 add_to_front(input);
 }
 else
 {
 printf("Could not insert '%d' at index '%d' in the LinkedList because the list has not been initialized yet.\n", input, index);
 return NULL;
 }
 }
 // Count items in list to check whether item can added at specified location
 if ((index_count = size_list(head)) < index)
 {
 printf("Could not insert '%d' at index '%d' in the LinkedList because there are only '%d' nodes in the LinkedList.\n", input, index, index_count);
 return NULL;
 }
 //Go through list -- stop at item before insertion point
 while (ptr_prev != NULL)
 { 
 if (index == 0) // Use add_to_front function if user-specified index is 0 (the head of the list)
 {
 add_to_front(input);
 return head;
 }
 if ((index_track) == index) 
 { 
 break;
 }
 ptr_prev = ptr_prev ->next;
 ++index_track;
 }
 ptr_new ->next = ptr_prev ->next; // Change the new node to point to the original's next pointer
 ptr_new->value = input;
 ptr_prev ->next = ptr_new; // Change the original node to point to the new node
 return head;
}
// Verify if the list contains an input value and return the pointer to the value if it exists
struct node* search_list(int input, struct node **prev)
{
 node* ptr = head;
 node* temp = (node*)malloc(sizeof(node));
 bool found = false;
 // Search if value to be deleted exists in the list
 while (ptr != NULL)
 {
 if(ptr->value == input)
 {
 found = true;
 break;
 }
 else
 {
 temp = ptr;
 ptr = ptr ->next;
 }
 }
 // If the value is found in the list return the ptr to it
 if(found == true)
 {
 if(prev)
 *prev = temp;
 return ptr;
 }
 else
 {
 return NULL;
 }
}
// Remove an input value from the list
struct node* remove_from_list(int input)
{
 node* prev = NULL; // list starting from one item before value to be deleted
 node* del = NULL; // pointer to deleted value
 // Obtain pointer to the list value to be deleted
 del = search_list(input, &prev);
 if(del == NULL)
 {
 printf("Error: '%d' could not be deleted from the LinkedList because it could not be found\n");
 return NULL;
 }
 else
 {
 if (prev != NULL)
 {
 prev->next = del->next;
 }
 if (del == current) // If item to be deleted is last in list, set the current last item as the item before deleted one
 {
 current = prev;
 }
 else if (del == head) // If item to be deleted is the head of the list, set the new head as the item following the deleted one
 {
 head = del ->next;
 }
 return head;
 }
}
// Reverse the order of the list
struct node* reverse_list() 
{
 node* reverse = NULL;
 node* next = NULL;
 node* ptr = head; 
 if (head == NULL)
 {
 printf("Error: There is no LinkedList to reverse.\n");
 return NULL;
 }
 printf("Reversing order of the LinkedList.\n");
 while (ptr != NULL) 
 {
 next = ptr ->next; // Holds the remaining items in the original list
 ptr ->next = reverse; // List now points to items in reversed list
 reverse = ptr; // Reversed list set equal to the List
 ptr = next; // List re-pointed back to hold list 
 }
 head = reverse;
} 
// Print the list to the console
void print_list()
{
 node* ptr = head;
 printf("------------------------------\n");
 printf("PRINTING LINKED LIST\n");
 while (ptr != NULL)
 {
 printf("%d\n", ptr->value);
 ptr = ptr->next;
 }
 printf("------------------------------\n");
}
int main()
{
 int i;
 reverse_list(); //test function error message
 for (i = 3; i > 0; --i)
 {
 add_to_front(i);
 }
 for (i= 4; i < 7; ++i)
 {
 add_to_end(i);
 }
 add_to_list(4,9); //test function error message
 add_to_list(4,1); 
 print_list(); 
 remove_from_list(3); 
 print_list();
 reverse_list();
 print_list();
 add_to_list(10,0);
 print_list();
 getchar();
}

Answer 1

You code is quite good for a beginner and shows a grasp of how pointers and lists work, so that's great! However, there are a few points I'd like to address.

I'll start by briefly listing what for me are less important issues or some things that others are likely to disagree with, then move on to more problematic errors:

General style:

• Personally, I find that an if statement with a single-line block introduces too much noise. That is, I prefer

  if (condition)
   statement;
  

  to

  if (condition)
  {
   statement;
  }
  

• Since you typedefed struct node as node, you don't have to write struct node all the time.

malloc() issues:

• Don't cast the return value of malloc() unless you're writing C++: see this SO question.
• It's better to write ptr = malloc(sizeof(*ptr)); instead of ptr = malloc(sizeof(node)); because that way the line won't need changing if the type of ptr changes.

Bigger problems:

• Globals: head and current seem to be global objects in your program, making all of the functions you wrote impossible to reuse. This impedes the usefulness of your list data structure. It is generally a good idea not to have any read-write globals at all, but read-only globals like conversion tables and constants are usually fine.

  For the purposes of an example, let's pretend to delete head and current. Let's look at the functions create_list() and add_to_end():

  // Initialize list with input value
  node* create_list(int input)
  { 
   node *ptr = malloc(sizeof(*ptr)); // Allocating 8 bytes of memory for type node pointer
   if (ptr == NULL) // Would occur is malloc can't allocate enough memory
   return NULL;
   ptr->value = input;
   ptr->next = NULL;
   return ptr;
  }
  

  The function merely creates a new list node and returns it, unless there's an error. Then, we can query the return value to determine if the creation of the list was successful:

  node *head = create_list(7);
  if (head == NULL)
   some_kind_of_error_handling_here();
  

  The same goes for add_to_end():

  // Add input value to the end of the list
  node* add_to_end(node *head, int input)
  {
   if (head == NULL)
   return NULL;
   // Find the last element of the list
   while(head->next != NULL)
   head = head->next;
   node *ptr = malloc(sizeof(*ptr));
   if (ptr == NULL)
   return NULL;
   ptr->value = input;
   ptr->next = NULL; // End value in list should have NULL next pointer
   // Attach new node to the end of the list.
   head->next = ptr;
   return ptr; 
  }
  

  Now we find the last element, attach a new node to it (unless malloc() fails) and as a bonus return a pointer to it. Actually, a lot of this code looks familiar, so we can do better:

  node* add_to_end(node *head, int input)
  {
   if (head == NULL)
   return NULL;
   node *ptr = create_list(input);
   if (ptr == NULL)
   return NULL;
   // Find the last element of the list
   while(head->next != NULL)
   head = head->next;
   // Attach new node to the end of the list.
   head->next = ptr;
   return ptr; 
  }
  

  Two things should be noted here: 1) We enabled code reuse by (the call to create_list()) by eliminating the globals and 2) that its possible to think of a list as consisting of a head and the rest, which is also a list.

• Memory leaks: Every object allocated using malloc() and friends must be deallocated using free(). The best way to deallocate the list memory would be to provide a function like delete_list().

• Separation of concerns: It is generally a good idea not to mix code that manipulates data with input or output code. It is best to return an error code from functions that may fail and test for it in the caller. Doing this will not only make things easier to change later (for example, should we need to log errors to a file instead of print them out) but also make the functions shorter and easier to understand.

• sammis: can you show me some code that you would have written instead to address the Globals and Separation of concerns issues? I understand your reasoning, just not sure how to actually implement the changes. Thanks!
• idoby: @sammis: Sure! I added some discussion of how to get rid of the globals and will add more examples later.
• sammis: thanks so much! I'm having a problem when I don't cast the malloc. Changing to node* ptr = malloc(sizeof(*ptr)); gives me the error: a value of type "void*" cannot be assigned to an entity of type "node*"
• William Morris: Are you compiling it as a C++ file (eg suffix .cc - should be just .c)
• idoby: In order to compile the code as C, you should add the flags -pedantic and one of -ansi for C89 or -std=c99 for C99 to your compiler invocation. Since we used C99 features, you should go for C99. (the features include // comments and declaring variables mid-block)

Answer 2

I would suggest you run this program through valgrind. Looks like you are leaking memory without any frees for the mallocs.

EDIT: (In regards to calling a function from another file) To call a function from another file (say foo.c) you separate your linked list code into header and implementation files (say linked_list.h and linked_list.c).

For example, in linked_list.h there would be the function prototype for create_list:

node* create_list(int input);

Then in in linked_list.c, at the top of the file you would include linked_list.h:

#include "linked_list.h"

and there would also be the implementation in linked_list.c:

node* create_list(int input) { ... }

Then in foo.c, you would include and call the code:

#include "linked_list.h"
...
node* bar = create_list(my_number);
...

Answer 3

Just a few additional notes to the already existing answers:

Your checks to for NULL pointers:

if (ptr == NULL)
while (ptr != NULL)

Could be simplified to:

if (!ptr)
while (ptr)

---

To quote @busy_wait:

Memory leaks: Every object allocated using malloc() and friends must be deallocated using free(). The best way to deallocate the list memory would be to provide a function like delete_list().

When you do free the allocated memory, make sure to set the pointer you free to NULL, so that you do not try to access the memory at that point again.

• idoby: Actually, some toolchains (embedded stuff) don't define NULL to be 0. It might not be standard, but they do. So IMHO it's better to test pointers for nullity explicitly and also makes more philosophical sense (is a pointer a condition?).
• icktoofay: @busy_wait: While some machines may use a non-zero address to indicate a null pointer, as far as I know, compilers are required to translate a constant 0 into whatever a null pointer is and treat a whatever a null pointer is as zero when it comes to comparisons.
• idoby: Does that apply when the zero doesn't appear in the code, like in if (!ptr)? I don't know. I still think it's better to test for NULL explicitly (also conveys intent better IMO).

Answer 4

As a simple list, what you have written in quite nice. If you were writing this for a purpose (ie. to be used by someone) then your list has some shortcomings. First among these is the use of globals for head/tail. This restricts the list to a single instance. A better approach is to make the functions operate on any list supplied as a parameter. What should the parameter be? To mirror what you have written, you would need to pass the addresses of the head and tail pointers of the list to each function. This is a little inelegant. Alternatively you could either:

1. pass a pointer to one node in the list (nominally the head, but not necessarily);

2. or create a list structure holding the head, tail and maybe the member count of the list.

Option 1 is the simplest and is often enough. It has the drawback that adding nodes to the tail requires the list to be traversed. But depending upon the application, that might not matter (adding to the head might be sufficient).

Option 2 means that you need a structure such as:

typedef struct {
 int length;
 Node *head;
 Node *tail;
} List;

This can then be instantiated on the stack:

List list1 = {
 .length = 0,
 .head = NULL,
 .tail = NULL
};
// or 
List list2 = {0, NULL, NULL};

or created and initialised by a new_list() function.

The you can pass around the list, for example:

int list_append(List *list, int value) {...}

---

Code Duplication

You use malloc to create a node in four places (five if we include search_list, but that one is an error). Instead you should write a function that is called wherever a new node is needed:

static node* new_node(node *next, int value)
{
 node *n = malloc(sizeof *n);
 if (n) {
 n->next = next; // pass NULL if the correct value is not avaialable
 n->value = value;
 }
 return n;
}

Note that I used the name value, the same as the structure field, instead of input. It is better to use a single name for an entity wherever possible.

Note also that my pointers are written without spaces around the ->. Although you might prefer to add spaces, that might mark you out as a novice.

---

I won't comment much on the function details as they rely on the globals discussed above. However,

• add_to_list looks much too long and it traverses the whole list to find the position required instead of just traversing up the the required index.

• search_list should be rewritten without a malloc call and without the boolean type (note that bool is defined in stdbool.h, but it is unnecessary here). (Note also that your typedef bool should read typedef int bool - the compiler should have warned you about that).

  Without using a boolean, the main loop can be:

   while (ptr != NULL && ptr->value != input) {
   ptr = ptr ->next;
   }
   if (ptr != NULL) { // ptr not NULL means the value was found
   ...
   }
  

  The interface of this function is a bit odd in that a return parameter holds a pointer to the previous node. If the searched-for value is the head of the list, this parameter receives a pointer to the malloced temp node, which is clearly wrong. I can see that you wanted to return the previous node so that remove_from_list can use it, but the result is inelegant. An alternative might be for search_list to take a delete parameter that says whether to delete the node (that too is inelegant) or for remove_from_list to duplicate the while loop above.

• Note that reverse_list lacks a return value

---

Some other minor comments:

• Functions with no parameters should take a void parameter list.

• You mix use of node and struct node. While not an error, this inconsistency is undesirable.

• With C99 it is possible to define variables at the point of first use. This is generally preferable.

• Many of your comments are unnecessary

• I disagree with busy_wait's preference for brace-less single-line statements. Adding braces is ugly but prevents a class of error - adding an extra line of code that is not actually part of the conditional:

  if (condition) 
   do_something;
   do_something_else(); // this is not part of the conditional, although
   // it appears to be.
  

• Make sure to enable warnings in the compiler (eg -Wall in gcc) and resolve all warnings.

• sammis: for you comment on add_to_list, how would you traverse indices without going through the list along with it?
• William Morris: I was a bit unclear - your code first traverses the whole list (in the call to size_list) and then traverses again up to the required index. It only needs to do the second part.