I don\'t know how to do this. What is the algorithmic complexity of each of the
ID: 3690152 • Letter: I
Question
I don't know how to do this.
What is the algorithmic complexity of each of the deque operations?
struct dlink {
TYPE value; struct dlink * next; struct dlink * prev;
};
struct linkedList {
int size;
struct dlink * frontSentinel; struct dlink * backSentinel;
};
/* these functions are written for you */ void LinkedListInit (struct linkedList *q) {
q->frontSentinel = malloc(sizeof(struct dlink)); assert(q->frontSentinel != 0);
q->backSentinel = malloc(sizeof(struct dlink)); assert(q->backSentinel); q->frontSentinel->next = q->backSentinel; q->backSentinel->prev = q->frontSentinell; q->size = 0;
}
void linkedListFree (struct linkedList *q) { while (q->size > 0)
linkedListRemoveFront(q); free (q->frontSentinel);
free (q->backSentinel);
} q->frontSentinel = q->backSentinel = null;
void LinkedListAddFront (struct linkedList *q, TYPE e) { _addBefore(q, q->frontSentinel_>next, e); }
void LinkedListAddback (struct linkedList *q, TYPE e) { _addBefore(q, q->backSentinel, e); }
void linkedListRemoveFront (struct linkedList *q) { assert(! linkedListIsEmpty(q));
_removeLink (q, q->frontSentinel->next); }
void LinkedListRemoveBack (struct linkedList *q) { assert(! linkedListIsEmpty(q));
_removeLink (q, q->backSentinel->prev); }
int LinkedListIsEmpty (struct linkedList *q) {
return q->size == 0; }
Or this
/* write addLink and removeLink. Make sure they update the size field correctly */
/* _addBefore places a new link BEFORE the provide link, lnk */ void _addBefore (struct linkedList *q, struct dlink *lnk, TYPE e) {
}
void _removeLink (struct linkedList *q, struct dlink *lnk) {
}
TYPE LinkedListFront (struct linkedList *q) {
}
TYPE LinkedListBack (struct linkedList *q) {
}
Explanation / Answer
I have answered first part. I have mentioned time complexity of each function using comment
struct dlink {
TYPE value; struct dlink * next; struct dlink * prev;
};
struct linkedList {
int size;
struct dlink * frontSentinel; struct dlink * backSentinel;
};
/* these functions are written for you */
/* This function takes O(1)[constant] time. */
void LinkedListInit (struct linkedList *q) {
q->frontSentinel = malloc(sizeof(struct dlink));
assert(q->frontSentinel != 0);
q->backSentinel = malloc(sizeof(struct dlink));
assert(q->backSentinel);
q->frontSentinel->next = q->backSentinel;
q->backSentinel->prev = q->frontSentinell;
q->size = 0;
}
/* This function takes O(n) time, as we are traversing through linked list */
void linkedListFree (struct linkedList *q) {
while (q->size > 0)
linkedListRemoveFront(q);
free (q->frontSentinel);
free (q->backSentinel);
q->frontSentinel = q->backSentinel = null;
}
/* THis function takes O(1) time. THis function add a new element at front thatt takes constant time*/
void LinkedListAddFront (struct linkedList *q, TYPE e) {
_addBefore(q, q->frontSentinel_>next, e);
}
/* As we have pointer of last elements, so to add element at last, it takes constant time=> O(1) */
void LinkedListAddback (struct linkedList *q, TYPE e) {
_addBefore(q, q->backSentinel, e);
}
/* Time complexity: O(1)
void linkedListRemoveFront (struct linkedList *q) {
assert(! linkedListIsEmpty(q));
_removeLink (q, q->frontSentinel->next);
}
/* Since this is doubly linked list and we have pointer to last element, so delete
last elemetn takes O(1) time */
void LinkedListRemoveBack (struct linkedList *q) {
assert(! linkedListIsEmpty(q));
_removeLink (q, q->backSentinel->prev);
}
/* TIme Complexity: O(1) */
int LinkedListIsEmpty (struct linkedList *q) {
return q->size == 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.