Notes on Linked Lists I

A linked list is a data structure that is made up of nodes.  Each node contains some data to be stored and a pointer to another node on the list.  The pointer mentioned here is a variable that contains a memory address.  This pointer may or may not be a C++ pointer variable.  The same type of data is stored in every node of a linked list.  The memory for each linked list node is obtained from some pool of free storage.  This memory is allocated only when a node needs to be inserted on the list.  No memory for list nodes is allocated until it is needed.  Linked lists are characterized by the fact that the number of elements that they can contain is limited only by the size of the memory pool.  They are also characterized by the fact that inserting and removing list elements is fairly easy.  We will study the implementation of linked list using C++ struct's and pointer variables.  We present an implementation that is not object oriented.  This implementation differs from that shown in the textbook.

A typical linked list is shown in the following diagram.

Each of the blocks represents a node.  Each node contains an integer value and a pointer to another node.  The NULL value for the pointer in the last node is a special C++ constant that represents a value for a C++ pointer variable that does not point to any valid memory location but is useful for comparison purposes.   The pointer variable h points to the beginning of the linked list.  It is the only variable whose memory must be allocated before construction of the linked list begins.   Normally a collection of data items are stored in each node.  For example, inventory information for one item might be stored in each node.  Thus the information stored in each node is usually represented by a C++ struct.  Information may be stored on a linked list in an arbitrary order, but sometimes it is stored in ascending order by one of the fields in the struct that is stored at each node.   Note that, when the list is empty, the value of the pointer variable h is NULL.

Suppose that the numbers 30, 10, 50, and 40 are to be entered in the order given and are to be stored in ascending order on the list.  Remember that h will have the value of NULL before this process begins.  After 30 is inserted, the list appears as follows.

After 10 is inserted the list now looks like the following.

After 50 is inserted, the list will be changed to appear as the following diagram shows.

The final list will then appear as follows.

The program that appears below reads a list of integers similar to the above which is terminated by zero and inserts the values onto a linked list of integers.  It then prints the values stored on the list.  The code in this program will be discussed in the next set of notes.  Your current assignment can be constructed in a similar way to this program except that you must place a struct at each node in place of the integer value.

//
//
//  list.cxx
//  inserts elements onto a linked list in order
//
//

#include <iostream.h>

//  Type Declarations

typedef int LISTTYPE;

struct noderec {
                         LISTTYPE info;
                         noderec *next;
               };

typedef noderec * PTR;

//  Function Prototypes

PTR newnode(),findpos( PTR, LISTTYPE );

void create( PTR &),
     printlist( PTR ),
     readlist( PTR &),
     printinfo( LISTTYPE ),
     readinfo( LISTTYPE &);


void push( PTR &, LISTTYPE ),
     insafter( PTR, LISTTYPE );

void main(void)
{
 PTR l;             //  l points to the beginning of a linked list
 LISTTYPE x;        //  temporary input variable

 create(l);         //  creates an empty list
 readlist(l);      //  reads values and places them on the list
 printlist(l);      //  prints the values stored on the list

}

PTR newnode()      //  allocates storage for a new node
{
 PTR p;
 p = new noderec;
 return p;
}

void create( PTR &l)   //  creates an empty list pointed to by l
{
 l=NULL;
}

//  Inserts an element with value x at the beginning

void push( PTR &l, LISTTYPE x)
{
 PTR p;
 p = newnode();         // allocate storage for a new node
 p->info = x;           //  store x at this node
 p->next = l;           //  point to the beginning of original list
 l = p;
}

void printlist(PTR l)    //  prints the values stored on the list
{
 PTR p;
 p=l;
 while( p!=NULL )
   {
    printinfo( p->info );
    cout << endl;
    p = p->next;
   }
}

void readlist(PTR &l)    //  reads values and places them on the list
{                         //  in ascending order
  LISTTYPE x;
  PTR pos;
  readinfo( x );                //  Read first value
  while( x != 0 )
    {
     pos = findpos( l, x );     //  Find location of value
     if(pos == NULL )
       push(l, x );             //  If list is empty, place at beginning
     else
       insafter( pos, x );      //  Place in proper location
     readinfo( x );             //  Read next value
    }
}

void printinfo( LISTTYPE x )        //  Print value for a list element
{                                   //  Modify this when LISTTYPE changes
  cout << x;
}

void readinfo( LISTTYPE &x )        //  Read value for a list element
{                                   //  May need to be separated into parts
  cin >> x;                         //  If LISTTYPE is a struct
}

void insafter( PTR q, LISTTYPE x )  //  Insert a new node following the node
{                                   //  To which q points.  q is passed from
  PTR p;                            //  the calling function.
  p = newnode();
  p->info = x;
  p->next = q->next;
  q->next = p;
}

PTR findpos( PTR l, LISTTYPE x )       //  Find the position of a given
{                                      //  element on a list if the element
  int found = FALSE;                   //  is to appear in order.
  PTR p = l, q = NULL;
  while( ( p != NULL ) && (!found) )   //  Continue until end of list or value
    if( x <= p->info )                 //  is found.
      found = TRUE;
    else
      {
        q = p;                         //  Move both pointers
        p = p->next;
      }
  return q;
}