Add to the tail of the linked list without using if

Question

It was an interview question, and I thought I would share it with the rest.

How to effectively add the tail of a linked list without using "if"?

Remove if from this function. ( ? is still an if ).

 typedef struct tNode_ tNode; struct tNode_ { tNode* pNext; int data; }; tNode* pHead = NULL; tNode* pTail = NULL; AddTail(tNode* pNode){ if(!pTail) { pHead = pNode; } else { pTail->pNext = pNode; } pTail = pNode; pTail->pNext = NULL; } 

Answer 1

 typedef struct tNode_ tNode; struct tNode_ { tNode* pNext; int data; }; /* normal initialization for pHead */ tNode* pHead = NULL; /* the trick is to point at where you want the next pointer to go * instead of saving a pointer to the node. */ tNode** ppTail = &pHead; AddTail(tNode* pNode){ pNode->pNext = NULL; /* update the next pointer */ *ppTail = pNode; /* save the address of the next pointer */ ppTail = &pNode->pNext; } main(){ int cnt; tNode* pNew; for(cnt=0; cnt<10; cnt++){ pNew = malloc(sizeof(tNode)); pNew->data = cnt; AddTail(pNew); } for(pNew = pHead; pNew; pNew = pNew->pNext){ printf("%d\n", pNew->data); } } 

Answer 2

One (admittedly stupid) way to do this is to use the behavior of short trailing logical operators && and || . For example, you can do this:

  AddTail(tNode* pNode){ pTail || (pHead = pNode); !pTail || (pTail->pNext = pNode); pTail = pNode; pTail->pNext = NULL; } 

This works because if ptail is NULL, the first part of the first statement will evaluate to false, forcing the second half of the || . If it is not equal to zero, the second half of the instruction will not be evaluated. Similar logic works for the following statement.

However, this is a very stupid interview question, and I honestly don't know what they are aiming for. Personally, I would question the wisdom of someone trying to gauge your ability to write such code.

Hope this helps!

Answer 3

I would use a dummy element (or sentinel node , as they call it) for each list. An addition to the head becomes an addition to the dummy, an addition to the tail is simply an addition to the last element that by definition exists.

 typedef struct tNode_ tNode; struct tNode_ { tNode* pNext; int data; }; // The Remove operation must never remove this dummy! tNode* pDummy = (tNode*)calloc(1, sizeof(tNode)); tNode* pHead = pDummy; tNode* pTail = pDummy; AddTail(tNode* pNode){ pTail->pNext = pNode; pTail = pNode; pTail->pNext = NULL; } 

Answer 4

 tNode pHead; tNode pTail; void init() { pHead.pNext = &pTail; pTail.pNext = &pHead; } AddTail(tNode* pNode){ pTail.pNext->pNext = pNode; pNode->pNext = &pHead; pTail.pNext = pNode; }