Linked Lists in C
To efficiently implement q_size and q_insert_tail, we add a pointer called tail
to point the end of the queue and an integer called size
to record the size of this queue.
We allocate space for this queue structure and make the head pointer point to NULL. If the malloc fails, the pointer q would be assigned NULL. We use this attribute to detect malloc failure.
In this code, we use two-pointer(temp, prev) to go through this queue. Prev points to the element temp just went through. Whenevertemp goes through an element, we free the string that element points to. After that, prev will go through this element and free it.
First, we handle the special conditions like: queue doesn’t exist(q == NULL), malloc failure when allocating space for string or element. Note that, at line 29, we need to free the space we just allocated or it would be a memory leak.
Then we need to do the right move corresponding to two situations: the queue is empty or not. If it is, we need to point both the head and a tail pointer to this new element. Also, the new element should point to NULL. If it’s not, we make the new element point to the old head element, then point the head point to the new element.
q_insert_tail is highly similar to q_insert_head, the functionality is the same and also the special conditions and situations need to be handled. To keep this note short, I won’t elaborate on this function here because the content would be almost the same.
Note: we are required to implement this function in O(1). The key point to do so is in the queue structure declaration. We declared the tail pointer in this structure so that we can easily use the same method as q_insert_head and implement this function in constant time.
First, we use a simple if statement to handle the situations that q is empty or doesn’t even exist(q==NULL or q->head==NULL). Then we check if sp is non-NULL. If it is, we need to copy the string we are about to remove to sp.
Then, we can free the space and adjust the pointers to make the linked list still works properly.
Instead of calculating the size in this function, we record the size of the queue everytime we insert or remove an element. To do so, we need to declare an integer called size in the queue structure.
You can go and check the code above, there is a line q->size--; or q->size++; everytime we remove or insert an element.
First, we handle the special cases, empty queue, and non-existing queue. In these two cases, we don’t need to do anything.
Then, we use three pointers here, which are prev, temp, and next. prev holds the element previous to temp, and next holds the one next to temp. We go through the whole list from the head and make the element held by temp point to the previous one, then move to the next element by using next. This move will keep being implemented until temp reaches NULL.