CODEWITHSUNDEEP
clist
Kyuu
Kyuu

Reputation: 1045

how to keep track of my tail node in a linked list

How can I keep track of my tail node so I can return its value quickly. This is how Im creating my list so far but I want to write a function that can return the very last node and delete it from the list. Not too sure where to start

typedef struct node_t{
    int val;
    struct node_t *next;
}node_t;

int main(int argc, char *argv[])
{
    int input;
    node_t *list;
    list = NULL;
    list = push(1,list);
    list = push(2,list);
    list = push(3,list);
    return 0;
}


node_t *push(int input, node_t *list)
{
    if(list == NULL)
    {
        list = makeStack(input, list);
        return list;
    }

    else
    {
        list->next = push(input,list->next);
    }
    return list;
}

Upvotes: 1

Views: 1349

Answers (1)

Andrzej Budzanowski
Andrzej Budzanowski

Reputation: 1022

Basically there are two approaches:

You can calculate pointer of last node with function like:

node_t * find_last( node_t * ptr )
{
 /* is this node last? */
 if ( ptr->next == NULL )
  return ptr;

 /* let's travel to last node */
 do
  ptr = ptr->next;
 while ( ptr->next != NULL );

 /* and then return it */
 return ptr;
}

But with large list this function can be expensive.

Second approach requires you to simply cache value of last pointer in some kind "base" struct.

typedef struct
{
 node_t * first;
 node_t * last;
} linked_list_t;

Upvotes: 1

Related Questions