(mm) A singly linked list library
Home | Software | Count
Software:
GWT
  GWTOAuthLogin
X/Motif
  ansi xterm
  grabc
  mdgclock
  miv
  mplaymidi
  mppp
  mxascii
  mcmap
  mxcmap
  mxconsole
  mxkill
  mxshowfont
  qtip
  xmastm
  yrolo
Web
  mhttpd
  web counter
  upload.pl
  TimeTrack.pl
  mod_auth_ldap
Games
  fltkmm
  iphonemm
Java
   cdcl
   cdclgwt
   jdgclock
Libraries
  libcalen
  libmcfg
  libsll
  libmsock
Misc
  bangla font
  dpr
  genmake
  hod
  smtp.pl
  vhtml
  phones_ldap
  showpic_ldap
  mbasecalc
  fluid_hack
  kdialppp
  strip2csv
  googlecode-upload
MS Windows
  mwinclip.pl
  mbasecalc
  mailsend
  wiv
sll
Singly Linked List Library
(For Linux/Unix,MS NT/2000)
Muhammad A Muquit
Introduction
Sll is a Singly Linked List library. The functions takes pointer to a void data type, so you can make a linked list from any kind of data. It's required that you have to write your own function to free your data. You will pass a pointer to your function while calling sll free routines. Please look at the Examples section for code sample. I hope You will find the library useful. Note, this library is not object oriented, nothing is abstracted, I wrote it this way. I wanted to see clearly what's going on. I wrote it because I was tired of many object oriented linked list libraries out there.

Download
Source
File: libsll.tar.gz
Size: 27622 bytes
MD5 Checksum: a790622c196a1b8ac27d60eeb377fd70
Last updated: ?

(contains compiled sll.lib for Windows NT/2000)

sll Data Structure

    typedef struct _Sll
    {
        void
            *data;          /* void pointer for user data */

        struct _Sll
            *next;          /* pointer to next node */
    } Sll;    

sll Function reference

    void initlist         (Sll **list)
    Sll  *allocateNode    (void *data)
    void appendNode       (Sll **head,Sll **new)
    void appendNodeSorted (Sll **head,Sll **new,int (*compFunc) (void *,void *))
    void insertNode       (Sll **head,Sll **new)
    Bool emptyList        (Sll *list)
    void delNode          (Sll **head,Sll *node)
    void freeNode         (Sll **list)
    Sll  *getNthNode      (Sll *head,int n)
    void destroyNode      (Sll **head, void (*freeFunc)(void **))
    void destroyNodes     (Sll **head, void (*freeFunc)(void **))
    int  numNodes         (Sll **head)

Examples
  • Example 1 - Insert a node at the beginning of the list
  • Example 2 - Append a node at the end of the list.
  • Example 3 - Append a node at the end of the list sorted.
  • Example 4 - Delete a node.

Example 1: Insert a node at the beginning of the list. The code is available in examples/insert directory.

/*
**  test inserting a node at the beginning of the list. print the result
**  and then free the memory. a user defined function is called to free
**  the data.
**
**  Development History:
**      who                  when           why
**      ma_muquit@fccc.edu   Aug-09-1998    first cut
*/


#include <config.h>
#include <sll.h>

typedef struct _addr
{
    char
        *name,
        *city,
        *state;
} Addr;

static void freeData(void **data);

int main (int argc,char **argv) 
{
    Sll
        *l,
        *head=NULL,
        *new=NULL;
    Addr
        *addr;

    int
        n=0;

    (void) fprintf(stderr,
"=========================================================================\n");
    (void) fprintf(stderr," Testing Insert a node at the beginning of a list\n");
    (void) fprintf(stderr,
"=========================================================================\n");

    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }

    /*
    ** it will be the last node
    */
    addr->name=strdup("Muhammad A Muquit");
    addr->city=strdup("Philadelphia");
    addr->state=strdup("PA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }

    new=allocateNode((void *) addr);
    insertNode(&head,&new);
    (void) fprintf(stderr,"Inserting Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** insert node before the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Janet Hunter");
    addr->city=strdup("Santa Clara");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    insertNode(&head,&new);
    (void) fprintf(stderr,"Inserting Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);


    /*
    ** insert node before the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Babs Jensen");
    addr->city=strdup("Cupertino");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    insertNode(&head,&new);
    (void) fprintf(stderr,"Inserting Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** print
    */
    (void) fprintf(stderr,"\n\nPrinting........\n");
    n=0;
    for (l=head; l; l=l->next)
    {
        addr=(Addr *) l->data;
        (void) fprintf(stderr,"Node: %d\n",++n);
        (void) fprintf(stderr,"  %s\n",addr->name);
        (void) fprintf(stderr,"  %s\n",addr->city);
        (void) fprintf(stderr,"  %s\n\n",addr->state);
    }

    /*
    ** free nodes
    */
    destroyNodes(&head,freeData);

    exit(0);
}


/*
** routine to free the user data
*/

static void freeData(void **data)
{
    Addr
        **addr=(Addr **) data;

    static int
        n=0;

    n++;
    if (*addr)
    {
        if ((*addr)->name)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->name);
            (void) free((char *) (*addr)->name);
        }
        if ((*addr)->city)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->city);
            (void) free ((char *) (*addr)->city);
        }
        if ((*addr)->state)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->state);
            (void) free ((char *) (*addr)->state);
        }

        (void) fprintf(stderr,"Freeing the node %d itself\n\n",n);
        (void) free((char *) (*addr));
        (*addr)=NULL;
    }
}


Example 2: Append a node at the end of the list. The code is available in examples/append directory.

/*
**  test appending a node at the end of the list. print the result
**  and then free the memory. a user defined function is called to free
**  the data.
**
**  Development History:
**      who                  when           why
**      ma_muquit@fccc.edu   Aug-09-1998    first cut
*/


#include <config.h>
#include <sll.h>

typedef struct _addr
{
    char
        *name,
        *city,
        *state;
} Addr;

static void freeData(void **data);

int main (int argc,char **argv) 
{
    Sll
        *l,
        *head=NULL,
        *new=NULL;
    Addr
        *addr;

    int
        n=0;

    (void) fprintf(stderr,
"=========================================================================\n");
    (void) fprintf(stderr," Testing Append a node at the beginning of a list\n");
    (void) fprintf(stderr,
"=========================================================================\n");

    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }

    (void) fprintf(stderr,"\n---------------[ appending ]----------\n");
    /*
    ** it will be the last node
    */
    addr->name=strdup("Muhammad A Muquit");
    addr->city=strdup("Philadelphia");
    addr->state=strdup("PA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }

    new=allocateNode((void *) addr);
    appendNode(&head,&new);
    (void) fprintf(stderr,"Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** append node after the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Janet Hunter");
    addr->city=strdup("Santa Clara");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    appendNode(&head,&new);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);


    /*
    ** append node after the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Babs Jensen");
    addr->city=strdup("Cupertino");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    appendNode(&head,&new);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** print
    */
    (void) fprintf(stderr,"\n---------------[ printing ]----------\n");
    n=0;
    for (l=head; l; l=l->next)
    {
        addr=(Addr *) l->data;
        (void) fprintf(stderr,"Node: %d\n",++n);
        (void) fprintf(stderr,"  %s\n",addr->name);
        (void) fprintf(stderr,"  %s\n",addr->city);
        (void) fprintf(stderr,"  %s\n",addr->state);
    }

    /*
    ** free nodes
    */
    (void) fprintf(stderr,"\n---------------[ freeing ]----------\n");
    destroyNodes(&head,freeData);

    exit(0);
}


/*
** routine to free the user data
*/

static void freeData(void **data)
{
    Addr
        **addr=(Addr **) data;

    static int
        n=0;

    n++;
    if (*addr)
    {
        if ((*addr)->name)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->name);
            (void) free((char *) (*addr)->name);
        }
        if ((*addr)->city)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->city);
            (void) free ((char *) (*addr)->city);
        }
        if ((*addr)->state)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->state);
            (void) free ((char *) (*addr)->state);
        }

        (void) fprintf(stderr,"Freeing the node %d itself\n\n",n);
        (void) free((char *) (*addr));
        (*addr)=NULL;
    }
}

Example 3: Appends a node to the end of a list sorted.
/*
**  Appends a node to the end of a list sorted. The data of two lists are
**  passed to the user defined function compFunction for sorting. 
**
**  Development History:
**      who                  when           why
**      ma_muquit@fccc.edu   Aug-09-1998    first cut
*/


#include <config.h>
#include <sll.h>

typedef struct _addr
{
    char
        *name,
        *city,
        *state;
} Addr;

static void freeData(void **data);
static int compFunc(void *a1,void *a2);

int main (int argc,char **argv) 
{
    Sll
        *l,
        *head=NULL,
        *new=NULL;
    Addr
        *addr;

    int
        n=0;

    (void) fprintf(stderr,
"=========================================================================\n");
    (void) fprintf(stderr," Testing Append a node at the beginning of a list\n");
    (void) fprintf(stderr,
"=========================================================================\n");

    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }

    (void) fprintf(stderr,"\n---------------[ appending ]----------\n");
    /*
    ** it will be the last node
    */
    addr->name=strdup("Cindy Muquit");
    addr->city=strdup("Philadelphia");
    addr->state=strdup("PA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }

    new=allocateNode((void *) addr);
    appendNodeSorted(&head,&new,compFunc);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** append node before the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Janet Hunter");
    addr->city=strdup("Santa Clara");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    appendNodeSorted(&head,&new,compFunc);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);


    /*
    ** append node before the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Babs Jensen");
    addr->city=strdup("Cupertino");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    appendNodeSorted(&head,&new,compFunc);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** print
    */
    (void) fprintf(stderr,"\n---------------[ printing ]----------\n");
    n=0;
    for (l=head; l; l=l->next)
    {
        addr=(Addr *) l->data;
        (void) fprintf(stderr,"Node: %d\n",++n);
        (void) fprintf(stderr,"  %s\n",addr->name);
        (void) fprintf(stderr,"  %s\n",addr->city);
        (void) fprintf(stderr,"  %s\n",addr->state);
    }

    /*
    ** free nodes
    */
    (void) fprintf(stderr,"\n---------------[ freeing ]----------\n");
    destroyNodes(&head,freeData);

    exit(0);
}


/*
** routine to free the user data
*/

static void freeData(void **data)
{
    Addr
        **addr=(Addr **) data;

    static int
        n=0;

    n++;
    if (*addr)
    {
        if ((*addr)->name)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->name);
            (void) free((char *) (*addr)->name);
        }
        if ((*addr)->city)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->city);
            (void) free ((char *) (*addr)->city);
        }
        if ((*addr)->state)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->state);
            (void) free ((char *) (*addr)->state);
        }

        (void) fprintf(stderr,"Freeing the node %d itself\n\n",n);
        (void) free((char *) (*addr));
        (*addr)=NULL;
    }
}


static int compFunc(void *a1,void *a2)
{
    Addr
        *addr1=(Addr *) a1,
        *addr2=(Addr *) a2;

/*
    (void) fprintf(stderr,"name1=%s\n",addr1->name);
    (void) fprintf(stderr,"name2=%s\n",addr2->name);
*/
    return (strcasecmp(addr1->name,addr2->name));
}


Example 4: Delete a node.
/*
**  first append a node at the end of a list. then dele a node and free the
**  memory associated with data.
**
**  Development History:
**      who                  when           why
**      ma_muquit@fccc.edu   Aug-09-1998    first cut
*/


#include <config.h>
#include <sll.h>

typedef struct _addr
{
    char
        *name,
        *city,
        *state;
} Addr;

static void freeData(void **data);

int main (int argc,char **argv) 
{
    Sll
        *node,
        *l,
        *head=NULL,
        *new=NULL;
    Addr
        *addr;

    int
        n=0;

    (void) fprintf(stderr,
"=========================================================================\n");
    (void) fprintf(stderr," Append a node at the beginning of a list\n");
    (void) fprintf(stderr,
"=========================================================================\n");

    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }

    (void) fprintf(stderr,"\n---------------[ appending ]----------\n");
    /*
    ** it will be the last node
    */
    addr->name=strdup("Muhammad A Muquit");
    addr->city=strdup("Philadelphia");
    addr->state=strdup("PA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }

    new=allocateNode((void *) addr);
    appendNode(&head,&new);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** append node before the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Janet Hunter");
    addr->city=strdup("Santa Clara");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    appendNode(&head,&new);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);


    /*
    ** append node before the last one
    */
    addr=(Addr *) malloc(sizeof(Addr));
    if (addr == NULL)
    {
        (void) fprintf(stderr," malloc failed\n");
        exit(-1);
    }
    addr->name=strdup("Babs Jensen");
    addr->city=strdup("Cupertino");
    addr->state=strdup("CA");

    if ((addr->name == NULL) ||
        (addr->city == NULL) ||
        (addr->state == NULL))
    {
        (void) fprintf(stderr,"malloc failed\n");
        exit(-1);
    }   
    new=allocateNode((void *) addr);
    appendNode(&head,&new);
    (void) fprintf(stderr,"Appending Node: %d\n", ++n);
    (void) fprintf(stderr,"  %s\n",addr->name);
    (void) fprintf(stderr,"  %s\n",addr->city);
    (void) fprintf(stderr,"  %s\n",addr->state);

    /*
    ** print
    */
    (void) fprintf(stderr,"\n---------------[ printing ]----------\n");
    n=0;
    for (l=head; l; l=l->next)
    {
        addr=(Addr *) l->data;
        (void) fprintf(stderr,"Node: %d\n",++n);
        (void) fprintf(stderr,"  %s\n",addr->name);
        (void) fprintf(stderr,"  %s\n",addr->city);
        (void) fprintf(stderr,"  %s\n",addr->state);
    }

    (void) fprintf(stderr,"\n-----------[ delete Node 2 ]---------\n");
    node=getNthNode(head,2);
    if (node != NULL)
        destroyNode(&head,node,freeData);
    else
        (void) fprintf(stderr,"No node found at position 2\n");
    (void) fprintf(stderr,"\n-----------[ printing all the nodes again ]--------\n");
    n=0;
    for (l=head; l; l=l->next)
    {
        addr=(Addr *) l->data;
        (void) fprintf(stderr,"Node: %d\n",++n);
        (void) fprintf(stderr,"  %s\n",addr->name);
        (void) fprintf(stderr,"  %s\n",addr->city);
        (void) fprintf(stderr,"  %s\n",addr->state);
    }


    /*
    ** free nodes
    */
    (void) fprintf(stderr,"\n---------------[ freeing ]----------\n");
    destroyNodes(&head,freeData);

    exit(0);
}


/*
** routine to free the user data
*/

static void freeData(void **data)
{
    Addr
        **addr=(Addr **) data;

    if (*addr)
    {
        if ((*addr)->name)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->name);
            (void) free((char *) (*addr)->name);
        }
        if ((*addr)->city)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->city);
            (void) free ((char *) (*addr)->city);
        }
        if ((*addr)->state)
        {
            (void) fprintf(stderr," Freeing: %s\n",(*addr)->state);
            (void) free ((char *) (*addr)->state);
        }

        (void) fprintf(stderr,"Freeing the node itself\n\n");
        (void) free((char *) (*addr));
        (*addr)=NULL;
    }
}

Copyright - GNU GPL

ChangeLog

  • First cut, Aug-09-1999

URL of this page: http://www.muquit.com/muquit/software/libsll/libsll.html

back Page updated: Sun Mar 31 01:59:56 2013 GMT   Copyright © 2013 muquit@muquit.com.