ABOUT TWO YEARS AGO, I IMPLEMENTED AN IDEA (USE SINGLE POINTER FIELD GET A
DOUBLY LINKED LIST ) . The comments are not
totally correct 
In a list, there would be two implicit dummy node ( one at the front and one
at the end ). I put the copyright with
the hope that I can sue someone using this code :). Just kidding, if it is
of any use go for it. But make sure you understand ( there is no bumper to
bumper warrenty :).
The findings are : Memory usage efficiency is really good ( leaving it as an
exercise ) for doubly link grid datastructure it would be magnificant.
Hardly any noticable time differences when runing on 5K, 10K, … 30K nodes.
Enjoy !!!
-pro
/* Created by Anjuta version 0.1.7 */
/* This file will not be overwritten */
/* COPYRIGHT “PROGRAMMERS SOCIETY INC. - PROKASH SINHA " */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
// use a single ptr to traverse back and forth
// //////////////////////////////////////////////
// | 0 | | 1 | | 2 | | 3 | | 4 | | 5 |
// |-----| |-----| |-----| |-----| |-----| |-----|
// |(1^0)| |(2^0)| |(3^1)| |(4^2)| |(5^3)| |(4^0)|
//
// Numerator of a node is the element.
// (m^n) is the exclusive or of ptr to m, and ptr to n.
// pStart points to element 0, pEnd points to 5 in this example
//
//
// pStart = pEnd = NULL => list is empty
// pStart = pEnd <> NULL => list is singleton
typedef int T;
//
// dbly link represented by ptr distance
//
typedef struct listNode{
T elm;
struct listNode * ptrdiff;
};
typedef struct listNode *plistNode;
//
// conventional dbly link representaion
//
typedef struct dlistNode {
T elm;
struct dlistNode *next;
struct dlistNode *prev;
};
typedef struct dlistNode *pdlistNode;
//
//globls for ptrdiff ds
plistNode pStart, pEnd;
//glbls for conventional
pdlistNode pdHead, pdEnd;
// * for ptrdiff
plistNode NextNode( plistNode pNode, plistNode pPrevNode)
{
return ((plistNode) ((int) pNode->ptrdiff ^ ( int)pPrevNode) );
}
//conventional
pdlistNode dNextNode ( pdlistNode pdNode)
{
return (pdNode->next );
}
pdlistNode dPrevNode ( pdlistNode pdNode)
{
return (pdNode->prev );
}
// ptr.dist list delete
void delList ()
{
//
plistNode pPrev, pCurrent;
pPrev = NULL;
pCurrent = pStart;
while ( pCurrent ) {
pCurrent->ptrdiff = NextNode( pCurrent, pPrev);
if (pPrev)
free(pPrev);
if ( !pCurrent->ptrdiff ){
printf(” Final node being deleted in prt.dist. =%d\n", pCurrent->elm);
free(pCurrent);
pCurrent = NULL;
continue;
}
pPrev = pCurrent;
pCurrent = pCurrent->ptrdiff;
}
}
// conventional list delete
void ddelList()
{
pdlistNode pdCurrent, pdNext;
pdCurrent = pdHead;
while (pdCurrent) {
pdNext = dNextNode(pdCurrent);
free(pdCurrent);
pdCurrent = pdNext;
}
}
// for dist. ptr.
void insertAfter ( plistNode pNew, T theElm )
{
plistNode pPrev, pCurrent, pNext;
pPrev = NULL;
pCurrent = pStart;
while (pCurrent) {
pNext = NextNode(pCurrent, pPrev);
if (pCurrent->elm == theElm ) {
/*fw traversal is done */
//
if (pNext ) { // fix the existing next node
pNext->ptrdiff = (plistNode) ((int)pNext->ptrdiff ^ ( int) pCurrent ^
(int)pNew );
}
//fix the current node
pCurrent->ptrdiff = (plistNode) ((int)pNew ^ (int)pNext ^
(int)pCurrent->ptrdiff);
//fix the new node
pNew->ptrdiff = (plistNode) ( (int)pCurrent ^ (int)pNext );
break;
}
pPrev = pCurrent;
pCurrent = pNext;
}
}
// * for conventional insertAfter()
void dinsertAfter(pdlistNode pdNew, T theElm )
{
pdlistNode pdPrev, pdCurrent, pdNext;
pdCurrent= pdHead;
while (pdCurrent) {
pdNext = dNextNode(pdCurrent);
if (pdCurrent->elm == theElm ) {
if (pdNext ) {//fix the existing next node
pdNext->prev = pdNew;
}
//fix the current node
pdCurrent->next = pdNew;
//fix the new node
pdNew->next = pdNext;
pdNew->prev = pdCurrent;
break;
}
pdCurrent = pdNext;
}
}
// ptr. dist. struct. traversal
void traverse( plistNode pRoot )
{
//
plistNode pCurrent, pPrev, pNext;
pPrev = NULL;
pCurrent = pRoot;
while (pCurrent)
{
//printf(" -> %d\n", pCurrent->elm) ;
pNext = NextNode(pCurrent, pPrev );
pPrev = pCurrent;
pCurrent = pNext;
}
}
// conventional forward traversal
void dtraversefw( pdlistNode pdHead )
{
//
pdlistNode pCurrent;
pCurrent = pdHead;
while (pCurrent)
{
//printf(" -> %d\n", pCurrent->elm) ;
pCurrent = dNextNode(pCurrent);
}
}
// conventional backward traversal
void dtraversebw( pdlistNode pdHead )
{
//
pdlistNode pCurrent;
pCurrent = pdHead;
while (pCurrent)
{
//printf(" -> %d\n", pCurrent->elm) ;
pCurrent = dPrevNode(pCurrent);
}
}
//
// dist. ptr. insertion
void insert( T elm)
{
//
plistNode pnewNode = (plistNode)malloc(sizeof(struct listNode) );
if (! pnewNode) {
printf(" malloc failed in insert( T elm) \n");
return;
}
pnewNode->elm = elm;
pnewNode->ptrdiff = NULL;
//brand new
if ( !pStart ) {
pStart = pEnd = pnewNode;
}else {
insertAfter( pnewNode, pEnd->elm);
pEnd = pnewNode;
}
return ;
}
//conventional insert
void dinsert ( T elm)
{
pdlistNode pdnewNode = (pdlistNode)malloc(sizeof(struct dlistNode) );
if (! pdnewNode) return;
pdnewNode->elm = elm;
pdnewNode->next = pdnewNode->prev = NULL;
//brand new
if ( !pdHead ) {
pdHead = pdEnd = pdnewNode;
}else {
dinsertAfter(pdnewNode, pdEnd->elm );
pdEnd = pdnewNode;
}
return ;
}
#define NO_OF_ITEM_IN_LIST 30000
//#define EXERCISE_PTR_DIST 1
void doTimeStamp (char * strArg)
{
char *pcharTime ;
time_t c_time;
time(&c_time);
pcharTime = ctime(&c_time);
printf(“%s %s\n”,strArg, pcharTime);
}
// exercise the conventional struct
void exerciseDlist()
{
char *pcharTime ;
time_t c_time;
int i;
doTimeStamp("Before conventional insert() " );
for (i = 0; i < NO_OF_ITEM_IN_LIST; i++)
dinsert ( (T) i );
doTimeStamp("After conventional insert() " );
printf (“Total Memory taken by conventional structure = %d bytes.\n”,
NO_OF_ITEM_IN_LIST *sizeof(struct dlistNode) );
//forward
doTimeStamp("Before conventioal dtraversefw(pdHead ) " );
dtraversefw(pdHead );
doTimeStamp("After conventioal dtraversefw(pdHead ) " );
//backward
doTimeStamp("Before conventioal dtraversebw(pdEnd) " );
dtraversebw(pdEnd);
doTimeStamp("After conventioal dtraversebw(pdEnd) " );
//delete
doTimeStamp("Before conventioal ddelList () " );
ddelList ();
doTimeStamp("After conventioal ddelList () " );
}
void exerciseDistptrlist()
{
int i;
doTimeStamp(“Before insert(prt.dist.)”);
// exercise the ptr distance structure
for (i = 0; i < NO_OF_ITEM_IN_LIST ; i++)
insert ( (T) i );
doTimeStamp( “After insert(prt.dist.)” );
printf (“Total Memory taken by ptr distance structure = %d bytes.\n”,
NO_OF_ITEM_IN_LIST *sizeof(struct listNode) );
//forward traversal
doTimeStamp ("Before traverse(pStart) of (prt.dist.) ");
traverse(pStart);
doTimeStamp( "After traverse(pStart) of(prt.dist.) ");
//backward traversal
doTimeStamp("Before traverse(pEnd) of (prt.dist.) ");
traverse(pEnd);
doTimeStamp( "After traverse(pEnd) of (prt.dist.) ");
//delete the whole list
doTimeStamp( "Before delList () of (prt.dist.) ");
delList ();
doTimeStamp("After delList () of (prt.dist.) ");
}
int main()
{
//exerciseDlist();
#ifdef EXERCISE_PTR_DIST
exerciseDistptrlist();
#else
exerciseDlist();
#endif
printf(“Hello world\n”);
return (0);
}</time.h></stdlib.h></assert.h></stdio.h>
