				File List
				=========

test.c
        This forms a singly linked list.

        Performance:
        O(n) operations for adding (appending).

test2.c
	This forms a doubly linked list.
	
	Performance: 
	O(n) operations for adding (appending).

test3.c
        This forms a doubly linked ring.

        Performance:
        O(1) operations for adding (appending).

test4.c
        This forms a doubly linked semi-ring.

        i.e. root's previous pointer pointing to the last node, but the
        last node doesn't point to root. (i.e. a semi-ring.) This makes it
        easier to traverse and easier to understand, since it has the same
        traversal method as a normal linked list.

        Performance:
        O(1) operations for adding (appending).


--------------------------------------------------------------------------


				Performance
				===========

Which is the best to use?
-------------------------

To answer that, we must first understand the advantages and disadvantages
of each type of link list.

Singly Linked List:
-------------------

In most cases, a plain linked list is absolutely useless. Even if you're
constrained with memory usage, you cannot append fast enough to make it
worthwhile. Whilst the singly linked list saves the overhead of the doubly
linked list by a pointer per node, the savings usually go unnoticed since
it would require a large amount of nodes to be worthwhile, but because
it's poor in appending, you may just give up. 

It's advantage lies in the fact that it's O(1) for prepending (i.e
insertion at position 1). It similarly also has O(1) for removal of
position 1. Because of this, it behaves well as a LIFO stack. (i.e. push/pop
opcodes in the cpu do similar things, except this is the link list method.)
Because using a singly linked list saves the overhead of the extra "previous"
pointer, this is often used to represent LIFO stacks.

Doubly Linked List:
-------------------

Similar to the singly linked list in advantage and disadvantage, however
there is an advantage only available to the doubly linked list. It has the
ability to easily remove nodes without having to save the previous node
into a temporary variable. Some say, this advantage of saving the previous
node is not worth saving the previous node for all nodes. But if there's
alot of insertions or deletions at any point within the list and you have
at least the node's pointer in question, then these operations are all
O(1), whereas in a singly linked list these are expensive O(n) (n
operations in worst case) operations.

But again, it still has the disadvantage of any linked list: expensive
appending with O(n) operations.

Doubly Linked Ring:
-------------------

This has all the advantages of a doubly linked list with one significant
advantage: O(1) appending.

Linked Semi-Rings:
------------------

Semi-rings can be doubly or singly linked, as long as it has saved the
last node in the root node. It's insertion/deletion performance is based
on whether or not it is doubly or singly linked. A semi-ring has the
advantage of O(1) appending regardless of whether it's doubly or singly
linked.

---------------------------------------------------------------------------

				Terms
				=====

Singly: a list or ring whereby only the *next pointer is used.

Doubly: a list or ring whereby both *next and *prev pointers
are used.

Linked List: a list created from a chain of pointers where
the list is terminated with a null pointer. A linked list may be
singly or doubly linked.

Linked Ring: a ring created from a chain of pointers where
the last node is connected to the root node. A linked ring must be
doubly linked.

Linked Semi-Ring: a list similar to a ring where only the dummy root
node's previous pointer points to the last node. A semi-ring may be singly
or doubly linked, but it requires the dummy/root node to store the pointer
of the last node.



