Add to tail of linked list without using an if

Question

This was an interview question and I thought I'd share it with the rest of you.

How does one efficiently add to the tail of a linked list without using an "if"?

Remove the 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;
}

This strikes me as an extremely silly interview question - why would anyone disallow you use of a fundamental programming construct? Additionally, can you please post more code here? You haven't defined `pHead`, `pTail`, or the shape of the struct `tNode`. — templatetypedef, Jan 02 '13 at 01:58
the idea was to think about what you are actually trying to accomplish. There's a simple solution if you look and the true end goal. — kdubs, Jan 02 '13 at 02:01
@templatetypedef: See this question about [branch prediction](http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array). — krlmlr, Jan 02 '13 at 02:01
@user946850- That strikes me as an egregious microoptimiation. Unless this code is absolutely time-critical, this seems like an unnecessary complication. — templatetypedef, Jan 02 '13 at 02:02
@templatetypedef: It might be, you never know. Stamping this question as silly is, well, you know... let's say, ignoring its beauty. — krlmlr, Jan 02 '13 at 02:03
@user946850 If that function is called frequently enough for the `if` to potentially matter, the branch predictor will have a perfect playing field. — Daniel Fischer, Jan 02 '13 at 02:04
@DanielFischer: What about add^n + remove^n, n varying between 1 and, say, 5? — krlmlr, Jan 02 '13 at 02:06
I think the interviewer was looking for you to add a sentinel object, ensuring that `pHead` is never `NULL`. — Sergey Kalinichenko, Jan 02 '13 at 02:10
@user946850 Then any half-sane person would use a circular buffer, and not a linked list. — Daniel Fischer, Jan 02 '13 at 02:10
If you are allowed to change the node/list structures, you could use something similar to [AmigaOS linked lists](http://gega.homelinux.net/AmigaDevDocs/lib_23.html). The head and tail pointers are always valid, so adding a node to the head or the tail of the list is very efficient. — Some programmer dude, Jan 02 '13 at 02:15

score 2 · Answer 1 · answered Jan 02 '13 at 02:01

2

One (admittedly silly) way to do this is to use the behavior of the short-circuiting logical operators && and ||. For example, you could 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 evaluation of the second half of the || statement. If it's non-null, the second half of the statement will not be evaluated. Similar logic works for the next statement.

That said, this is a very silly interview question and I honestly don't know what they're getting at. Personally, I would question the wisdom of someone trying to assess your ability to write code like this.

Hope this helps!

answered Jan 02 '13 at 02:01

templatetypedef

362,284
104
897
1,065

Wow, this trick would probably score very high in the nomination "the mother of all hacks" :):):) – Sergey Kalinichenko Jan 02 '13 at 02:04
@dasblinkenlight- From my understanding, this is a normal Perl idiom (though I'm not a Perl programmer). Or perhaps I've just read very odd Perl code. :-) – templatetypedef Jan 02 '13 at 02:05
1

@templatetypedef "a normal Perl idiom" implies a high ranking in "the mother of all hacks". – Daniel Fischer Jan 02 '13 at 02:07
To me, almost any piece of code written in Perl qualifies as "a very odd Perl code" :) – Sergey Kalinichenko Jan 02 '13 at 02:08
@templatetypedef: The interviewer would still classify this as an `if` construct... – krlmlr Jan 02 '13 at 02:28
@user946850- The OP specifically disallowed `if` and `?`, but did not disallow any other constructs. I'm completely aware that this goes against the *spirit* of the question, but it's well within the letter. – templatetypedef Jan 02 '13 at 02:28
that's what it's about. thinking around the if. I like this, but it's not the most efficient. – kdubs Jan 02 '13 at 04:01

score 1 · Accepted Answer · answered Jan 02 '13 at 01:59

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);
  }
}

answered Jan 02 '13 at 01:59

kdubs

1,596
1
21
36

What is the benefit of introducing an extra layer of indirection when the current version works perfectly well? I'm skeptical that this is a fundamentally more elegant solution to the problem. – templatetypedef Jan 02 '13 at 02:03
getting rid of a branch is a good thing for branch prediction. But the question is an attempt to get one to think about the end goal. – kdubs Jan 02 '13 at 02:10
@kdubs- I'm not a hardware expert, but isn't the cost of a pointer indirection that isn't in cache much greater than the cost of a branch misprediction? (See the numbers here: https://gist.github.com/2841832). But more importantly - I fundamentally disagree with the idea that this is trying to get you to think about "the end goal." The code you've posted in the original question is absolutely standard linked list manipulation code. Saying that the use of an `if` statement misses sight of "the end goal" seems very misguided. But that's just my opinion. – templatetypedef Jan 02 '13 at 02:12
it's the same about of hardware access. either way you have to access the memory at that next pointer. This way you avoid a read, and only do a write. – kdubs Jan 02 '13 at 03:59

score 1 · Answer 3 · answered Jan 02 '13 at 02:11

1

I would use a dummy element (or sentinel node as they call it) for each list. Appending to the head becomes appending to the dummy, appending to the tail is just appending to the last element which then 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;
}

answered Jan 02 '13 at 02:11

krlmlr

25,056
14
120
217

Why do you need 3 pointers? Wouldn't it be sufficient to just have `pHead` and `pTail` and set `pTail = pHead`? – Ungeheuer Sep 09 '17 at 06:58
Maybe to conserve the initial value? – krlmlr Sep 09 '17 at 07:40

score 1 · Answer 4 · answered Jan 02 '13 at 02:20

1

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;
}

answered Jan 02 '13 at 02:20

perreal

94,503
21
155
181

What's the benefit of having two sentinel objects? – krlmlr Jan 02 '13 at 02:21
It helps to eliminate if statements, and makes head-tail management easier. – perreal Jan 02 '13 at 02:22
But you still need to check if the list is empty before attempting to remove a node? – krlmlr Jan 02 '13 at 02:24
the question is not about deleting nodes though – perreal Jan 02 '13 at 02:26
interesting. there's no if, but not sure how you tell the list is empty in this case. the pointers form an infinite loop at first. – kdubs Jan 02 '13 at 04:09
the list is empty `if (pHead.pNext == &pTail)` – perreal Jan 02 '13 at 04:16

Add to tail of linked list without using an if

4 Answers4