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;
};
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
{
private:
LinkedListNode __nogc* m_pHead;
LinkedListNode __nogc* m_pTail;
int m_count;
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
{
private:
LinkedList* m_list;
LinkedListNode* m_pNode;
LinkedListNode* m_pHead;
int m_version;
public:
LinkedListEnumerator(LinkedList* list, LinkedListNode* pHead);
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.'