Circular Singly Linked Lists

Given the following struct ...

  struct Node
    {
      into info;
      Node * next;
    };

... which can be represented by the following graphic ...

     -------------
    | info | next |
     -------------

... and introducing a head pointer, we can create a singly linked list with 4 items.
The numbers represent the data.

    head
      |
      v
      -----------      -----------      -----------      ------------   
     |  17  | ---|--> |  20  | ---|--> |  12  | ---|--> |  8  | NULL |
      -----------      -----------      -----------      ------------ 

Modifying the list just a bit we make it into a circular linked list ... 

    head
      |
      v
      -----------      -----------      -----------      ------------   
     |  17  | ---|--> |  20  | ---|--> |  12  | ---|--> |  8  |   v  |
      -----------      -----------      -----------      ------------ 
      ^                                                           |
      |                                                           v
       <------------------------------------------------------------

... where the next field in the LAST item points to the FIRST item.
The next step is to delete the head pointer and to introduce a TAIL pointer.
The tail pointer always points to the LAST item in the list (or it is NULL).

                                                       tail 
                                                        |
                                                        v
      -----------      -----------      -----------      -----------   
     |  17  | ---|--> |  20  | ---|--> |  12  | ---|--> |  8  |  v  |
      -----------      -----------      -----------      ----------- 
      ^ A4               B5              C2               E7     |
      |                                                          v
       <-----------------------------------------------------------

This gives us a Circular Singly Linked List with a tail pointer.
The numbers along the bottom are the ADDRESSES of the first byte of the
node, which will be placed in the linked fields of the previous node.

                                                       tail 
                                                        |
                                                        v
      -----------      ------------     -----------      ------------   
     |  17  | B5 |    |  20  | C2  |   |  12  | E7 |    |  8  |  A4  |
       -----------      ------------     -----------      ------------ 
      ^ A4               B5              C2               E7      |
      |                                                           v
       <-----------------------------------------------------------

Circular Singly Linked Lists have an interesting property.  You can use the
SAME CODE for both insertion and removal.

INSERTION: 

Given the above list and a new node pointed to by 'p' ...

        -----------      
  p--> |  22  | D4 | 
        -----------
         D4

  You will notice that the node points to ITSELF, giving us a 1 node Circular 
  Singly Linked List.

  The following code will insert the node pointed to by 'p' on the LOGICAL LEFT 
  end of the list, making it the first item in the list.

    swap(p->next, tail ->next);

in English, swap the D4 with the A4.  After the swap, we will have ...  

                                                                        tail 
                                                                         |
                                                                         v
        -----------     -----------     ------------     -----------      ------------   
  p--> |  22  | A4 |  |  17  | B5 |    |  20  | C2  |   |  12  | E7 |    |  8  |  D4  |
        -----------    -----------      ------------     -----------      ------------ 
       ^D4             A4               B5               C2               E7      |
       |                                                                          v
        <-------------------------------------------------------------------------

	Since tail->next points to the FIRST item in the list, then the node pointed to
	by 'p' is the first item in the list, hence 'insert on the left'.

REMOVAL:

With deletion, you use the same code,  swap(p->next,tail->next)  and you will be
right back where you started, i.e. you will have 2 lists, one pointed to by 'tail'
and one pointed to by p. This removal can be thought of as 'remove from the left'.

  A Circular Singly Linked List can be used to implement a stack (of any size).
  Insert would be a push, and Remove would be a pop.

end.