Linked List Class

CLinkedList is an intrusive doubly-linked list with support for adding items to multiple lists. It fully supports SimpleLib's semantics classes.

template <class T, class TSem=SValue, CChain<T> T::* pMember=&T::m_Chain>
class CLinkedList

In order for items to be placed in a CLinkedList collection, they must contain a CChain member variable to hold the next and previous pointers.

class CMyItem
{
	CChain<CMyItem>	m_Chain;
}

To declare the linked list:

CLinkedList<CMyItem>	List;

Or an owned pointer list:

CLinkedList<CMyItem, SOwnedPtr>	List;

In order to add items to more than one list, you must add a CChain member variable for each list: (Note this functionality is not available on Microsoft Visual C++ 6.0).

class CMyItem
{
	CChain<CMyItem>	m_Chain1;
	CChain<CMyItem> m_Chain2;
}

and specify which chain each list is to use:

CLinkedList<CMyItem, SValue, &CMyItem::m_Chain1> List1;
CLinkedList<CMyItem, SValue, &CMyItem::m_Chain2> List2;

Add items to a list with the Add, Prepend or Insert methods:

List.Add(new CItem());                     // Adds to end of list
List.Prepend(new CItem());                 // Adds to head of list
List.Insert(new CItem(), List.GetLast());  // Insert before the last item</pre>

CLinkedList supports pseudo random access using the [] operator or GetAt method. To iterate through a list use the following familiar syntax:

for (int i=0; i<List.GetSize(); i++)
{
	List[i]->DoSomething();
}

It is safe to insert and/or delete a list while using pseudo random access.

You can also iterate forward through the list using MoveFirst, MoveNext, IsEOF and Current()

for (List.MoveFirst(); !List.IsEOF(); List.MoveNext())
{
	List.Current()->DoSomething();
}

Reverse iteration is similar:

for (List.MoveLast(); !List.IsBOF(); List.MovePrev())
{
	List.Current()->DoSomething();
}

Note when iterating a list in this manner, the current position is maintained by the list itself and it is therefore not possible to have multiple loops iterating the list simultaneously. Be careful not to call another function that iterates the list while inside an iterating loop.

It is safe to insert, remove or detach items while iterating the list (in either direction):

for (List.MoveLast(); !List.IsBOF(); List.MovePrev())
{
	if (SomeCondition(Current()))
		List.Remove(Current());
}

Other useful methods include:

• RemoveAll - Removes all elements from the list.
• IsEmpty - Checks if the list contains any elements.
• GetSize - Returns the number of elements in the list.
• Contains - Checks for the existence of an item in the list.
• GetFirst - Returns the first element in the list (or NULL if empty).
• GetLast - Returns the last element in the list.