CODEWITHSUNDEEP
cdata-structureslinked-list
kdubs
kdubs

Reputation: 1722

Add to tail of linked list without using an if

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

Upvotes: 4

Views: 2467

Answers (4)

perreal
perreal

Reputation: 98088

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

Upvotes: 1

krlmlr
krlmlr

Reputation: 25484

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

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373042

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!

Upvotes: 2

kdubs
kdubs

Reputation: 1722

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

Upvotes: 1

Related Questions