In particular, we will focus on sorted linked lists. Let's begin with some terminology. A linked list consists of nodes. Each node contains data, which is the information you want to store, and a "link" called next which points to the next node in a list. It's very similar to a bunch of trains hooked up together.
With classes, you can hide this pointer as a data member. The question is: how many classes should you use to represent a singly linked list, and what should each class do?
Immediately, one thinks of making a "node" into a class. After all, that's an object. Yet, we have a collection of nodes, not just one, and it seems unusual to make one node in charge of all the other nodes (although, not too unreasonable).
So, often, there's a second class. This class manages all the nodes. In particular, it maintains a pointer to the first element of the linked list. It could also maintain other data members, such as a pointer to the last element or the total number of elements, though that's not strictly necessary.
This class is often thought of as the linked list class.
Lately, implementations of linked lists often include a third class: iterators. As you should recall, an iterator is basically a pointer stored inside an object. The purpose of an iterator is to allow you to step through the elements of a list, and not necessarily a linked list. An iterator can be used in list that's implemented as an array.
We'll look at a partial implementation of all three classes, where nodes and iterators are nested classes.
If they are separate classes, why have them nested? Mostly, it's for namespace reasons. The inner class is usually used extensively by the outer class. Think of it as an extension of helper functions. You write public methods, but may implement them with the help or private helper methods. It may make sense to have helper classes, and nested classes can be considered as helpers.
If the inner class is declared in the private section, then only methods of the outer class can declare an instance of the inner class. Methods outside the class (including standalone functions like main()) can't declare the nested class.
If the inner class is located in the public section of the outer
class, then instances of the inner class can be declared anywhere.
However, you must refer to it by its full type name. For example,
if Iterator is nested inside of List, then declaring
an iterator looks like:
List::Iterator iter
The type is the outer classes's type name, followed by double
colons, followed by the name of the inner class. This is to prevent
it from being confused with a class called simply Iterator or
another nested class with Iterator,
e.g. LinkedList::Iterator.
Within the methods of the outer class, you can often refer to the inner class by the short type name, e.g. Iterator instead of List::Iterator, although either one is acceptable.
class List {
private:
class Node { // private nested class
Student data;
Node *next;
public:
Node( const Student &data );
Student getStudent() const;
Node *getNext();
const Node *getNext() const;
void setNext( Node *nextIn );
bool update( const Student &data );
};
// data members
Node *first; // short typename can be used inside class
public:
// nested class
class Iterator { // private nested class
Node *curr;
public:
Iterator( Node *currIn );
Student & operator*(); // overloaded dereference
const Student &operator*() const; // const overloaded dereference
Student * operator->(); // overloaded ->
const Student *operator->() const; // const overloaded ->
Iterator &operator++(); // prefix
Iterator operator++( int ); // postfix
bool operator==( const Iterator &other );
bool operator!=( const Iterator &other );
};
// public methods
bool add( const Student &dataIn );
bool remove( const Name &keyIn );
bool contains( const Name &keyIn ) const;
bool update( const Student &dataIn );
int size() const;
void clear(); // remove all elements, set size to 0
Iterator first();
Iterator end();
// private methods
private:
bool locate( const Name &name, Node *& curr, Node *& prev );
// Helper methods for copy cons, op= and dest.
void init();
void copy( const List & list );
void freeMem();
};
Let's take a look at each part.
There's only one odd spot. You see that there are two methods called getNext(). Why two? Whenever you "get" a data member using a pointer or reference (as opposed to "by value"), you allow the person to modify the pointer or reference. In effect, they get access to the inner parts of your object. Generally, this is a bad idea, but sometimes, necessary.
Even though such "get" methods do not modify the data members, they shouldn't be const. The user can modify the list. So, you make it non-const. However, if the object is somehow const, you may still want to access the "next" data member (say, to print). So, the solution is to offer a "const" version of getNext(), which returns a const pointer. This will allow the called of the method to access "next", but not to modify the object that "next" points to.
Thus, the rule of thumb:
If you must return a pointer or reference to a data member, have a const and non-const version, and have one return a const pointer or reference (this method is const), and the other a non-const pointer or reference.Normally, you can't write methods that differ only in the return type. However, getNext() differs in the constness of the method. Thus, in const situations, the "const" method is used, and in all other situations, the non-const method is used.
The other operators should be straight-forward. They move the iterator forward or backward. If the iterator falls off the list, it becomes NULL, and then you can't get back on the list again.
Postfix ++ is a challenge. With prefix ++, it's easy. Move "curr", and return a reference to *this and you should be fine. However, with postfix, you must save a copy of the iterator to "temp", then move "curr" and return the copy. That's why it's returned by value, instead of by reference.
Iterators are primarily used by the users of the class. They could be used internally by the methods of the class, but it's not necessary to do so.
Let's go through what each method does:
Adds a Student object to the list. Returns true if the object was successfully added, i.e., there are no other students by the same name in the list. Returns false, if a student by the same name already exists in the list.
Removes a Student object from the list. Does so by the student's name. Returns true if the object was successfully removed, which means there was a student with the name in the list. Returns false, if student isn't in the list.
We'll discuss why this is done by the student's name, momentarily.
Returns true if student is in the list (by name) or false, if not.
Updates student information, if the student is in the list. Will only update the student that has the same matching name. Return true if student's name is in list, and false otherwise.
Returns the size of the linked list.
Empties the list, deallocating memory, and sets size to 0.
Empties the list, deallocating memory, and sets size to 0.
Returns an iterator to the first element of the list (which could be NULL).
Returns an iterator that points to NULL. You compare your iterator to this iterator. Indicates when the iterator has reached the end of the list.
That part of the data is called the key. The key should uniquely identify the data. Furthermore, if you're going to sort the list by the key, the key must support comparison operations.
In our example, Student is the data, while Name is the key. Two Student's are considered "equal" is their Names are the same. You can think of this as a kind of "shallow equality" since only names are compared. As opposed to "deep equality" where every data member must be the equal (as determined by the == operator).
Why is that? First, in order to sort, you need a "key". Second, you may want unique keys, to prevent duplicates. Yet, some lists should allow duplicate keys (such as a list of grocery items), while other lists should not (a list of students).
Furthermore, you may not always want to sort by the key.
You will discover that STL doesn't have a sorted list. Instead, it has unsorted lists, that support a sort operation. That means the list can be unsorted from time to time.
Nevertheless, sorted lists are commonly taught, and have their place, and that's why we study them.
The purpose of locate() is to set up to two pointers correctly in the linked list. In fact, there are two versions of locate.
In a predecessor locate, you only use a "curr" pointer. This pointer will point to the node being located, if it exists, or to its predecessor, if it doesn't.
For example, if you have a list of int values { 10, 20, 30 } and you are trying to locate 25, then "curr" would point to 20 (since 25 is not in the list, and 20 is 25's predecessor).
If you are trying to locate a number smaller than the smallest number (such as locating 5) or if the list is empty, then curr will point to NULL.
In a successor locate, you use a "curr" and "prev" pointer. "curr" will point to the node being located, if it exists, or to its predecessor, if it doesn't. "prev" will point to curr's successor.
If curr points to the first element of the list, is NULL, then prev is NULL.
For doubly linked lists, it turns out either one will do.
Now suppose the condition after the while loop is blarg, then what must the condition of the while loop be (assuming no break statements)? It should be ! blarg.
blarg, i.e., a condition that's true just after the loop, is called the postcondition of the loop. Sometimes it's easier to think of the postcondition of the loop than the condition of the loop. Fortunately, once you know the postcondition, it's easy to determine the condition. Take the negation of the postcondition!
For locate, the postcondition is:
curr == NULL || curr->getStudent().getName() >= nameIn
In English, it says that curr is NULL (meaning it fell
off the list) or it's not NULL and the current student's name is
greater than or equal to the name passed in. Thus, it found node
with the same name, or the node with the name of the successor.
If that's the postcondition, then we take the negation (using
DeMorgan's Law) to get:
curr != NULL && curr->getStudent().getName() < nameIn
We can write this code easily now.
bool List::locate( const Name &nameIn, Node * & curr, Node * & prev )
{
// precondition: curr == first && prev == NULL
while ( curr != NULL && curr->getStudent().getName() < nameIn )
{
prev = curr; // trail behind curr
curr = curr->getNext(); // advance curr
}
// This condition is true, only if we found the node
return curr == NULL && curr->getStudent().getName() == nameIn;
}
When writing the code, there are four cases to consider.
Why are all but the last extreme? Imagine inserting a million elements into a linked list, and determining how often each of the cases show up. Inserting in the middle ought to be the most common by far, even though, you have to insert into an empty list at least once.
You can write conditions to test for each of these cases, using the results of "prev" and "curr".
It turns out, that if you code all four up, the first two combine into one case, and the last two combine into one case. Code it out, and you will see this.
bool List::add( const Student &stu )
{
Node *curr = first, *prev = NULL; // satifies precond
if ( ! locate( stu.getName(), curr, prev ) )
{ // student not found---add student
Node *newStu = new Node( stu ); // allocate student node
if ( prev == NULL ) // empty or start
{
newStu-<setNext( first );
first = newStu;
}
else // end or middle
{
prev-<setNext( newStu );
newStu-<setNext( curr );
}
return true;
}
// student found
return false;
}
You should be able to figure out how to write the other three
methods.