A linked list collection class in MC++

• Download source files - 18 Kb
• Download demo project - 44 Kb

Introduction

If you examine the functionality of the ArrayList class, you'll find that it's quite ridiculous. When the array reaches maximum capacity, it creates a new array with double the capacity, copies the items from the old array into the new one and discards the old array. Convoluted and messy.

Every C/C++ programmer knows that the only way to make structures that are 'really' dynamic is to use linked lists. I've created a class in Managed C++ that does just that. Furthermore, I've included a TypedListBase abstract class from which you can inherit to make strongly typed collections. All this is put into a .NET dll and I've a program, written in C# that I used to test it.

The classes really don't do anything more than implement the IList, ICollection, IEnumerable and ICloneable. Therefore, it behaves identically to ArrayList as far as the programmer who's using it is concerned. I'm not getting into the details of the methods and properties of these interfaces here, but they're pretty straight-forward and self-explanatory, and the .NET Framework reference explains them quite well.

Implementing LinkedList

The LinkedList class maintains a linked list of LinkedListNode structures shown below:

__nogc struct LinkedListNode
{
    LinkedListNode __nogc* pNext;
    LinkedListNode __nogc* pPrev;
    gcroot<object*> item; // #include <vcclr.h> in StdAfx.h  

                          // makes this template available.

};

LinkedListNode::item stores the objects. The gcroot template is required to hold a managed object in an unmanaged struct/class.

The linked list class includes the following items, besides a constructor, destructor and the interface implementations:

public __gc __sealed class LinkedList : public IList, 
    public IEnumerable, public ICollection, public ICloneable
{
// Implementation

private:
    LinkedListNode __nogc* m_pHead;
    // Future versions will support reverse enumeration, 

    // like the STL classes.

    // Therefore, we need to store the tail as well.

    LinkedListNode __nogc* m_pTail;
    int m_count;
    // Used by the enumerator to check 

    // whether the list is modified after the

    // enumerator has been created.

    int m_version;	

    LinkedListNode* GetNodeAt(int index);
public:
    int GetVersion();

. . .
. . .

Implementing the enumerator

The code for LinkedList::GetEnumerator is:

IEnumerator* LinkedList::GetEnumerator()
{
    return new LinkedListEnumerator(this, m_pHead);
}

This class requires a pointer to the list it's working on and a pointer to the head. The class declaration is given below:

private  __gc __sealed class LinkedListEnumerator : public IEnumerator
{
// Implementation

private:
    LinkedList* m_list;
    LinkedListNode* m_pNode;
    LinkedListNode* m_pHead;
    int m_version;
public:
    LinkedListEnumerator(LinkedList* list, LinkedListNode* pHead);
    // Overrides of IEnumerator

public:
    __property Object* get_Current();
    bool MoveNext();
    void Reset();
};

The constructor calls list->GetVersion() and stores the return value in m_version. This number represents the state of the list when the enumerator is created. When the list is modified (by calling Add, Remove, Clear, etc.) the version is incremented. The IEnumerator functions check to make sure that the stored version and the current version are the same:

if (m_version != m_list->GetVersion())
    throw new InvalidOperationException(
        S"The list was modified after the enumerator was created.");

If the list is modified after the enumerator is created, there is a chance that LinkedListEnumerator::m_pNode and m_pHead are invalid, so the exception is thrown. This is really stretching it, but if the list is modified over 4 billion times (I think that's the capacity of an int), there will be an overflow. Well, this is how Microsoft implemented this behavior in ArrayList.

Testing the DLL with the program

Check out the program I've included. It has a GUI and lets you add strings to the list one by one and can add 500 random strings as well. It tests all the functions and lets you enumerate through the list using multiply threads. Try adding items while some threads are enumerating. They will throw InvalidOperationException, but an enumerator created after the items were added will run 'peacefully.'