Linked Lists

MemberAccess (Review)

A Linked List Class

1. Member Access

Types of Access Priviledge

Type of Member	Accessible in Class Definition	Accessible By Objects
private	yes	no
protected	yes	no
public	yes	yes

Member Access Under Inheritance

Inheritance Access Specifier	Type of Member in Base Class	Access Level in First Derived Class	Accessible by First Derived Class Definition	Accessible by First Derived Class Objects
private	private protected public	- private private	no yes yes	no no no
protected	private protected public	- protected protected	no yes yes	no no no
public	private protected public	- protected public	no yes yes	no no yes

Key Points

Private members are only accessible within the class that they are declared. They are not accessible by derived class definitions.
Protected members are not accessible by objects. They are always accessible by a first level derived class.
The inheritance access specifier places an upper limit on the access level of inherited members in the derived class.

2. A Linked List Class

A linked list can be implemented in several ways. Here we develop a class List that contains a pointer to the start of the list (usually called the head of the list). We also make a base class called ListElement that every object that we enter into the list inherits. Every ListElement object has a pointer to the next ListElement object in the list. Suppose we have 3 objects A,B and C already stored in the list. The variable mpHead in the List object points to the address of the last object stored in the list, ie object C. We now add object D. To do this we set the variable mpNext in D to point to object C (we have that address stored in mpHead) and reset mpHead to point to the address of object D. Look at the code below to verify this.

Class Declaration

list.h

#ifndef _LIST_H_
#define _LIST_H_

#include <iostream.h>
#ifndef TRUE
#define TRUE 1
#endif // TRUE
#ifndef FALSE
#define FALSE 0
#endif // FALSE

// Generic list element. ListElement is an abstract class which will be
// subclassed by users of the List class in order to create different types
// of list elements.
class ListElement {
private:
ListElement *mpNext; // Pointer to next element in the list.

public:
ListElement() {mpNext = NULL;}
~ListElement() {}

// A pure virtual method which returns some measure of the element's
// importance for purposes of ordering the list. The implementation
// will be provided by individual subclasses. The list will be ordered
// from most significant (at the head) to least significant.
virtual float ElementValue() = 0;

// A pure virtual method which prints out the contents of the list element.
// Implementation will be provided by individual subclasses.
virtual void print() = 0;

// Grant special access priviledge to class list.
friend class List;

// An operator<< which prints out a list.
friend ostream& operator<<(ostream &os, const List& list);
};

// A linked list class.
class List {
private:
ListElement *mpHead; // Pointer to the first element in the list.

public:
// Create an empty list.
List();

// Destroy the list, including all of its elements.
~List();

// Add an element to the list. Returns TRUE if successful.
int AddElement(ListElement *pElement);

// Remove an element from the list. Returns TRUE if successful.
int RemoveElement(ListElement *pElement);

// Return a pointer to the largest element. Does not remove it from the
// list.
ListElement *GetLargest();

// Return a pointer to the smallest element. Does not remove it from the
// list.
ListElement *GetSmallest();

// An operator<< which prints out the entire list.
friend ostream& operator<<(ostream &os, const List& list);
};

#endif // _LIST_H_

Class Definition

list.C

#include "list.h"

// Create an empty list.
List::List() {
mpHead = NULL;
}

// Destroy the list, including all of its elements.
List::~List() {
ListElement *pCurrent, *pNext;

for (pCurrent = mpHead; pCurrent != NULL; pCurrent = pNext) {
pNext = pCurrent->mpNext;
delete pCurrent;
}
}

// Add an element to the list. Returns TRUE if successful.
int List::AddElement(ListElement *pElement) {
ListElement *pCurrent, *pPrevious;
float fValue = pElement->ElementValue();

pPrevious = mpHead;
for (pCurrent = mpHead; pCurrent != NULL; pCurrent = pCurrent->mpNext) {
if (fValue > pCurrent->ElementValue()) {
// Insert the new element before the current element.
pElement->mpNext = pCurrent;
if (pCurrent == mpHead)
mpHead = pElement;
else
pPrevious->mpNext = pElement;
return TRUE;
}
pPrevious = pCurrent;
}

// We have reached the end of the list.
if (mpHead == NULL)
mpHead = pElement;
else
pPrevious->mpNext = pElement;
pElement->mpNext = NULL;

return TRUE;
}

// Remove an element from the list. Returns TRUE if successful.
int List::RemoveElement(ListElement *pElement) {
ListElement *pCurrent, *pPrevious;

pPrevious = mpHead;
for (pCurrent = mpHead; pCurrent != NULL; pCurrent = pCurrent->mpNext) {
if (pCurrent == pElement) {
if (pCurrent == mpHead)
mpHead = pCurrent->mpNext;
else
pPrevious->mpNext = pCurrent->mpNext;
delete pCurrent;
return TRUE;
}
pPrevious = pCurrent;
}

// The given element was not found in the list.
return FALSE;
}

// Return a pointer to the largest element. Does not remove it from the list.
ListElement *List::GetLargest() {
return mpHead;
}

// Return a pointer to the smallest element. Does not remove it from the list.
ListElement *List::GetSmallest() {
ListElement *pCurrent, *pPrevious;

pPrevious = mpHead;
for (pCurrent = mpHead; pCurrent != NULL; pCurrent = pCurrent->mpNext) {
pPrevious = pCurrent;
}

return pPrevious;
}

// An operator<< which prints out the entire list.
ostream& operator<<(ostream &os, const List& list) {
ListElement *pCurrent;

for (pCurrent = list.mpHead; pCurrent != NULL;
pCurrent = pCurrent->mpNext) {
// Print out the contents of the current list element. Since the
// print method is declared to be virtual in the ListElement class,
// the actual print method to be used will be determined at run time.
pCurrent->print();
}
}

Using the Linked List Class

shapes.h

// Some shapes that we may wish to store in a linked list.
// We will order the shape objects according to their areas.

#ifndef _SHAPE_H_
#define _SHAPE_H_

#define PI 3.14159

#include "list.h"

class Triangle : public ListElement {
private:
float mfBase, mfHeight;

public:
// Unless we provide an explicit base class initializer, the base
// class will be initialized using its default constructor.
Triangle() {mfBase = mfHeight = 0.0;}
Triangle(float fBase, float fHeight) {mfBase = fBase; mfHeight = fHeight;}
~Triangle() {}
float ElementValue() {return (mfBase * mfHeight / 2);}
void print() {cout << "Triangle: area = " << ElementValue() << endl;}
};

class Rectangle : public ListElement {
private:
float mfBase, mfHeight;

public:
// Unless we provide an explicit base class initializer, the base
// class will be initialized using its default constructor.
Rectangle() {mfBase = mfHeight = 0.0;}
Rectangle(float fBase, float fHeight) {mfBase = fBase; mfHeight = fHeight;}
~Rectangle() {}
float ElementValue() {return (mfBase * mfHeight);}
void print() {cout << "Rectangle: area = " << ElementValue() << endl;}
};

class Circle : public ListElement {
private:
float mfRadius;

public:
// Unless we provide an explicit base class initializer, the base
// class will be initialized using its default constructor.
Circle() {mfRadius = 0.0;}
Circle(float fRadius) {mfRadius = fRadius;}
~Circle() {}
float ElementValue() {return (PI * mfRadius * mfRadius);}
void print() {cout << "Circle: area = " << ElementValue() << endl;}
};
#endif // _SHAPE_H_

list_test.C

#include "shapes.h"

main() {
List list;
ListElement *p;

p = new Triangle(4, 3);
list.AddElement(p);
p = new Rectangle(2, 1);
list.AddElement(p);
p = new Circle(2);
list.AddElement(p);
p = new Triangle(3, 2);
list.AddElement(p);
p = new Circle(1);
list.AddElement(p);

cout << list << endl;

list.RemoveElement(list.GetLargest());

cout << list << endl;

list.RemoveElement(list.GetSmallest());

cout << list << endl;
}