© by Charles Lin. All rights reserved. You must receive written permission from Charles Lin to reproduce this webpage in any form.

Background

Definition A list is a mathematical entity, which contains 0 or more values, in some order. We'll mainly consider sorted, non-repeating lists.

It's important to think of the list as something abstract. Too often, beginning programmers get caught up thinking of the implementation. Instead, pretend you are a class designer, someone who writes classes to be used by programmers.

Other programmers want to work with easy-to-understand classes, and you should provide them with this abstraction. To understand a list (or other abstract entities), you need to consider what kind of operations you should perform. Here are some reasonably operations.

• Add an element.
• Remove an element
• Determine if an element is in the list.
• Copy the list
• Print the list

Key is the key

When you have a complicated object---by complicated, I mean it contains many data fields, you often sort based on a small part of the object. That part is called the key.

The key can be as simple as an integer, to something more complex. For example, you may wish to sort based on a person's height, weight, and eye color.

In a sorted list with no repeats, no key is duplicated. Thus, even though two objects may share the same key (for example, the same student ID) but differ on many other fields, only one of those objects can appear in a sorted list.

Implementation

The second class is simply a pointer to the first node of a singly linked list. We'll call this class SLL to stand for singly linked list.

Here's how you would write a Node class.

class Node {
   int key;
   Node *next;
public:
   Node( int numIn = 0 );
   void setNext( Node *nextIn );
   Node *getNext();
   const Node *getNext();
   int   getKey();
};

Admittedly, this is rather inconvenient. It's hard to create classes that have a separate key and data. In fact, in the STL, all lists are considered unsorted. That way, it's perfectly valid to change the "key", since the list doesn't have to be sorted by the key. Thus, one can have a list, sort it, modify one of the keys, and resort it again.

You may also wonder why this class is a class. Couldn't you use a struct instead? Yes, you could, and many books do this. In fact, you may have learned to use a Node which was implement as a struct. That way, key and next were public.

However, there are several reasons to make it into a class. First, it allows you to have a constructor and destructor. The constructor is useful, because you can initialize values inside the Node. It's easy to forget to do this when you don't use a constructor.

Secondly, if the Node contains a pointer to a dynamically allocated object (created when the Node was constructed), then the destructor has a chance to deallocate the object. Again, it's easy to forget to do this.

Of course, if you're used to having Node contain public members, then it seems awkward to use set and get methods. This is one reason, to use them. Programming, indeed all of learning, is dealing with new situations, and making adjustments.

As analogy, think of driving. In the U.S., everyone drives on the right side of the road. The steering wheel is on the left side. However, in England, people drive on the left side, and the steering wheel is on the right side. If you want to get good at driving, you would learn to drive both kinds of cars.

Learning to program is very much like this. You will learn one way of doing things. Then, someone tells you to do it a different way. You get annoyed, and claim that it's stupid. However, the more you are able to adapt to whatever you're being told to do, the easier it will be for you to get on with the task at hand, and not complain unnecessarily.

Now that I've digressed a while, here's the Node class again. Here's how you would write a Node class.

class Node {
   int key;
   Node *next;
public:
   Node( int numIn = 0 );
   void setNext( Node *nextIn );
   Node *getNext();
   const Node *getNext();
   int   getKey();
};

class SLL {
   Node *first;
   int  size;
public:
   SLL();
   bool add( int num );
   bool remove( int num );
   ConstIterator constIterator() const;
   void print() const;
private:
   bool locate( Node *&curr, Node *&prev, int num );
   void beginAddCase( Node * );
   void middleEndAddCase( Node *, Node *, Node * );
   void beginRemoveCase( Node *, Node * );
   void middleEndRemoveCase( Node *, Node * );
};

Node::Node( int numIn ) : key( numIn )
{
}

void Node::setNext( Node *nextIn )
{
   next = nextIn;
}

Node *Node::getNext()
{
   return next;
}

const Node *Node::getNext() const
{
   return next;
}

int Node::getKey() const
{
   return key;
}

// Constructor
SLL::SLL() : first( NULL ), size( 0 )
{
}

// constIterator
ConstIterator SLL::constIterator() const
{
  return ConstIterator( first );
}

// locate  HELPER
bool SLL::locate( Node *&curr, Node *&prev, int search )
{
  curr = first;
  prev = NULL;
  while ( curr != NULL && search > curr->getKey() )
    {
      prev = curr;
      curr = curr->getNext();
    }

  return ( curr != NULL && curr->getKey() == search );
}

// add
bool SLL::add( int num )
{
   bool success = false;
   Node *curr, *prev;
   if ( ! locate( curr, prev, num ) )
      {
         Node *insertPtr = new Node( num );
         if ( curr == first )  // first
            beginAddCase( insertPtr );
         else // middle or end
            middleEndAddCase( prev, curr, insertPtr );

         size++;
         success = true;
      }
   return success;
}

// beginAddCase   HELPER
void SLL::beginAddCase( Node *insertPtr )
{
   insertPtr->setNext( first );
   first = insertPtr;
}

// middleEndAddCase   HELPER
void SLL::middleEndAddCase( Node *prev, Node *curr, Node *insertPtr )
{
   prev->setNext( insertPtr );
   insertPtr->setNext( curr );
}

// remove
bool SLL::remove( int num )
{
   bool success = false;
   Node *curr, *prev;
   if ( locate( curr, prev, num ) )
      {
         if ( curr == first )  // first
            beginRemoveCase( prev, curr );
         else // middle or end
            middleEndRemoveCase( prev, curr );

         size--;
         success = true;
      }
   return success;
}

// beginRemoveCase   HELPER
void SLL::beginRemoveCase( Node *prev, Node *curr )
{
   Node *toDeletePtr = curr;

   curr = curr->getNext();
   first = curr;
   delete toDeletePtr;
}

// middleEndRemoveCase   HELPER
void SLL::middleEndRemoveCase( Node *prev, Node *curr )
{
   Node *afterPtr = curr->getNext(), *toDeletePtr = curr;

   prev->setNext( afterPtr );
   delete toDeletePtr;
}

// print
void SLL::print() const
{
   ConstIterator iter = constIterator();

   for ( iter.goFirst(); iter.inList(); iter.goNext() )
     {
       cout << iter.getCurrent() << " ";
     }
}

In particular, pay close attention to the add and remove methods. You may find that it's shorter than the version you would use. It's always good to study other people's code, and compare/contrast with your own.

Locate, then Update Pointers

When writing a program, you are often taught to break down problems into subtasks, then break the subtasks into further subtasks. Finally, write functions for the simplest subtasks.

It may be difficult to notice, but add() and remove() both consist of placing a "curr" pointers in the correct location, then inserting or removing the node. locate does the first part of the task: placing curr in a location of a linked list where it's convenient.

This turns out to be rather useful when you do a locate

Web Accessibility