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;