• Each item in the list is called a node (this is not an actual rule but a habit or a suggestion)

• If the list is empty, the new node added becomes the first element
• If the list contains at least one node, whenever a new node is added, that new node is positioned as the last in the list. This is because the new node is added next to the existing node
• If the list has only one node, that node represents the first and the last item

• If the list contains more than one node, each item holds a reference to the object next to it

In reality, there are various types of linked lists. A singly linked list is a one-way directional list where each item points (only) to the item next to it (in a somewhat right direction). The description we just gave is conform to a singly linked list. Another type is the doubly linked list in which:

• Each item in the list is called a node (again, this is not a real rule)
• If the list is empty, the first node is added as the first in the collection
• If the list contains one node, that node has two references to itself: one reference as the next and the other reference as its previous
• If the list contains two nodes:
  • One node is the first. That first node holds a reference to the other node as its next
  • The other node is the last. That last node holds a reference to the first node as its previous item
• If the list contains more than two nodes:
  • The first node holds a reference to the next node (in the right direction)
  • The last node holds a reference to the node previous to it (in the left direction)
  • Each node holds two references: one reference to the previous node and one reference to the next node

The last type of linked list is called a circular linked list. This list is primarily created as either a singly linked list or a doubly linked list:

• In a circular singly linked list, the list primarily follows the rules of a singly linked list. then:
  • If the list has two nodes, the first node holds a reference to the other node as its next and its previous node
  • If the list has more than one node:
    • The first node holds a reference to the last node as its previous node
    • The last node holds a reference to first node as its next

• In a doubly linked list, the list includes the rules of the doubly linked list and combines with those of the circular singly linked list:
  • The first node has a reference to the last node as its previous node
  • The last node has a reference to the first node as its next node
  • Each node has two references: its previous and its next nodes

1. Start Microsoft Visual Studio
2. To create a new application, on the main menu, click File -> New Project...
3. In the middle list, click MFC Application. Set the Name to ApartmentsForRent1
4. Click OK
5. In the first page of the wizard, click Next
6. In the second page of the wizard, click Dialog-Based
7. Click Next
8. In the third page of the wizard, click Next
9. In the fourth page, click Next
10. In the last page, click Finish
11. Click the TODO line and press Delete
12. While the OK button is selected, press Delete
13. Change the caption of the Cancel button to Close
14. Design the dialog box as follows:
     

    Control ID Caption Other Properties Static Text   Unit #:   Edit Control IDC_UNITNUMBER     Static Text   Unit Type:   Edit Control IDC_UNITTYPE     Static Text   Bedrooms:   Edit Control IDC_BEDROOMS   Align Text: Right Static Control   Bathrooms:   Edit Control IDC_BATHROOMS   Align Text: Right Static Text   Condition:   Edit Control IDC_CONDITION     Static Text   Monthly Rent:   Edit Control IDC_MONTHLYRENT   Align Text: Right Button IDC_FIRST | <   Button IDC_PREVIOUS <<   Button IDC_NEXT >>   Button IDC_LAST > |   Button IDCANCEL Close

15. Right-click each edit control and the 000 of 000 static control then click Add Variable...
16. Create the Value variables as follows:
     

    ID	Value Variable	Variable Type
    IDC_UNITNUMBER	m_UnitNumber	CString
    IDC_UNITTYPE	m_UnitType	CString
    IDC_BEDROOMS	m_Bedrooms	int
    IDC_BATHROOMS	m_Bathrooms	float
    IDC_CONDITION	m_Condition	CString
    IDC_MONTHLYRENT	m_MonthlyRent	double

17. In the Solution Explorer, right-click ApartmentsForRent1 -> Add -> Class...
18. In the Add Class dialog box, click C++ Class and click Add
    
19. Set the Class Name to CApartment
20. Click Finish
21. Change the StoreItem.h header file as follows:

    #pragma once
    class CApartment
    {
    public:
    	CApartment(void);
    	CApartment(CString number, CString type, int beds,
    		   float baths, CString status, double rate);
    	CApartment(const CApartment &unit);
    	CApartment &operator=(const CApartment& unit);
    	~CApartment(void);
    
    public:
    	CString UnitNumber;
    	CString UnitType;
    	int Bedrooms;
    	float Bathrooms;
    	CString Condition;
    	double  MonthlyRent;
    };

22. Access the StoreItem.cpp source file and change it as follows:
    

    #include "StdAfx.h"
    #include "Apartment.h"
    
    CApartment::CApartment(void)
    	: UnitNumber(_T("")), UnitType(_T("")),
    	  Bedrooms(0), Bathrooms(0.00F),
    	  Condition(_T("")), MonthlyRent(0.00)
    {
    }
    
    CApartment::CApartment(CString number, CString type, int beds,
    		       float baths, CString status, double rate)
       : UnitNumber(number), UnitType(type), 
         Bedrooms(beds), Bathrooms(baths),
         Condition(status), MonthlyRent(rate)
    {
    }
    
    CApartment::CApartment(const CApartment &unit)
    {
    	UnitNumber = unit.UnitNumber;
    	UnitType = unit.UnitType;
    	Bedrooms = unit.Bedrooms;
    	Bathrooms = unit.Bathrooms;
    	Condition = unit.Condition;
    	MonthlyRent = unit.MonthlyRent;
    }
    
    CApartment &CApartment::operator=(const CApartment& unit)
    {
    	UnitNumber = unit.UnitNumber;
    	UnitType = unit.UnitType;
    	Bedrooms = unit.Bedrooms;
    	Bathrooms = unit.Bathrooms;
    	Condition = unit.Condition;
    	MonthlyRent = unit.MonthlyRent;
    
    	return *this;
    }
    
    CApartment::~CApartment(void)
    {
    }

Although you can create a linked list collection class from scratch, to assist you, the MFC library provides many classes. Some of them use templates and some don't. The primary template-based class is named CList. If you plan to use it, include the afxtempl.h header file in your project.

Since CList is a template-based class, to use it, declare its variable and use the angle brackets. Here is an example:

void CExampleDlg::OnBnClickedLinkedlistBtn()
{
    CList<double, double> numbers;
}

1. In the Solution Explorer, double-click stdafx.h
2. Include the afxtempl.h template library:
   

   // stdafx.h : include file for standard system include files,
   // or project specific include files that are used frequently,
   // but are changed infrequently
   
   #pragma once
   
   #ifndef _SECURE_ATL
   #define _SECURE_ATL 1
   #endif
   
   #ifndef VC_EXTRALEAN
   #define VC_EXTRALEAN
   #endif
   
   #include "targetver.h"
   
   #define _ATL_CSTRING_EXPLICIT_CONSTRUCTORS
   
   #define _AFX_ALL_WARNINGS
   
   #include <afxwin.h>         // MFC core and standard components
   #include <afxext.h>         // MFC extensions
   
   #include <afxdisp.h>        // MFC Automation classes
   
   #ifndef _AFX_NO_OLE_SUPPORT
   #include <afxdtctl.h>
   #endif
   #ifndef _AFX_NO_AFXCMN_SUPPORT
   #include <afxcmn.h>             // MFC support for Windows Common Controls
   #endif // _AFX_NO_AFXCMN_SUPPORT
   
   #include <afxcontrolbars.h>     // MFC support for ribbons and control bars
   
   #include <afxtempl.h>

3. In the Solution Explorer, double-click ApartmentsForRent1Dlg.h
4. In the header file, declare a private CList variable named apartments as follows:
   

   // AppartmentsForRent1Dlg.h : header file
   //
   
   #pragma once
   #include "Apartment.h"
   
   // CAppartmentsForRent1Dlg dialog
   class CAppartmentsForRent1Dlg : public CDialogEx
   {
   // Construction
   public:
   	CAppartmentsForRent1Dlg(CWnd* pParent = NULL);	// standard constructor
   
   // Dialog Data
   	enum { IDD = IDD_APPARTMENTSFORRENT1_DIALOG };
   
   	protected:
   	virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
   
   	int index;
   	POSITION CurrentPosition;
   	CList<CApartment, CApartment&> apartments;
   
   // Implementation
   protected:
   	HICON m_hIcon;
   
   	// Generated message map functions
   	virtual BOOL OnInitDialog();
   	afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
   	afx_msg void OnPaint();
   	afx_msg HCURSOR OnQueryDragIcon();
   	DECLARE_MESSAGE_MAP()
   };

5. Return to the dialog box

In the CList class, a node is of type TYPE. When you declare a CList variable, that is, when you start the collection, you can specify how much memory to allocate for it. In fact, the CList class has one constructor that takes an optional argument. Its syntax is:

CList(INT_PTR nBlockSize = 10);

The constructor takes an integer as argument. Here is an example:

void CExampleDlg::OnBnClickedLinkedlistBtn()
{
    CList<double, double> numbers(5);
}

If you pass this argument, the value you provide specifies the initial capacity of the collection. This represents the intial amount of memory you request for the collection. As you add new items, if or when the compiler juges it necessary, new memory would be allocated for the variable.

Before performing any operation on a linked list, you should first check whether it has at least one element. To help you with this, the CList class is equipped with a member function named IsEmpty. Its syntax is:

BOOL IsEmpty() const;

When this member function is called, if there is no item in the list, the function returns TRUE. If there is at least one element, it returns FALSE.

In the next sections, we will see how to add new nodes to a linked list. When a node has been added, it occupies a position, which is somewhat equivalent to an index in an array. To identify the position of a node, the MFC defines a structure named POSITION. The MFC document defines the position as a key. This means that POSITION neither is an integer not does it represent the index of a node. It is just a way (a key) to identify the position of a node. This also means that you cannot directly use POSITION in a for loop the way you would use an int.

1. On the dialog box, double-click the | < button
2. Return to the dialog box and double-click the << button
3. Return to the dialog box and double-click the >> button
4. Return to the dialog box and double-click the > | button

The primary operation to perform on a linked list is to add a new node to it. To support it, the CList class is equipped with various methods. One of them is named AddTail and it is overloaded in two versions. One of them uses the following syntax:

POSITION AddTail(ARG_TYPE newElement);

This method expects the new value as argument. Here is an example of calling it:

void CExampleDlg::OnBnClickedLinkedlistBtn()
{
    CList<double, double> numbers;

    numbers.AddTail(52739.470);
}

Another version of this method is:

void AddTail(CList* pNewList);

This version expects a pointer to CList as argument. Here is an example of calling it:

void CExampleDlg::OnBnClickedLinkedlistBtn()
{
	CList<double, double> numbers;

	numbers.AddTail(52739.470);

	CList<double, double> values;

	values.AddTail(&numbers);
}

This second version of the AddTail() member function can be used to copy a CList or to assign one to another.

To let you know the number of items in a CList collection, the class is equipped with a member function named GetCount. Its syntax is:

INT_PTR GetCount() const;

When dealing with a linked list, you have many options on how to add a new node. As mentioned already, a linked list has a first node, a last node, and one or more nodes between them. All nodes have and use some references with regards to the node(s) close to them. Based on this, when adding a new node, you have to specify whether you want it as the first node, the last node, the node before a certain node, or the node after a certain one.

We saw that you could call the AddTail() member function to add a new node. In reality, there is no such a thing as simply adding a new node to a linked list. When a linked list has just been created and it is empty, it holds a reference to a NULL node. You have the option of adding a new node as the first or the last item. This would not make any difference because there is no other node in the list.

After adding a node, it becomes a reference that new nodes can use. If you call the AddTail() member function, the new node would be added after any existing node in the collection. By contrast, you can call a member function named AddHead. It is overloaded with teo versions. The syntax of one of them is:

POSITION AddHead(ARG_TYPE newElement);

This function takes an object as argument. Here is an example of calling it:

void CExampleDlg::OnBnClickedLinkedlistBtn()
{
    CList<double, double> numbers(5);

    numbers.AddTail(52739.470);
    numbers.AddTail(82.63);
    numbers.AddHead(374.0052);
    numbers.AddTail(1.864);
    numbers.AddTail(29374.04);
}

The syntax of the other version is:

void AddHead(CList* pNewList);

This version takes a CList collection as argument. If you call this version, the pNewList list will be added to the beginning of the list.

1. In the Resource View, right-click the name of the project -> Add -> Resource...
2. In the Add Resource dialog box, click Dialog and click New
3. In the Properties window, change its ID to IDD_APARTMENT
4. Design the dialog box as follows:
    

   Control ID Caption Other Properties Static Text   Unit #:   Edit Control IDC_UNITNUMBER     Static Text   Unit Type:   Edit Control IDC_UNITTYPE     Static Text   Unit Type:   Edit Control IDC_BEDROOMS   Align Text: Right Static Control   Bathrooms:   Edit Control IDC_BATHROOMS   Align Text: Right Static Text   Condition:   Edit Control IDC_CONDITION     Static Control   Monthly Rent:   Edit Control IDC_MONTHLYRENT   Align Text: Right

5. Right-click an unoccupied area of the dialog box and click Class Wizard...
6. On the right side of the MFC Class Wizard dialog box, click Add Class
7. In the Class Name, type CApartmentDlg
8. In the Base Class, select CDialogEx
9. In the Dialog ID, select IDD_APARTMENT
10. Click Finish
11. In the Class Name, make sure CItemEditorDlg is selected.
    Click the Member Variables tab
12. In the Member Variables, click IDC_ITEMNUMBER
13. Click Add Variable...
14. Set the Member Variable Name to m_UnitNumber
15. Set the Category to Value and make sure the Variable Type is set to CString
16. Click OK
17. In the same way, using the IDs in the Member Variable, add the member variables as follows:
     

    ID	Value Variable	Variable Type
    IDC_UNITNUMBER	m_UnitNumber	CString
    IDC_UNITTYPE	m_UnitType	CString
    IDC_BEDROOMS	m_Bedrooms	int
    IDC_BATHROOMS	m_Bathrooms	float
    IDC_CONDITION	m_Condition	CString
    IDC_MONTHLYRENT	m_MonthlyRent	double

     
    
18. Click OK
19. Display the first dialog box
20. Add four buttons and change its design as follows:
     

    Control Caption ID Button Add First... IDC_ADDFIRST Button Add Last... IDC_ADDLAST Button Insert Before... IDC_INSERTBEFORE Button Insert After... IDC_INSERTAFTER

21. Double-click the Add First... button and implement its event as follows:

    #include "stdafx.h"
    #include "ApartmentsForRent1.h"
    #include "ApartmentsForRent1Dlg.h"
    #include "ApartmentDlg.h"
    #include "afxdialogex.h"
    
    #ifdef _DEBUG
    #define new DEBUG_NEW
    #endif
    
    ... No Change
    
    void CApartmentsForRent1Dlg::OnBnClickedAddfirst()
    {
        // TODO: Add your control notification handler code here
        CApartmentDlg dlg;
    
        if(	dlg.DoModal() == IDOK )
        {
    	CApartment apt(dlg.m_UnitNumber, dlg.m_UnitType,
    	               dlg.m_Bedrooms, dlg.m_Bathrooms,
    		       dlg.m_Condition, dlg.m_MonthlyRent);
    	CurrentPosition = apartments.AddHead(apt);
    
    	OnBnClickedFirst();
        }
    }

22. Return to the dialog box and double-click the Add Last button
23. Implement its event as follows:

    void CApartmentsForRent1Dlg::OnBnClickedAddlast()
    {
        // TODO: Add your control notification handler code here
        CApartmentDlg dlg;
    
        if(	dlg.DoModal() == IDOK )
        {
    	CApartment apt(dlg.m_UnitNumber, dlg.m_UnitType,
    	               dlg.m_Bedrooms, dlg.m_Bathrooms,
    		       dlg.m_Condition, dlg.m_MonthlyRent);
    	CurrentPosition = apartments.AddTail(apt);
    
    	OnBnClickedFirst();
        }
    }

24. Return to the dialog box
25. To execute, press F5
26. Click the following records using either the Add First or the Add Last button:
     

    Unit #	Unit Type	Bedrooms	Bathroms	Condition	Monthly Rent
    2A	Apartment	1	1	Excellent	885
    4D	Efficiency	0	1	Good Shape	675
    1B	Apartment	3	1	Needs Paint	1050
    1E	Duplex	3	2	Excellent	1155
    3C	Apartment	2	1	Needs Carpet	955
    2B	Duplex	4	2	Excellent	1295

27. Close the dialog box and return to your programming environment