Re: [Dev-C++] Sorting Queues

[<or...@vp...>]

Hello!

Samuel Keding wrote:
> Linked 
> lists are better but if I want to stick an element right in the 
> middle, I still have to follow the links all the way down the list. 

Well, I am making a project in C, and I needed sorted linked lists for 
it. I have made a very small implementation of a doubly linked closed 
list, which can be sorted, by giving a comparison function at the 
creation of the list (something like qsort()). If it is NULL, the list 
will be unsorted. I have made a small, yet very efficient function which 
inserts at the right place using the comparison function, or appends if 
it is NULL.
The list stores void* pointers, so actually anything can be contained in it.
Lists can be created, destroyed. Elements (void* values) can be added, 
removed, they are stored in nodes internally. Searching is also 
implemented. The list structure has a pointer to the first and the last 
node, and each node has a pointer to the previous and next nodes. So 
removal and insertation is fast.
The list is called xlist, nodes xnode.

Ex.: getting next value: xnode_current->next->value.
Ex.: Iterating through the list if needed:

xnode *xn
xlist *xl;
/* Create, add values here ... */
/* Iterate now: */
for(xn = xl->first;xn != NULL;xn = xn->next){
   xn->value ...
}

The whole stuff is one .c (only 90 lines of code) and one .h(40 lines of 
code) file (xlist.c, xlist.h). I have attached them. I hope it will be 
useful :)
Here is the interface for it (the xlist.h file):


/* General purpose list implementation
  * Header file
  * Written by: Balázs Oroszi
  * 2002
  */

#ifndef _S_XLIST_H
#define _S_XLIST_H
#ifdef __cplusplus
extern "C" {
#endif

   typedef int (*compproc)(void*,void*);

   typedef struct _xnode{
     void* value;
     struct _xnode *prev;
     struct _xnode *next;
   }xnode;

   typedef struct _xlist{
     int length;
     xnode *first;
     xnode *last;
     compproc cmp; /* if NULL, the list is unsorted */
   }xlist;

   /* list management */
   xlist* xlist_create(compproc cmp);
   void xlist_destroy(xlist *pxl);
   xnode* xlist_add(xlist *pxl, void* value);
   int xlist_remove(xlist *pxl, xnode *pxn);
   int xlist_length(xlist *pxl); /* O(1) time */

   /* list utility functions */
   xnode* xlist_search(xlist *pxl, void* value);

#ifdef __cplusplus
}
#endif
#endif