CODEWITHSUNDEEP
clinked-list
bouncingHippo
bouncingHippo

Reputation: 6040

optimizing a special case in linkedlist by tail-building

I want to build a list {1, 2, 3, 4, 5} by appending the nodes to the tail. For our client purposes, all the other nodes are inserted after the last node using a tail pointer. The only "problem" with this solution is that coding separate special case for the first node can be optimized, and the client is pressing me. Nonetheless, this approach should be solid one for production code in theory...at least i thought until it keeps throwing null pointer exception when i get to the tail...am i missing something?

struct node* BuildWithSpecialCase() {
    struct node* head = NULL;
    struct node* tail;
    int i;

    Push(&head, 1);
    tail = head;

    for (i=2; i<6; i++) {
        Push(&(tail->next), i); 
    }
    return(head); 
}

Upvotes: 1

Views: 174

Answers (1)

Edwin Buck
Edwin Buck

Reputation: 70949

If all of your accessing pointers are traveling from the head to the tail, then adding nodes to the tail exposes them to "new" data that didn't exist at the time the "querying" of the list started.

Talk to your client, perhaps there is more than just "optimization" at stake.

--- Edited after seeing your code edit ---

Without an understanding of what Push is doing, I'll guess it's pushing a node on top of the linked list as if it were a stack.

Push(&head, 1);
tail = head;

So far, so good.

for (i=2; i<6; i++) {
    Push(&(tail->next), i); 
}

It appears that you just Pushed several nodes at tail, but I can't see where you actually updated the tail to maintain it's reference to the end of the list. In my reading, head still points to the head of the list, tail still points to the head of the list (from the assignment tail = head) and you have a lot of "extra" nodes beyond tail.

Is that the problem?

Upvotes: 2

Related Questions