MFC List classes

Lists

The InsertAt and RemoveAt functions make it easy to add items to an array and to take them away. But the ease with which items are inserted and removed comes at a cost: when items are inserted or removed in the middle of an array, items higher in the array must be shifted upward or downward in memory. The performance penalty incurred when manipulating large arrays in this manner can be quite expensive.

A classic solution to the problem of maintaining ordered lists that support fast item insertion and removal is the linked list. A linked list is a collection of items that contain pointers to other items. In a singly linked list, each item contains a pointer to the next item in the list. Moving forward through a singly linked list is fast because moving to the next item is a simple matter of extracting that item's address from the current item. To support fast forward and backward traversal, many lists are doubly linked—that is, each item contains a pointer to the previous item in the list as well as to the next item. Given the address of the first item in the list (the head), it's a simple matter to enumerate the items in the list using code like this:

item* pItem = GetHead ();
while (pItem != NULL)
pItem = pItem->pNextItem;




Conversely, given the address of the final item in the list (the tail), a doubly linked list can be traversed in reverse order, like this:

item* pItem = GetTail ();
while (pItem != NULL)
pItem = pItem->pPrevItem;





The MFC List Classes
The MFC template class CList implements a generic linked list that can be customized to work with any data type. MFC also provides the following nontemplatized list classes to deal with specific data types. These classes are provided primarily for compatibility with older versions of MFC and aren't used very often in modern MFC applications.

Type-Specific MFC List Classes

Class Name Data Type
CObList CObject pointers
CPtrList void pointers
CStringList CStrings






These examples assume that the list doesn't wrap around on itself—that is, that the pNextItem pointer in the final item and the pPrevItem pointer in the first item are equal to NULL. Some linked lists form a circular chain of items by connecting the first and last items.