#C_CODE: Single Linked List Manipulations in C

/* Details: Single linked list manipulation functions
* Author : Vinod Sasidharan
* Date : Monday, March 21, 2011, 11.41 am
* Remarks: reverse, findNthNodeFromLast,deletedata
*/

/* Include files */
#include <stdio.h>
#include <malloc.h>

 
/* typedef for meaningful name */
typedef struct singlelink node;

/* The single linked list structure */
struct singlelink
{
    int data;
    node *link;
};

/* Function: append()
 * Appends the input data to the end of the linked list.
 * If it's the 1st node, then process it separately.
 */
void append(node **q, int num)
{
    node *temp = *q,*r;
    r = (node *)malloc(sizeof(node));
    r->data = num;
    r->link = NULL; //This would be the last node in list

    if(NULL == temp) // If it's going to be the 1st node...
        *q = r;
    else
    {
        //Traverse through the list to reach the last node
         while(NULL != temp->link) 
            temp = temp->link; 

        temp->link = r;
    }
}

/* Function: display()
 * Displays the linked list data on the standard output  
 */
void display(node *temp)
{
    printf("\nThe list: ");
    while(temp)
    {
        printf("%d ",temp->data);
        temp = temp->link;
    }
    printf("\n");
    getchar(); // Wait for user.
}

/* Function delatbeg()
 * Deletes the node at the beginning of the list
 */
void delatbeg(node **q)
{
    node *temp = *q;
    *q = temp->link;
    free(temp);
}

/* Function: addatbeg()
 * Adds a node at the beginning of the list with input data.
 */
void addatbeg(node **q,int num)
{
    node *r;
    r = (node *)malloc(sizeof(node));
    r->data = num;
    r->link = *q;
    *q = r;
}

/* Function: findNthNodeFrmLast()
 * Find the data in the Nth node(input) from last pos in
 * the list.
 */
void findNthNodeFrmLast(node *temp,int pos)
{
    node *Nth = temp;
    int i = 0;

    while(temp)
    {
        if(i++ >= pos) //The core logic
            Nth = Nth->link;
        temp = temp->link;
    }
    printf("Data in position %d node from last: %d\n",
            pos,Nth->data);
    getchar(); //Wait for user...
}

/* Function: reverse()
 * Reverse the linked list.
 */
void reverse(node **q)
{
    node *temp1 = *q;
    node *temp2 = NULL;
    node *temp3 = NULL;

    if(!temp1) return; //Sanity check

    while(temp1)
    {
        temp2 = temp1->link; // Save the next pointer
        temp1->link = temp3; // Save the previous
        temp3 = temp1; // Update the previous
        temp1 = temp2; // Update the next
    }
    *q = temp3; // Update the head node pointer.
}

/* Function: deletedata()
 * Deletes a particular data(input) from the list
 */
void deletedata(node **q,int data)
{
    node *temp = *q, *old = NULL;
    while(temp)
    {
        if(data == temp->data)
        {
            if(*q == temp)
                *q = temp->link;
            else
                old->link = temp->link;

            free(temp); // Free the node using the free().
            return;     // Expected exit.
        }
        else
        {
            old = temp;
            temp = temp->link;
        }
    }
}

/* Function: Main() 
 * Calls the single linked list manipulation functions 
 */
int main()
{
    /* Initialize the head node */
    node *head = NULL; 
    int i;

    /* Append 10 nos of data to the linked list */
    for(i=0; i<10; i++)
        append(&head,i);

    /* Display the linked list */ 
    display(head);

    /* Reverse the linked list & display it. */
    reverse(&head);
    printf("The reversed list: ");
    display(head);

    /* Find Nth node from last */
    findNthNodeFrmLast(head,3);

    /* delete a particular data */
    deletedata(&head,4);
    printf("Delete data 4: ");
    display(head);

    /*Delete the node at the beginning of the list */
    delatbeg(&head);
    delatbeg(&head);
    printf("Delete 1st two data: ");
    display(head);

    /* Add a data at the beginning of the list */
    addatbeg(&head,22);
    addatbeg(&head,25);
    printf("Add 22 & 25 at beginning: ");
    display(head);
}

Tested on: Visual C++ 2008 Express Edition, Windows XP