Lists

[Previous] [Next]

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; 

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.

How do linked lists solve the problem of fast item insertion and removal? Inserting an item midway through the list doesn't require any items to be shifted upward in memory; it simply requires that the pointers stored in the items before and after the insertion point be adjusted to reference the new item. Removing an item is equally efficient, requiring nothing more than the adjustment of two pointers. Compare this to inserting an item into the middle of an array, which could require a memcpy involving tens, hundreds, or perhaps thousands of items to make room for one new item, and the benefits should be obvious.

Nearly every programmer has, at some point in his or her career, implemented a linked list. Everyone should do it once, but no one should have to do it more than once. Fortunately, many class libraries, including MFC, provide canned implementations of linked lists. As an MFC programmer, you can sleep well tonight knowing that you'll probably never have to write a linked list from scratch again.

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

MFC lists are doubly linked for fast forward and backward traversal. Positions in the list are identified by abstract values called POSITIONs. For a list, a POSITION is actually a pointer to a CNode data structure representing one item in the list. CNode contains three fields: a pointer to the next CNode structure in the list, a pointer to the previous CNode structure, and a pointer to the item data. Insertions at the head of the list, the tail, or at a specified POSITION are fast and efficient. Lists can also be searched, but because searches are performed by traversing the list sequentially and examining its items one by one, they can be time-consuming if the list is long.

I'll use CStringList to demonstrate how the list classes are used, but keep in mind that the principles demonstrated here apply to the other list classes as well. The following example creates a CStringList object and adds 10 strings to it:

 // Schools of the Southeastern Conference const TCHAR szSchools[][20] = {     _T ("Alabama"),     _T ("Arkansas"),     _T ("Florida"),     _T ("Georgia"),     _T ("Kentucky"),     _T ("Mississippi"),     _T ("Mississippi State"),     _T ("South Carolina"),     _T ("Tennessee"),     _T ("Vanderbilt"), }; CStringList list; for (int i=0; i<10; i++)     list.AddTail (szSchools[i]); 

The AddTail function adds an item (or all the items in another linked list) to the end of the list. To add items to the head of the list, use the AddHead function instead. Removing an item from the head or tail is as simple as calling RemoveHead or RemoveTail. The RemoveAll function removes all the items in one fell swoop.

Each time a string is added to a CStringList, MFC copies the string to a CString and stores it in the corresponding CNode structure. Therefore, it's perfectly acceptable to allow the strings that you initialize a list with to go out of scope once the list is built.

Once a list is created, you can iterate through it forward and backward using the GetNext and GetPrev functions. Both accept a POSITION value identifying the current position in the list and return the item at that position. Each also updates the POSITION value to reference the next or previous item. You can retrieve the POSITION of the first or last item in the list with GetHeadPosition or GetTailPosition. The following statements enumerate the items in the list from first to last, writing each string retrieved from the list to the debug output window using MFC's TRACE macro:

 POSITION pos = list.GetHeadPosition (); while (pos != NULL) {     CString string = list.GetNext (pos);     TRACE (_T ("%s\n"), string); } 

Walking the list backward is equally simple:

 POSITION pos = list.GetTailPosition (); while (pos != NULL) {     CString string = list.GetPrev (pos);     TRACE (_T ("%s\n"), string); } 

If you simply want to retrieve the first or last item in the list, you can use the list's GetHead or GetTail function. Neither requires a POSITION value as input because the position is implied in the call.

Given a POSITION value pos identifying a particular item, you can use the list's At functions to retrieve, modify, or delete the item:

 CString string = list.GetAt (pos);       // Retrieve the item. list.SetAt (pos, _T ("Florida State"));  // Change it. list.RemoveAt (pos);                     // Delete it. 

You can also use InsertBefore or InsertAfter to insert items into the list:

 list.InsertBefore (pos, _T ("Florida State"));  // Insert at pos. list.InsertAfter (pos, _T ("Florida State"));   // Insert after pos. 

Because of the nature of linked lists, insertions and removals performed this way are fast.

MFC's list classes include two member functions that you can use to perform searches. FindIndex accepts a 0-based index and returns the POSITION of the item at the corresponding location in the list. Find searches the list for an item matching an input you specify and returns its POSITION. For string lists, Find compares strings. For pointer lists, it compares pointers; it does not dereference the pointers and compare the items that they point to. Searching a string list for "Tennessee" requires just one function call:

 POSITION pos = list.Find (_T ("Tennessee")); 

By default, Find searches the list from beginning to end. If you'd like, you can specify an alternate starting point in the function's second parameter. But be aware that if the item you're looking for occurs before the starting POSITION, Find won't find it because searches don't wrap around to the beginning of the list.

You can find out how many elements a list contains with the GetCount function. If GetCount returns 0, the list is empty. A quick way to test for an empty list is to call IsEmpty.

Creating Type-Safe List Classes with CList

You can create type-safe list classes for the data types of your choice from MFC's CList class. Here's an example involving a linked list of CPoint objects:

 CList<CPoint, CPoint&> list; // Populate the list. for (int i=0; i<10; i++)     list.AddTail (CPoint (i*10, 0)); // Enumerate the items in the list. POSITION pos = list.GetHeadPosition (); while (pos != NULL) {     CPoint point = list.GetNext (pos);     TRACE (_T ("x=%d, y=%d\n"), point.x, point.y); } 

As with CArray, the first template parameter specifies the data type (CPoint objects) and the second specifies how items are passed in parameter lists (by reference).

If you use classes rather than primitive data types in a CList and you call the list's Find function, your code won't compile unless one of the following conditions is true:

• The class has an overloaded == operator that performs a comparison to a like object.
• You override the template function CompareElements with a type-specific version that compares two instances of the class.

The first method—overloading the == operator—is the more common of the two and has already been done for you in MFC classes such as CPoint and CString. If you write a class yourself, you must do the operator overloading. Here's a modified version of CPoint3D that overloads the comparison operator for compatibility with CList::Find:

 class CPoint3D { public:     CPoint3D ()     {         x = y = z = 0;     }     CPoint3D (int xPos, int yPos, int zPos)     {         x = xPos;         y = yPos;         z = zPos;     }     operator== (CPoint3D point) const     {         return (x == point.x && y == point.y && z == point.z);     }     int x, y, z; }; 

The alternative to overloading the comparison operator is to override the global CompareElements function, as demonstrated here:

 class CPoint3D { public:     CPoint3D ()     {         x = y = z = 0;     }     CPoint3D (int xPos, int yPos, int zPos)     {         x = xPos;         y = yPos;         z = zPos;     }     // Note: No operator==     int x, y, z; }; BOOL AFXAPI CompareElements (const CPoint3D* p1, const CPoint3D* p2) {     return (p1->x == p2->x && p1->y == p2->y && p1->z == p2->z); } 

Overriding CompareElements eliminates the need for operator overloading because the default implementation of CompareElements, which is called by CList::Find, compares items using the comparison operator. If you override CompareElements and don't use == in the override, you don't need to overload the == operator either.