Inserting into a linked list

Question

I know that this is very very basic, but now I am starting from group up after getting frustrated with my coding practices and knowledge of standard idioms out there and elegant way of coding corner cases. The problem is to insert into tail of a linked list.

void insertattail (struct node *head, int data)
{
  //First construct the node in newp
  struct node *newp;
  struct node *p;
  newp = malloc (sizeof (struct node));
  newp -> data = data;
  newp -> next = NULL; 

  // Standard name for node pointers only used for traversal? p? q? tmp?
  // if more than 1 kind of nodes?
  // Then what about temp pointers for swapping etc but not exactly for traversal?

  if (head == NULL)  // is there more elegant way of dealing with this? any idiom?
  {
    head = newp;
    return;
  }

  for (p=head; p->next != NULL; p++)
    ;
  p->next=newp;
}

I've always like curr for "current node pointer" to match next and previous. — David Harkness
– David Harkness, Commented May 30, 2011 at 21:21

Winston Ewert · Accepted Answer · 2011-05-30 15:37:42Z

if(head == NULL)  // is there more elegant way of dealing with this? any idiom?
{
head=newp;
return;
}

head is a local variable in this function. Modifying it will not change the variable that was passed into the function. As a result, the new node you create isn't attached to anything that the caller can access. If you want to modify a variable being passed in you need to use a pointer. If you want to modify a pointer, you need to use a pointer to a pointer.

Here is a version which reduces the amount of code, but for those who don't think in pointers naturally it may be hard to follow.

// I take a pointer to a pointer so that I can modify it if need be.
void insertattail(struct node **head,int data)
{
    // advance the pointer until it reaches NULL
    // because its a pointer to a pointer I can modify it
    while(*head != NULL) head = &(*head)->next;

    // replace that NULL with a new node
    *head = malloc(sizeof(struct node));
    // fill up the node
    (*head)->data = data;
    (*head)->next = NULL;
}

Chris · Accepted Answer · 2025-11-24 00:47:45Z

If we're assuming that head is not NULL, so let's split up the responsibilities: writing a separate function that finds the tail of a list.

Having done that, inserting the new node at the tail is easy.

struct node *tail_of_list(struct node *head) 
{
    struct node *curr = head;
    for (; curr && curr->next; curr = curr->next);

    return curr;
}

void insertattail(struct node *head, int data)
{
    if (!head) 
    {
        return;
    }

    struct node *tail = tail_of_list(head);
    tail->next = malloc(sizeof(*head));

    if (!tail->next) 
    {
        return;
    }

    tail->next->data = data;
    tail->next->next = NULL;
}

Of course, I would argue the ideal way to handle the empty list scenario is to create a strust linked_list which has pointers to the head, tail, and stores the length of a linked list.

struct linked_list 
{
    struct node *head;
    struct node *tail;
    size_t length;
};

This solves the empty list scenario and if our insertion and removal operations maintain that last pointer correctly, insertion at the tail becomes O(1) rather than O(n).

Stack Exchange Network

Inserting into a linked list

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Inserting into a linked list

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions