Pointers and Linked Lists
A pointer may point at an object as well as a value, and a class may have a pointer to another object as a member variable, which in turn points at another object and so on. In this way, a linked list can be constructed. The list must end eventually, so the last pointer points at null. A pointer to the next cell in the list is called a link.
Stacks and Linked Lists
A stack is very valuable in a number of applications and it can be implemented with a linked list. We can add a value on top of the stack, we can inspect or remove the topmost value, and we can check whether the stack is empty. However, we cannot do anything to the values that are not on top. The method that adds a new value on top of the stack is called push and the method removing it is called pop. Let us say that we push our stack three times with the values 1, 2, and 3. Then we can only access the topmost value, 3, and not the two below, 1 or 2.
An additional point of this example is that the Value method is overloaded. The first version returns a reference to the value; the second version is constant and returns the value itself. This implies that the first version can be called to modify the value of the cell and the second version can be called to inspect the value of a constant cell object.
Cell cell1(1, NULL); cell1.Value() = 2; const cell2(2, NULL); int iValue = cell2.Value();
Another way to archive the same functionality would be to add a get/set pair.
const int GetValue() const {return m_iValue;}
void SetValue(int iValue) {m_iValue = iValue;}
/// ...
Cell cell1(1, NULL);
cell1.SetValue(2);
const cell2(2, NULL);
int iValue = cell2.GetValue();
In order to make the typedef definition below work, we have to declare the class on the preceding line. It is possible to define a pointer to an unknown type as all pointers occupy the same amount of memory regardless of what they point at. However, it is not allowed to define arrays of unknown types or classes with fields of unknown types.
class Cell;
typedef Cell* Link;
class Cell
{
public:
Cell(int iValue, Cell* pNextCell);
int& Value() {return m_iValue;}
const int Value() const {return m_iValue;}
Link& NextLink() {return m_pNextLink;}
const Link NextLink() const {return m_pNextLink;}
private:
int m_iValue;
Link m_pNextLink;
};
#include "Cell.h"
Cell::Cell(int iValue, Link pNextLink)
:m_iValue(iValue),
m_pNextLink(pNextLink)
{
// Empty.
}
#include <cstdlib>
#include "Cell.h"
void main()
{
Link pCell3 = new Cell(3, NULL);
Link pCell2 = new Cell(2, pCell3);
Link pCell1 = new Cell(1, pCell2);
}
The following structure is created by main above.
There is one more thing to think about. What happens if we run out of dynamic memory or try to access the topmost value of an empty stack? We can deal with the problem in some different ways, everything from ignoring it to aborting the execution. In this case, I have limited the handling of memory shortage to the use of the macro assert, as described in the previous chapter.
class Stack
{
public:
Stack();
~Stack();
void Push(int iValue);
void Pop();
int Top() const;
bool IsEmpty() const;
private:
Cell* m_pFirstCell;
};
#include <cstdlib>
#include <cassert>
#include "..\\LinkedList\\Cell.h"
#include "Stack.h"
Stack::Stack()
:m_pFirstCell(NULL)
{
// Empty.
}
Stack::~Stack()
{
Cell* pCurrCell = m_pFirstCell;
while (pCurrCell != NULL)
{
Cell* pRemoveCell = pCurrCell;
pCurrCell = pCurrCell->NextLink();
delete pRemoveCell;
}
}
void Stack::Push(int iValue)
{
Cell* pNewCell = new Cell(iValue, m_pFirstCell);
assert(pNewCell != NULL);
m_pFirstCell = pNewCell;
}
void Stack::Pop()
{
assert(m_pFirstCell != NULL);
Cell* pTempCell = m_pFirstCell;
m_pFirstCell = m_pFirstCell->NextLink();
delete pTempCell;
}
int Stack::Top() const
{
assert(m_pFirstCell != NULL);
return m_pFirstCell->Value();
}
bool Stack::IsEmpty() const
{
return (m_pFirstCell == NULL);
}
#include "..\\LinkedList\\Cell.h"
#include "Stack.h"
void main()
{
Stack stack;
stack.Push(1);
stack.Push(2);
stack.Push(3);
}
The stack in main above gives rise to the following structure. However, when the stack goes out of scope (at the end of main), the destructor deallocates the allocated memory. All memory allocated with new must (or at least should) be deallocated with delete.
