In this chapter, we look at the use of pointers to build "linked" data types. A linked data type allows separate objects to be linked together into more complex information structures. There are many examples of such linked structures including lists, queues, trees and graphs. It is not the goal of this course to explore these in detail - this is left to a later course on Data Structures. Instead, we focus on the relatively simple example if a list in order to demonstrate the overall approach.
This chapter introduces the following key concepts:
Lists are a familiar feature of our lives and examples include shopping lists and address books containing lists of names. For our purposes we shall consider a list to have the following basic properties:
The properties of insertion and deletion are shown below and make lists quite different from arrays where these operations are not possible.
Carrots --> Peas --> Cabbage --> Parsnips
{ insert "Sweetcorn" into position 3 }
Carrots --> Peas --> Sweetcorn --> Cabbage --> Parsnips
{ delete "Cabbage" from position 4 }
Carrots --> Peas --> Sweetcorn --> Parsnips
These basic properties led me to the following design of a list Abstract Data Type (based on our five categories of interface function).
Constructors: build an empty list (no elements)
build a list from another list (copy constructor)
Access: insert a new element into position n
delete the element at position n
retrieve the value at position n (overload [])
return the length of the list (number of elements)
Combination: join two lists together to get a new one (operator +)
Tests: is the list empty (operator !)
are two lists equal (operator ==)
are two lists not equal ( != )
I/O: print a list in the form [a] -> [b] -> [c] -> oo
read a list from the keyboard
We will limit our first example to be a list of single characters. However, it should be easy to see how to extend this to other types, including your own classes. The design above yields the following class definition for a new List class. Notice that in this definition I have left out the data members - these will be introduced in the implementation section below.
// class to represent a linked list of characters
class List {
private:
// to be completed
public:
// constructors
List();
List(List& l);
// combination
List operator+(List& l);
// access
int insertN(char c, int n);
int deleteN(int n);
int retrieveN(char &c, int n);
// tests
int operator!();
int operator==(List& l);
int operator!=(List& l);
int length();
// I/O operators
friend ostream& operator<<(ostream& os, List& l);
friend istream& operator>>(istream& is, List& l);
};
Notice that the retrieveN method places the retrieved value into the argument char &c - a deliberate side effect. As a result, this argument must be passed by reference. List arguments are also passed by reference, but in this case for reasons of increased efficiency.
The implementation of the List class uses the fact the pointers can be used to link objects together. First, consider the following definition of a simple Element class.
class Element {
private:
// value stored in this element
char val;
// pointer to next element in list
Element *next;
public:
Element(char);
};
An element object may contain a single character (val) and also
a pointer (next) which can be set to point at some other element.
The following constructor function is provided to initialise an Element object.
// construct a single list element
Element::Element(char c) {
val = c;
next = 0;
}
Now, assuming that our program has permission to manipulate the data-members of the class Element, we can build chains of elements in the following way.
Element a('a'), b('b');
a.next = &b;
cout << a.val << b.val << a.next->val;
Or better ...
Element *first;
first = new Element('a');
first->next = new Element('b');
first->next->next = new Element('c');
first->next->next->next = new Element('d');
first->next->next->next->next = new Element('e');
first->next->next->next->next->next = new Element('f');
We have now managed to build up a chain of linked objects - in other words a simple list. The following code prints out the values in this list, in sequence.
Element *p = first;
while ( p != 0 ) {
cout << p->val;
p = p->next;
}
These ideas form the basis of our list implementation. However, instead of adding each element to the chain explicitly we need a much more flexible approach. This is given by implementing the methods insertN and deleteN in a general way so that we can access any part of an arbitrary long list.
Overall, our List implementation will require two classes - the basic Element class described above and the more general List class. Thus, once again we see an example of a using relationship between different classes.
The following is the completed header file which defines both classes. Note that we have also added some extra methods to the List class. These include a destructor and an overloaded assignment operator. These are required because we will we be doing our own memory allocation.
A new searchN method has been introduced into the private section of the class. This method returns the address of the nth element in the list (and the 0 pointer if there is no such element). This is generally useful for implementing insertN, retrieveN and deleteN. However, a user of the class should not see such addresses and so searchN is defined as a private method, not a public one. In other words, it can only be used by other methods of the List class.
// specification for an ADT representing a list of chars
// implementation using pointers to link elements together
#include <stream.h>
// status codes returned by public functions
const int OK = 1;
const int OUT_OF_BOUNDS = -1;
// class to represent a single list element
class Element {
private:
char val;
Element *next;
public:
Element(char);
friend class List;
friend ostream& operator<<(ostream& os, List& l);
};
// class to represent a linked list of characters
class List {
private:
Element *first;
int len;
Element *searchN(int n);
public:
// constructors
List();
List(List& l);
// destructor
~List();
// combination
void operator=(List& l);
List operator+(List& l);
// access
int insertN(char c, int n);
int deleteN(int n);
int retrieveN(char &c, int n);
// tests
int operator!();
int operator==(List& l);
int operator!=(List& l);
int length();
// I/O operators
friend ostream& operator<<(ostream& os, List& l);
friend istream& operator>>(istream& is, List& l);
};
Notice that we define two error codes to be returned by public functions. One represents the fact that a requested element is not in the list (e.g. trying to delete the fourth element of a list that is three elements long). The other indicates that the operation completed successfully.
Note also that the class List is declared as a friend to the class Element. This enables ALL methods of List to manipulate the internal data-members of Element objects (e.g. making and breaking links via the next pointers). We also have to declare the overloaded output operator as a friend to both List and Element.
The List class defines two private data members, len which indicates how many elements are in the list at a given time and first which is a pointer to the first element in a chain. Thus the overall approach is to have a List object point to an Elment object which, in turn, is linked to a chain of further Element objects. The following figures show two example lists, one empty (i.e. no elements) and the other containing several elements.
Each of the methods defined for List will need to access and manipulate this structure in some way. We will now look at each of these methods in turn.
The constructor to build an empty list merely sets the pointer first to be null and notes that there are zero elements in the list.
// construct an empty list
List::List() {
first = 0;
len = 0;
}
Next, we need to look at searchN. The goal of this private method is to return a pointer to the nth element in the list (where n is its argument). To do this, a while loop starts at the first element and moves down the list, following the next pointers, until either the end of the list is reached (the 0 pointer) or it has seen n elements. Of course, it needs to keep a record of how many elements have already been seen. This is achieved through the local variable int seen. Finally, it returns a pointer to the element at which it stopped (this will be the 0 address if it ran over the end of the list).
// general function to return a pointer to the nth element
// return null pointer for error
Element* List::searchN(int n) {
Element *pos = first;
int seen = 1;
// check bounds
if((n < 1) || (n > len))
return 0;
// move down list one element at a time
while( (pos != 0) && (seen != n)) {
pos = pos->next;
seen++;
}
// return pointer to element
return pos;
}
Next we look at the insert function. There are two distinct cases to be considered - inserting at the beginning of the list and inserting somewhere in the middle or at the end of the list.
First, we check whether the subscript is in bounds. Then we construct a new Element with the correct value. If we are inserting at the first position, we link this new element to the one that first is currently pointing at and then link first to our new element. This is shown below.
If we are inserting in the middle of the list we get a pointer to the preceding element and then follow these steps:
In both cases we increase the length of the list.
// insert character c in position n
int List::insertN(char c, int n) {
// check bounds (note we can insert in position n+1)
if ((n > len+1) || (n < 1))
return OUT_OF_BOUNDS;
// build a new element to be added to the list
Element *new_elem = new Element(c);
// first element is a special case
if(n == 1) {
new_elem->next = first;
first = new_elem;
}
else {
// otherwise find element n-1
Element *prev = searchN(n-1);
// link new element to the following elements
new_elem->next = prev->next;
// ling preceding element to the new element
prev->next = new_elem;
}
// increase the length of the list
len++;
return OK;
}
Deletion also starts with bounds checking. Beyond this, the procedure is the reverse to insertion. Notice that as well as making and breaking pointers, we also free the memory associated with the element being deleted.
// delete the element at position N in the list
int List::deleteN(int n) {
// pointer to the preceding element and the element being deleted
Element *prev, *pos;
// check bounds
if ((n > len) || (n < 1))
return OUT_OF_BOUNDS;
// first element is a special case
if (n == 1) {
// remember the old first element
pos = first;
// reset the start of the list
first = first->next;
}
else {
// find previous element
prev = searchN(n-1);
// remember the element to be deleted
pos = prev->next;
// chop element out of list
prev->next = pos->next;
}
// delete the element and free its memory
delete pos;
// decrease the length of the list
len--;
return OK;
}
Retrieving a value involves getting a pointer to the element in question using searchN and then extracting its value.
// retrieve the value of element N
int List::retrieveN(char &c, int n) {
// check bounds
if((n < 1) || (n > len))
return OUT_OF_BOUNDS;
// get a pointer to the element
Element *pos = searchN(n);
// assign its value and return
c = pos->val;
return OK;
}
The destructor needs to free all of the memory that has been allocated for the list. This means going down the list and element at a time freeing each element. Note that it is important to get the address of the next element in the list BEFORE deleting the current one.
// destructor - free all memory
List::~List() {
Element *p = first; // current element
Element *temp; // temporary
// examine elements one at a time
while(p != 0) {
// remember old element
temp = p;
// find next element
p = p->next;
// delete old element
delete temp;
}
}
As with the String class in the preceding chapter, we need to overload the assignment operator (otherwise memberwise copying would result in different lists sharing the same memory). First, we go down the list deleting each of the old elements. Then we reset the list to be empty. Finally we go down the list to be copied, an element at a time, inserting each value. Notice how easy this is once we have defined the insertN method.
// overloaded assignment operator
void List::operator=(List& l) {
Element *p = first, *temp;
// first destroy the current contents of this list
while( p != 0) {
temp = p;
p = p->next;
delete temp;
}
// now reset the list to be empty
len = 0;
first = 0;
// now insert the elements of the given list one at a time
for(p = l.first; p != 0; p = p->next)
insertN(p->val, len+1);
}
The copy constructor is very like the assignment operator except that we don't need to delete any existing elements first.
// copy constructor
List::List(List& l) {
Element *p;
// initialise the list to be empty
len = 0;
first = 0;
// now insert the elements of the given list one at a time
for(p = l.first; p != 0; p = p->next)
insertN(p->val, len+1);
}
Concatenation involves the following:
// concatenate two lists and return result
List List::operator+(List& l) {
// initialise results variable
List res;
// insert the elements of the current list into results
Element *pos = first;
while(pos != 0) {
res.insertN(pos->val, res.len + 1);
pos = pos->next;
}
// insert all the elements of the given list 'l'
pos = l.first;
while(pos != 0) {
res.insertN(pos->val, res.len + 1);
pos = pos->next;
}
// return results (calls overloaded assignment)
return res;
}
The empty list test is trivial.
// tests for an empty list
int List::operator!() {
return !len;
}
In order to test equality we first compare the lengths of the lists and, if they are equal, then compare each element in turn.
// test equality of lists
int List::operator==(List& l) {
// cursors to move down each list
Element *pos1, *pos2;
// are the lists the same length?
if (len != l.len)
return 0;
// move down both lists an element at a time, comparing values
pos1 = first;
pos2 = l.first;
while(pos1 != 0) {
// compare elements
if (pos1->val != pos2->val)
return 0;
// increment position in both lists
pos1 = pos1->next;
pos2 = pos2->next;
}
// if we get here they must be the same
return 1;
}
// test inequality of lists
int List::operator!=(List& l) {
// cursors to move down each list
Element *pos1, *pos2;
// are the lists the same length?
if (len != l.len)
return 1;
// move down both lists an element at a time, comparing values
pos1 = first;
pos2 = l.first;
while(pos1 != 0) {
// compare elements
if (pos1->val != pos2->val)
return 1;
// increment position in both lists
pos1 = pos1->next;
pos2 = pos2->next;
}
// if we get here they must be the same
return 0;
}
The following implements the remaining List methods.
// return the length of the list
int List::length() {
return len;
}
// print a list on the standard output
ostream& operator<<(ostream& os, List& l) {
// go down the list one element at a time
Element *pos = l.first;
while (pos != 0) {
cout << " [" << pos->val << "] ->";
pos = pos->next;
}
cout << "oo\\n";;
return os;
}
// read in a list from the keyboard and append to current list.
// stop at end of line
istream& operator>>(istream& is, List& l) {
char data;
// read and insert chars until end of line or no more space
while(1) {
// read a single character into data
cin.get(data);
// check for end of line
if(data == '\\n')
return is;
// append to the end of the list
l.insertN(data, l.len+1);
}
}
To finish this chapter, the following user program demonstrates the syntax for using the List class.
// program to test the list implementation
#include "List.h"
main() {
List l, m ,n;
char c, data;
int pos;
cout << "List testing program\\n";
// input initial list
cout << "Please enter a list\\n";
cin >> l;
cout << l;
// test not operator
if(!l)
cout << "l is empty\\n";
else
cout << "l is not empty\\n";
// test length operator
cout << "length of l is " << l.length() << "\\n";
// test insert
c = 'y';
while(c == 'y') {
cout << "enter value to be inserted\\n";
cin >> data;
cout << "enter position\\n";
cin >> pos;
if(l.insertN(data, pos) < 0)
cout << "error\\n";
else
cout << l << "\\n";
cout << "another? (y/n): ";
cin >> c;
}
// test delete
c = 'y';
while(c == 'y') {
cout << "enter position to be deleted\\n";
cin >> pos;
if(l.deleteN(pos) < 0)
cout << "error\\n";
else
cout << l << "\\n";
cout << "another? (y/n): ";;
cin >> c;
}
// flush line
cin.get(c);
// read a second list
cout << "Please enter second list\\n";
cin >> m;
cout << m;
// test comparison operators
if(l == m)
cout << "lists are equal\\n";
else
cout << "lists are not equal\\n";
if(l != m)
cout << "lists are not equal\\n";
else
cout << "lists are equal\\n";
// test concatenate operator
n = l + m;
cout << "first + second is\\n" << n << "\\n";
}
Notes converted from troff to HTML by an Eric Foxley shell script, email errors to me!