Unsorted List Implemented as a linked structure in C
Header file for a list
//---------------------------------------------------------------
// File: Code111_List.h
// Purpose: Header file for a demonstration of an unsorted list
// implemented as a linked structure.
// Programming Language: C
// Author: Dr. Rick Coleman
//---------------------------------------------------------------
#ifndef CODE111_LIST_H
#define CODE111_LIST_H
#include <stdio.h>
// Define a structure to use as the list item
typedef struct ListItemType
{
int key;
float theData;
struct ListItemType *next;
}ListItem;
// List Function Prototypes
void InitList(); // Initialize the list
void ClearList(); // Remove all items from the list
int Insert(int key, float f); // Add an item to the list
int Delete(int key); // Delete an item from the list
int Search(int key, float *retVal); // Search for an item in the list
int ListLength(); // Return number of items in list
int isEmpty(); // Return true if list is empty
int isFull(); // Return true if list is full
void PrintList(); // Print all items in the list
// Define TRUE and FALSE if they have not already been defined
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!FALSE)
#endif
#endif // End of list header
Implementation (.c) file for a list
//---------------------------------------------------------------
// File: Code111_List.c
// Purpose: Implementation file for a demonstration of an unsorted
// list implemented as a linked structure.
// Programming Language: C
// Author: Dr. Rick Coleman
// Date: January 7, 2002
//---------------------------------------------------------------
#include <stdlib.h> // To get access to malloc()
#include <string.h>
#include "Code111_List.h"
// Declare this as static so no code outside of this source
// can access it.
static ListItem *head; // Declare global pointer to head of the list
//--------------------------------------------
// Function: InitList()
// Purpose: Initialize list to empty. Use only
// with a new list.
// Precondition: List must not contain any
// nodes.
// Returns: void
//--------------------------------------------
void InitList()
{
head = NULL;
}
//--------------------------------------------
// Function: ClearList()
// Purpose: Remove all items from the list
// Returns: void
//--------------------------------------------
void ClearList()
{
ListItem *temp;
if(!isEmpty())
{
temp = head;
// Scan list and free all nodes
while(head != NULL)
{
temp = head;
head = head->next;
free(temp);
}
}
}
//--------------------------------------------
// Function: Insert()
// Purpose: Insert an item into the list at
// the end of the list. See alternate
// code below for insert at the beginning
// of the list.
// Returns: TRUE if insertion was successful
// or FALSE if the insertion failed.
//--------------------------------------------
int Insert(int key, float f)
{
ListItem *temp, *newNode;
// Create a new node and insert the data
newNode = (ListItem *)malloc(sizeof(ListItem));
// Check to see if memory allocation failed
if(newNode == NULL) return FALSE;
// If all OK then insert the data
newNode->key = key;
newNode->theData = f;
newNode->next = NULL; // Very import to init this to NULL
// Check to see if the list is empty
if(isEmpty())
{
// Insert new node as first in the list
head = newNode;
}
else
{
// Find end of the list
temp = head;
while(temp->next != NULL)
temp = temp->next;
// Add this node to the end of the list
temp->next = newNode;
/* Alternate insertion code:
* Since this is an unsorted list an alternate
* insertion approach is to add the new node at
* the head of the list. To do this replace all
* of the code in the else part of this function
* with the following:
*
* newNode->next = head;
* head = newNode;
*/
}
return TRUE; // Signal successful insertion
}
//--------------------------------------------
// Function: Delete()
// Purpose: Delete an item from the list.
// Returns: TRUE if deletion was successful
// or FALSE if the deletion failed.
//--------------------------------------------
int Delete(int key)
{
ListItem *temp, *back;
// Check for empty list
if(isEmpty()) return FALSE;
// Search the list for the item to delete
temp = head;
back = NULL;
// The order of the two conditionals in the while()
// look is VERY important. You want to check first
// to see if temp is NULL before trying to reference
// the memory temp is pointing to. If temp is NULL
// then, because this is a && (AND) condition the
// second condition will never be tested. Testing
// the second condition when temp==NULL will result
// in a crash and burn.
while((temp != NULL) && (key != temp->key))
{
back = temp;
temp = temp->next;
}
// Check to see if the item was found
if(temp == NULL) return FALSE; // Not found so return FALSE
else if(back == NULL) // Check to see if item is first in list
{
head = head->next;
free(temp); // Dispose of the node removed from the list
}
else // Delete node elsewhere in the list
{
back->next = temp->next;
free(temp); // Dispose of the node removed from the list
}
return TRUE; // Signal successful deletion
}
//--------------------------------------------
// Function: Search()
// Purpose: Search for an item by key and copy
// the value into the variable pointed to
// by *retVal.
// Returns: TRUE if search was successful
// or FALSE if the search failed.
//--------------------------------------------
int Search(int key, float *retVal)
{
ListItem *temp;
temp = head;
// See note on the order of the conditional in this
// while() loop in Delete() function above.
while((temp != NULL) && (key != temp->key))
{
temp = temp->next;
}
// If item not found or list is empty return FALSE
if(temp == NULL) return FALSE;
else
*retVal = temp->theData; // Copy the data
return TRUE; // Signal successful search
}
//--------------------------------------------
// Function: ListLength()
// Purpose: Return the number of items in the
// list.
// Returns: Number of items in list.
//--------------------------------------------
int ListLength()
{
ListItem *temp;
int count = 0;
temp = head;
while(temp != NULL)
{
temp = temp->next;
count++;
}
return count;
// An alternate way to do this is to maintain
// a static variable at the top of this source
// code, e.g. int count. This can be incremented
// each time a node is added and decremented each
// time a node is deleted.
}
//--------------------------------------------
// Function: isEmpty()
// Purpose: Return true if the list is empty
// Returns: TRUE if empty, otherwise FALSE
// Note: C has no boolean data type so we use
// the defined int values for TRUE and FALSE
// instead.
//--------------------------------------------
int isEmpty()
{
return (head == NULL);
}
//--------------------------------------------
// Function: isFull()
// Purpose: Return true if the list is full
// Returns: TRUE if full, otherwise FALSE
// Note: In theory a linked list cannot be
// full (unless you run out of memory) so
// this function defaults to returning FALSE.
//--------------------------------------------
int isFull()
{
return FALSE;
}
//--------------------------------------------
// Function: PrintList()
// Purpose: Print all items in the list with
// their key.
// Returns: void
//--------------------------------------------
void PrintList()
{
ListItem *temp;
printf("\n\nItems in the List\n");
printf("-----------------------------------------------------------\n");
printf("Key\t\tData\n");
printf("-----------------------------------------------------------\n");
if(head == NULL) // Report no items in the list
{
printf("\t List is currently empty.\n");
}
else
{
temp = head;
while(temp != NULL)
{
printf("%d\t\t%f\n", temp->key, temp->theData);
temp=temp->next;
}
}
printf("-----------------------------------------------------------\n\n");
}
Main file used to test the list
//---------------------------------------------------------------
// File: ListMain.c
// Purpose: Main file with tests for a demonstration of an unsorted
// list implemented as a linked structure.
// Programming Language: C
// Author: Dr. Rick Coleman
// Date: January 8, 2002
//---------------------------------------------------------------
#include <stdio.h>
#include "Code111_List.h"
int main(int argc, char **argv)
{
float f;
printf("Simple List Demonstration\n");
printf("(List implemented as a linked structure)\n\n");
printf("Create a list and add a few tasks to the list");
InitList();
Insert(5, 3.1f); // Note: The argument to the funtion should be a float
Insert(1, 5.6f); // A constant real number like 3.1 is interpreted as
Insert(3, 8.3f); // a double unless it is explicitly defined as a float
Insert(2, 7.4f); // by ading an 'f' to the end of the number.
Insert(4, 2.5f);
// Show what is in the list
PrintList();
// Test the list length function
printf("\nList now contains %d items.\n\n", ListLength());
// Test delete function
printf("Testing delete of last item in list.\n");
Delete(4);
PrintList();
// Test delete function
printf("Testing delete of first item in list.\n");
Delete(5);
PrintList();
// Test delete function
printf("Testing delete of a middle item in list.\n");
Delete(3);
PrintList();
// Test delete function with a known failure argument
printf("Testing failure in delete function.\n");
if(Delete(4))
printf("Oops! Should not have been able to delete.\n");
else
printf("Unable to locate item to delete.\n");
// Test search (known failure)
printf("Testing Search function. Search for key 3\n");
if(Search(3, &f))
printf("Search result: theData = %f\n", f);
else
printf("Search result: Unable to locate item in list\n");
// Test search (known success)
printf("Testing Search function. Search for key 2\n");
if(Search(2, &f))
printf("Search result: theData = %f\n", f);
else
printf("Search result: Unable to locate item in list\n");
printf("\n\nEnd list demonstration...");
return 0;
}