Table of Contents

• List Representation
• Creating Nodes
• Adding to a List
• Searching a List
• Trailing Pointers
• Data Abstraction

• List Representation

  Use this Node structure as the basis of your program:

     struct Node 
     {
        char * word ;
        int count ;
        Node * next ;
     } ;
  

  A linked list is a bunch of these Nodes connected together using their next fields. An empty list, that is, a list with zero elements on it, can be represented most simply by having no nodes, and a pointer to an empty list, of value NULL:

     Node * theList ; // (*theList) is of type Node.
     theList = NULL ; // theList is an empty list.
  

  The drawback to this method is that theList changes value as the list is updated. You cannot hand the value of theList to someone, saying - hey, here's my list - because it might change later. It is better that the value of theList be immutable: once set, always set. Then references distributed to the list will be always valid.

  Therefore, represent an empty list by a single node, the dummy node, which has no content:

     Node * theList ;
     theList = new Node ;
     theList->count = 0 ;
     theList->word = NULL ;
     theList->next = NULL ;
  

  This Node will always be the first element on the list.

• Creating Nodes

  You will need to create the Node and the string which the the Node's word field points to. Here's an example:

     char * aWord ;
     Node * newNode ;
  
     aWord = new char[strlen("Hi")+1] ;
     strcpy( aWord, "Hi") ;
     
     newNode = new Node ;
     newNode->word = aWord ;
     newNode->count = 1 ;
     newNode->next = NULL ; // initialize all unused pointers to NULL!
  

• Adding to List

  A new Node can be added to the list at the list's head, just after the dummy node:

     // suppose newNode is of type Node *, and the Node
     // (*newNode) has been created using new.
  
     newNode->next = theList->next ; // items 1, 2, ... are now item 2, 3, ...
     theList->next = newNode ; // and newNode is item 1.
  

• Searching a List

  All the Nodes in the list theList can be looked at by repeatedly following the contents of the next field:

     Node * p ;
     for ( p = theList->next; p!=NULL; p = p->next ) 
     {
        // check p, use break if p is the one you want.
     }
     // when you get here, either:
     // p==NULL: you didn't find what you were looking for;
     // p!=NULL: p is what you were looking for.
  

  Note that p = theList is not checked, because it is the dummy node.

• Trailing Pointers

  To delete a Node from a list, you must have access to the Node previous to the Node to be deleted. It is that Node's next field which is updated. The general rule in cases where deletion is desired is to indicate any Node by a reference to its previous Node. The search routine is modified:

     Node * p ;
     for ( p = theList; p->next!=NULL; p = p->next )
     {
        // check (p->next), use break if(p->next) is the one you want.
     }
     // when you get here, either:
     // (p->next)==NULL: you didn't find what you were looking for;
     // (p->next)!=NULL: (p->next) is what you were looking for.
  

  p is called a trailing pointer because it is always trailing one behind where it actually references.

• Data Abstraction

  It is best to write functions getCount and incrementCount to manipulate the count field of a Node, rather than manipulating this field directly in various places in your code:

     int getCount( Node * p ) 
     {
     // given a pointer to a node, return the count field value
     }
  
     void incrementCount( Node * p )
     {
     // given a pointer to a node, increment the count field by one
     }
  

  This way, when you modify your working simple program to support move to the front only these functions will need to be updated to abid by the new Trailing Pointer convention.

  This is an example of Data Abstraction. The details of a Node structure are hiden behind calls to functions which accomplish the desired manipulations on the Node structure.