Correct way to implement linked list

Question

I'm doing this challenge on Hacker Rank that wants me to implement a linked list.

It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. Therefore the last instance added would have head=None (I'm using Python).

This is the pic they provide -

Wouldn't it make more sense to create a node instance with its head linked to the previous node? That way the only node with head=None would be the first node created.

I've seen conflicting suggestions so far. I'm not a CS student or developer.

EDIT -

This example from Youtube (1.36) suggests the second method.

EDIT -

Sorry if this seemed like a programming question. I'm trying to see if there's a logical way to set up linked lists for my own benefit... solving the HackerRank challenge is not the issue.

Answer 1

First of all, don't have a head pointer in your structure that doesn't point to the head of the list: it will confuse everyone. Call the pointer in your structure next or something!

You are right that in a singly-linked list (one with a next pointer but no pre pointer) it is illogical and inefficient to add new items to the end of the list. Singly-linked lists work best when you add each new item to the beginning of the list. Then all you need to do is:

1. Create a new item and fill in its data.
2. Set its next pointer to the value stored in the global head variable.
3. Set the global head variable to point to the new item.

Thus, as you say, only the first item to be added to the list will have next=null.

Adding items to the end of the list involves walking through the whole of the list every time, which is not efficient or sensible.

If you wanted a singly linked list to which you could add items at the end, you would have a second global variable (call it tail) pointing to the last item in the list. This makes for inelegant code, since you now have different kinds of behaviour when tail is null (which it will be at the beginning) and when tail is not null. In fact, a good way of handling matters in this case is to create the list with one fictional item in it already, and tail pointing to that item. This saves a lot of tests, but you will of course have to remember, when walking through the list, not to pay attention to that fictional item.

Answer 2

One of the solutions can be:

Node* insert(Node *head,int data)

{

Node *p,*q;


q=(struct Node *)malloc(sizeof(struct Node*));// Allocating memory for new node
if(q==NULL)
{
  printf("Memory Problem....");  //return if memory can't be allocated
  return 0;
}
q->data=data;                //Put data in data portion of the new node
q->next=NULL;                //The next link will point to NULL since it is getting added at the end of the list 
if(head == NULL)             //Check out if the list is empty
{
    head=q;                  //If empty the new node will be 'head'
}
else
{
    p=head;
    while(p->next != NULL)    // Otherwise get to the end of the list
    {
        p=p->next;
    }

    p->next=q;                //last node of the list will point to the new node created

}
 return head;                 

}

I have tested, it is working on Hacker Rank. Whether the head is linked to previous or next it has to be singly linked list and we have to traverse to the end of the list for insertion of a node.

I hope this is helpful to you....