CS 201 - 9/18/14

On Syllabus, Midterm is listed at Thursday 10/14/14

    The 14th is a Tuesday.

    The original intent was to hold the exam on
           Thursday the 16th

  /* code to grow a queue dynamic array */

void enque ( queue* q, int val)
           {
              /* check if array is full */
              if ( isFull ( q ) == TRUE )
                 {
                  /* code to grow the array */
                  int* temp;
                  temp = (int*) malloc (sizeof (int)
                                   * (q->size * 2) );
                  int i, j;
                  i = 0;
                  j = q->frontPos;
                  while (j != q->backPos)
                    {
                     temp[i] = q->que[j];
                     i++;
                     j = (j+1) % q->size;
                    }

                  free (q->que);
                  q->que = temp;
                  q->backPos = i;
                  q->frontPos = 0;
                  q->size = q->size * 2;

                 }

       
              /* add the value to the queue */
              q->que[q->backPos] = val;
              q->backPos = q->backPos + 1;
              /* check if backPos needs to wrap around */
              if (q->backPos >= q->size)
                   q->backPos = 0;

           }


Linked Lists

    We dynamically allocate a chunk of memory for
      each item in the list.

    Each chunk of memory in the list contains 2 items
       1) whatever data is being stored for that item
       2) the location in memory of the next item in
             the list

    In a singularly linked link, we can access the
      next item, but not the previous item.

    In a doubly linked link, we also store the memory
       location of the previous item in the list

Storage Structure for a simple linked list

typedef struct linkedStruct
{
   int elem;
   struct linkStruct* next;
} listNode;

typedef struct linkedStruct* listPtr;

The authors have their structure format as:

typedef struct linkedStruct* listPtr;

typedef struct linkedStruct
{
   int      elem;
   listPtr  next;
} listNode;

The following code would create a short linked list:
   (no functions being used at this time)

   listPtr head;

   head = NULL;

   listNode temp1;  /* created on the stack */
   temp1.elem = 7;
   temp1.next = NULL;

                   /* created in the heap memory */
   listPtr temp2 = (listPtr) malloc ( sizeof(listNode));
   temp2->elem = 7;
   temp2->next = head;

   Most often (99.9999999% of the time) we want linked
    list nodes allocated/create in the heap memory

   head = temp2;