// Igor Kolpakov's "reverse pointer" trick
// DDJ, June 1999, p. 128

#include <conio.h>
#include <iostream.h>
#include <stdlib.h>

typedef struct _ITEM ITEM;
struct _ITEM {
	int key;
	ITEM * next;
};

void AddItem(ITEM *newItem);

ITEM *listHead;

void AddItem(ITEM *newItem) {
	// keep a "reverse pointer" to the pointer to this item
	ITEM ** rpItem = &listHead;
	ITEM * item = listHead;

	while (item && (newItem->key > item->key)) {
		rpItem = &item->next;
		item = item->next;
	}
	// Note: No extra tests
	*rpItem = newItem;
	newItem->next = item;
}

void DeleteItem(int key) {
	ITEM ** rpItem = &listHead;
	ITEM * item = listHead;

	while (item && (key > item->key)) {
		rpItem = &item->next;
		item = item->next;
	}
	if (item && (key==item->key)) {
		// Note: no extra tests
		*rpItem = item->next;
		free ( item );
	}
}

void printItems()  {
	ITEM *item = listHead;

	while (item && !kbhit()) {
		cout << "Item key: " << item->key << endl;
		item = item->next;
	}
}

void main() {
	ITEM *i=new ITEM;
	i->key = 2;
	i->next=0;
	AddItem(i);

	ITEM *j=new ITEM;
	j->key = 1;
	j->next=0;
	AddItem(j);

	ITEM *k=new ITEM;
	k->key = 3;
	k->next=0;
	AddItem(k);

	ITEM *l=new ITEM;
	l->key = 12;
	l->next=0;
	AddItem(l);

	DeleteItem(12);
	printItems();
}