Thread: C Linked List - first attempt.

Example where the last node pointer (called tail) is in main, and without a dummy node.

Code:

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

struct node                 /* node structure */
{
    struct node *next;
    int data;
};

void createNewNode(struct node **head, struct node **tail, int data)
{
    /* allocate space for new node */
    struct node *newNode = malloc(sizeof(*newNode));
    if(!newNode)            /* check the memory allocation took place */
    {
        printf("Out of memory\n");
        exit(-1);           /* exit program showing error code -1 */
    }
    newNode->next = NULL;   /* initialise the new node */
    newNode->data = data;
    if(NULL == *head)       /* set link to the new node */
        *head = newNode;
    else
        (*tail)->next = newNode;
    *tail = newNode;
}

void deleteList(struct node **head, struct node **tail)
{
    struct node *thisNode;  /* pointers to node */
    struct node *nextNode;
    /* if null pointers or empty list return */
    if(head == NULL || tail == NULL || *head == NULL)
        return;
    thisNode = *head;       /* free nodes */
    while(thisNode)
    {
        nextNode = thisNode->next;
        free(thisNode);
        thisNode = nextNode;
    }
    *head = NULL;           /* reset head, tail */
    *tail = NULL;
}

void displayList(struct node **head)
{
    struct node *Node;      /* pointer to node */
    /* check for null ptr or empty list */
    if(head == NULL || *head == NULL)
    {
        printf("empty list\n");
        return;
    }
    Node = *head;
    while(Node)             /* while not end of list */
    {
        /* show the element */
        printf("{addr} %p {data} %d {next} %p\n",Node,Node->data,Node->next);
        Node = Node->next;
    }
}

int main(int args, char *argv[])
{
    struct node *head = NULL;           /* root pointer */
    struct node *tail = NULL;           /* last node pointer */
    int i;                              /* counter variable */
    
    for(i = 0 ; i < 10 ; i++)           /* add some elements to the list */
        createNewNode(&head, &tail, i);

    displayList(&head);                 /* display the total list */
    
    deleteList(&head, &tail);           /* delete list */
    
    displayList(&head);                 /* display empty list */
    
    return 0;
}

Here is a sample program using a linked list. Note that the most basic of operations have been given their own functions.

linkedlistop.h

Code:

// linkedlistop.h


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


void display( struct node * );
struct node * addback( struct node * , int );
struct node * addfront( struct node * , int );
struct node * nalloc( int );
struct node * find( struct node * , int );
struct node * delnode( struct node * , struct node * );
void freelist( struct node * );

linkedlistop.c

Code:

/*
  this file contains functions for manipulating a linked list
*/


#include <stdlib.h>


#ifndef LLOP
#define LLOP


#include "linkedlistop.h"
#include <stdio.h>


#endif


/*
  iterate through list and print data from each node
*/
void display( struct node * head )
{
    struct node * p = head;
    while( p != NULL )
    {
        printf( "%d " , p->data );
        p = p->next;
    }
    printf( "\n" );
}
/*
  creates node, init's data members and returns pointer to node
*/
struct node * nalloc( int data )
{
    struct node * p = malloc( sizeof( struct node ) );
    if( p != NULL )
    {
        p->data = data;
        p->next = NULL;
    }
    return p;
}
/*
  creates node and adds it to the front of list, becoming new head
*/
struct node * addfront( struct node * head , int data )
{
    struct node * p = nalloc( data );
    if( p == NULL )
        return head;
    p->next = head;
    return p;
}
/*
  creates node and adds it to back of list, returns (new) head
*/
struct node * addback( struct node * head , int data )
{
    struct node * curr;
    struct node * p = nalloc( data );
    if( p == NULL )
        return head;
    if( head == NULL )
        return  p;
    for( curr = head; curr->next != NULL; curr = curr->next )
        ;
    curr->next = p;
    return head;
}
/*
  searchs link beginning at head for target
*/
struct node * find( struct node * head , int target )
{
    struct node * p = head;
    if( head == NULL )
        return NULL;
    while( p != NULL )
    {
        if( p->data == target )
            return p;
        p = p->next;
    }
    return NULL;
}
/*
  deletes the node pointed to by np, returns updated head
*/
struct node * delnode( struct node * head , struct node * np )
{
    if( head == NULL || np == NULL )
        return NULL;
    struct node * p , * q = NULL;
    for( p = head; p != np && p != NULL; p = p->next )
        q = p;
    if( p == NULL ) // not found
        return head;
    if( q == NULL ) // head node
    {
        free( np );
        return p->next;
    }
    q->next = p->next;
    free( np );
    return head;
}
/*
  deletes every node in list using free()
*/
void freelist( struct node * head )
{
    struct node * p = NULL;
    while( head )
    {
        p = head;
        head = head->next;
        free( p );
    }
}

lltest.c

Code:

#include <stdlib.h>
#include <time.h>


#ifndef LLOP
#define LLOP


#include "linkedlistop.h"
#include <stdio.h>


#endif


int main( void )
{
    srand( time( NULL ) );
    struct node * head = nalloc( 10 );  // list: 10


    display( head );


    head = addback( head , rand() % 100 );  // list: 10 , (random1)


    display( head );


    head = addfront( head , rand() % 100 ); // list: (random2) , 10 , (random1)


    display( head );


    head = delnode( head , find( head , 10 ) ); // list: (random2) , (random1)


    display( head );


    freelist( head );


    return 0;
}

Use this to compare against your code where you are having trouble understanding.

It's not meant to be robust, just an example. But thanks for pointing that out.