Title: Difference Structures in C/C++

Difference structures are a Prolog technique but they can be adapted to C and C++ as follows: Imagine having a linked list, but as well as a pointer to the head of the list you also have a pointer to its last element. (When the list is empty or there is only one item, the two pointers will be equal.) Code to maintain such a list shouldn't be too difficult if you can write linked list code, so I'll leave it as an exercise but I'll assume you're using:

typedef struct Item {
  void* data;
  struct Item* next;
} Item;
typedef struct {
  Item* firstElement;
  Item* lastElement;
} List;

(In C++ you would of course use a class with methods and possibly a template, but I won't do that here for the benefit of the C programmers.)

With a pointer to the last element, you can do some powerful things. For example, you can concatenate two lists very quickly:

void concat(List* first, const List* second) {
  if (first->lastElement) first->lastElement->next=second->firstElement;
  if (second->lastElement) first->lastElement=second->lastElement;
}

(Note that no copy of the second list is made.) Or if you want a queue:

void queueItem(List* addTo,void* d) {
  Item* i=malloc(sizeof(Item));
  i->data=d; i->next=NULL;
  if (addTo->lastElement) addTo->lastElement->next=i;
  else addTo->firstElement=i;
  addTo->lastElement=i;
}

void* getItem(List* getFrom) {
  void* ret=NULL;
  Item* i=getFrom->firstElement;
  if (i) {
    getFrom->firstElement=getFrom->firstElement->next;
    if(!(getFrom->firstElement)) getFrom->lastElement=NULL;
    ret=i->data;
    free(i);
  } return ret;
}

Some implementations of queues use doubly-linked lists, but the above uses less memory. You can also rotate a list quickly (but only in one direction with single links):

void rotate(List* l) {
  if(l->firstElement) {
    l->lastElement->next=l->firstElement;
    l->lastElement=l->firstElement;
    l->firstElement=l->firstElement->next;
    l->lastElement->next=NULL;
  }
}

When writing code like that you have to keep a clear head. The order of assignments is crucial - if in doubt, simulate on paper. Bearing in mind that one or more of the parameters might be an empty list is also important (although it is reasonable to insist that the parameters themselves will not be NULL - add asserts if desired).