sll
Singly Linked List Library Muhammad A Muquit |
Download
sll.tar.gz
|
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) |
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,Sll *node,void (*freeFunc)(void **))
void destroyNodes(Sll **head,void (*freeFunc)(void **))
int numNodes(Sll **head)
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; } }
/* ** 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)); }
/* ** 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