MFC - Linked Lists
A linked list is a linear data structure where each element is a separate object. Each element [we will call it a node] of a list comprises two items the data and a reference to the next node. The last node has a reference to null.
A linked list is a data structure consisting of a group of nodes which together represent a sequence. It is a way to store data with structures so that the programmer can automatically create a new place to store data whenever necessary. Some of its salient features are
Linked List is a sequence of links which contains items.
Each link contains a connection to another link.
Each item in the list is called a node.
If the list contains at least one node, then a new node is positioned as the last element in the list.
If the list has only one node, that node represents the first and the last item.
There are two types of link list
Singly Linked List
Singly Linked Lists are a type of data structure. In a singly linked list, each node in the list stores the contents of the node and a pointer or reference to the next node in the list.
Doubly Linked List
A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields that are references to the previous and to the next node in the sequence of nodes.
CList Class
MFC provides a class CList which is a template linked list implementation and works perfectly. CList lists behave like doubly-linked lists. A variable of type POSITION is a key for the list. You can use a POSITION variable as an iterator to traverse a list sequentially and as a bookmark to hold a place.
| 1 | AddHead Adds an element [or all the elements in another list] to the head of the list [makes a new head]. |
| 2 | AddTail Adds an element [or all the elements in another list] to the tail of the list [makes a new tail]. |
| 3 | Find Gets the position of an element specified by pointer value. |
| 4 | FindIndex Gets the position of an element specified by a zero-based index. |
| 5 | GetAt Gets the element at a given position. |
| 6 | GetCount Returns the number of elements in this list. |
| 7 | GetHead Returns the head element of the list [cannot be empty]. |
| 8 | GetHeadPosition Returns the position of the head element of the list. |
| 9 | GetNext Gets the next element for iterating. |
| 10 | GetPrev Gets the previous element for iterating. |
| 11 | GetSize Returns the number of elements in this list. |
| 12 | GetTail Returns the tail element of the list [cannot be empty]. |
| 13 | GetTailPosition Returns the position of the tail element of the list. |
| 14 | InsertAfter Inserts a new element after a given position. |
| 15 | InsertBefore Inserts a new element before a given position. |
| 16 | IsEmpty Tests for the empty list condition [no elements]. |
| 17 | RemoveAll Removes all the elements from this list. |
| 18 | RemoveAt Removes an element from this list, specified by position. |
| 19 | RemoveHead Removes the element from the head of the list. |
| 20 | RemoveTail Removes the element from the tail of the list. |
| 21 | SetAt Sets the element at a given position. |
Following are the different operations on CList objects
Create CList Object
To create a collection of CList values or objects, you must first decide the type of values of the collection. You can use one of the existing primitive data types such as int, CString, double etc. as shown below in the following code.
CListm_list;Add items
To add an item, you can use CList::AddTail[] function. It adds an item at the end of the list. To add an element at the start of the list, you can use the CList::AddHead[] function. In the OnInitDialog[] CList, object is created and four values are added as shown in the following code.
CListm_list; //Add items to the list m_list.AddTail[100.75]; m_list.AddTail[85.26]; m_list.AddTail[95.78]; m_list.AddTail[90.1];Retrieve Items
A variable of type POSITION is a key for the list. You can use a POSITION variable as an iterator to traverse a list sequentially.
Step 1 To retrieve the element from the list, we can use the following code which will retrieve all the values.
//iterate the list POSITION pos = m_list.GetHeadPosition[]; while [pos] { double nData = m_list.GetNext[pos]; CString strVal; strVal.Format[L"%.2f\n", nData]; m_strText.Append[strVal]; }Step 2 Here is the complete CMFCCListDemoDlg::OnInitDialog[] function.
BOOL CMFCCListDemoDlg::OnInitDialog[] { CDialogEx::OnInitDialog[]; // Set the icon for this dialog. The framework does this automatically // when the application's main window is not a dialog SetIcon[m_hIcon, TRUE]; // Set big icon SetIcon[m_hIcon, FALSE]; // Set small icon // TODO: Add extra initialization here CListm_list; //Add items to the list m_list.AddTail[100.75]; m_list.AddTail[85.26]; m_list.AddTail[95.78]; m_list.AddTail[90.1]; //iterate the list POSITION pos = m_list.GetHeadPosition[]; while [pos] { double nData = m_list.GetNext[pos]; CString strVal; strVal.Format[L"%.f\n", nData]; m_strText.Append[strVal]; } UpdateData[FALSE]; return TRUE; // return TRUE unless you set the focus to a control }Step 3 When the above code is compiled and executed, you will see the following output.
Add Items in the Middle
To add item in the middle of the list, you can use the CList::.InsertAfter[] and CList::.InsertBefore[] functions. It takes two paramerters First, the position [where it can be added] and Second, the value.
Step 1 Let us insert a new item as shown in the followng code.
BOOL CMFCCListDemoDlg::OnInitDialog[] { CDialogEx::OnInitDialog[]; // Set the icon for this dialog. The framework does this automatically // when the application's main window is not a dialog SetIcon[m_hIcon, TRUE]; // Set big icon SetIcon[m_hIcon, FALSE]; // Set small icon // TODO: Add extra initialization here CListm_list; //Add items to the list m_list.AddTail[100.75]; m_list.AddTail[85.26]; m_list.AddTail[95.78]; m_list.AddTail[90.1]; POSITION position = m_list.Find[85.26]; m_list.InsertBefore[position, 200.0]; m_list.InsertAfter[position, 300.0]; //iterate the list POSITION pos = m_list.GetHeadPosition[]; while [pos] { double nData = m_list.GetNext[pos]; CString strVal; strVal.Format[L"%.2f\n", nData]; m_strText.Append[strVal]; } UpdateData[FALSE]; return TRUE; // return TRUE unless you set the focus to a control }Step 2 You can now see see that we first retrieved the position of value 85.26 and then inserted one element before and one element after that value.
Step 3 When the above code is compiled and executed, you will see the following output.
Update Item Value
To update item at the middle of array, you can use the CArray::.SetAt[] function. It takes two paramerters First, the position and Second, the value.
Let us update the 300.00 to 400 in the list as shown in the following code.
BOOL CMFCCListDemoDlg::OnInitDialog[] { CDialogEx::OnInitDialog[]; // Set the icon for this dialog. The framework does this automatically // when the application's main window is not a dialog SetIcon[m_hIcon, TRUE]; // Set big icon SetIcon[m_hIcon, FALSE]; // Set small icon // TODO: Add extra initialization here CListm_list; //Add items to the list m_list.AddTail[100.75]; m_list.AddTail[85.26]; m_list.AddTail[95.78]; m_list.AddTail[90.1]; POSITION position = m_list.Find[85.26]; m_list.InsertBefore[position, 200.0]; m_list.InsertAfter[position, 300.0]; position = m_list.Find[300.00]; m_list.SetAt[position, 400.00]; //iterate the list POSITION pos = m_list.GetHeadPosition[]; while [pos] { double nData = m_list.GetNext[pos]; CString strVal; strVal.Format[L"%.2f\n", nData]; m_strText.Append[strVal]; } UpdateData[FALSE]; return TRUE; // return TRUE unless you set the focus to a control }When the above code is compiled and executed, you will see the following output. You can now see that the value of 300.00 is updated to 400.00.
Remove Items
To remove any particular item, you can use CList::RemoveAt[] function. To remove all the element from the list, CList::RemoveAll[] function can be used.
Let us remove the element, which has 95.78 as its value.
BOOL CMFCCListDemoDlg::OnInitDialog[] { CDialogEx::OnInitDialog[]; // Set the icon for this dialog. The framework does this automatically // when the application's main window is not a dialog SetIcon[m_hIcon, TRUE]; // Set big icon SetIcon[m_hIcon, FALSE]; // Set small icon // TODO: Add extra initialization here CListm_list; //Add items to the list m_list.AddTail[100.75]; m_list.AddTail[85.26]; m_list.AddTail[95.78]; m_list.AddTail[90.1]; POSITION position = m_list.Find[85.26]; m_list.InsertBefore[position, 200.0]; m_list.InsertAfter[position, 300.0]; position = m_list.Find[300.00]; m_list.SetAt[position, 400.00]; position = m_list.Find[95.78]; m_list.RemoveAt[position]; //iterate the list POSITION pos = m_list.GetHeadPosition[]; while [pos] { double nData = m_list.GetNext[pos]; CString strVal; strVal.Format[L"%.2f\n", nData]; m_strText.Append[strVal]; } UpdateData[FALSE]; return TRUE; // return TRUE unless you set the focus to a control }When the above code is compiled and executed, you will see the following output. You can now see that the value of 95.78 is no longer part of the list.