A linked list is a data structure consisting of a group of nodes, which together represent a sequence. There are two general variants of linked lists - single and doubly linked, depending on whether each node has only a reference to the next node or to both the next and the previous node in the list. Both single and doubly linked lists can be linear (in the case of which they have a head and tail nodes) or circular (ring).

In NOV the NChain<T> class implements a doubly linked linear or circular list, that is for simplicity called chain. NOV does not implement single linked lists, because of the relatively small overhead of doubly linked lists and also because single linked lists have a generally smaller range of applications, that can all be replicated by a doubly linked list. The following image represents the chain objects organization:

figure 1. Chain objects diagram

The nodes of the chain are represented by instances of the NChainNode<T> class, each of which holds references to the previous and next nodes in the chain accessible from the PrevNode and NextNode properties respectively. For the head node the PrevNode property always returns null. Similarly, for the tail node the NextNode property always returns null.  The NChainNode<T> class provides the PrevRingNode and NextRingNode properties, that help you threat each chain as a circular doubly linked list. The PrevRingNode returns the PrevNode reference if it is not null, otherwise it returns the TailNode. Similarly, the NextRingNode returns the NextNode reference if it is not null, otherwise it returns the HeadNode.

The NChain<T> object holds references to the head and tail nodes of the chain, accessible from the HeadNode and TailNode properties respectively. Note that it does not store any references to the internal nodes in the chain and that is why indexed access to the internal nodes in the chain is achieved in 0(N/2) time. However NChain<T> provides methods that help you insert nodes before and after a certain other node and also remove certain nodes that is achieved in constant time. That is why chains are primary used for small in size but very dynamic structures, since inserting and removing nodes is really fast (always performed at constant time).

Each instance of the NChainNode<T> class, holds an Item reference (datum), where the Item is an instance of the of the generic T argument type.  If you view only the items contained by the chain nodes, you can see that they form a generic list. This list is represented by the NChainList<T> class a reference to which can be obtained from the Items property of the NChain<T> object. The NChain<T> instance that backs the items of a NChainList<T> can be accessed by the Chain property of the NChainList<T> object. The following code example shows how to add/removes nodes and the relationship between the NChain<T> and NChainList<T> objects:

void TestChain()
{
    // create a chain of strings
    NChain<string> chain = new NChain<string>();

    // push two nodes to the back and one node to the front of the chain.
    NChainNode<string> northAmericaNode = chain.PushBack("North America");
    NChainNode<string> europeNode = chain.PushBack("Europe");
    NChainNode<string> asiaNode = chain.PushFront("Asia");

    // The output is:
    // Asia
    // North America
    // Europe
    OutputChain(chain);

    // use the items list to add and insert nodes
    chain.Items.Add("South America");
    chain.Items.Insert(1, "Australia");

    // The output is:
    // Asia
    // Australia
    // North America
    // Europe
    // South America
    OutputChain(chain);

    // use the chain and items to remove nodes.
    chain.Remove(northAmericaNode);
    chain.Items.Remove("Asia");
    chain.Items.RemoveAt(0);

    // The output is:
    // Europe
    // South America
    OutputChain(chain);
}
void OutputChain(NChain<string> chain)
{
    NChainNode<string> cur = chain.HeadNode;
    Console.WriteLine("----Chain Items Start----");
    while (cur != null)
    {
        Console.WriteLine(cur.Item);
        cur = cur.NextNode;
    }
    Console.WriteLine("----Chain Items End----");
}