2
$\begingroup$

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 -

Image example

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.

$\endgroup$
  • 2
    $\begingroup$ I'm not sure what you're asking. Your question appears to be "This programming challenge wants me to do X. Wouldn't it be more sensible to do Y?" First, programming questions are off-topic here. Second, the programming challenge is challenging you to do a particular thing so, to pass the challenge, you need to do that thing. SoI don't understand what you're asking. $\endgroup$ – David Richerby Jun 22 '16 at 7:37
  • 1
    $\begingroup$ I'm not doing that all. I'm asking, as the question headline implies, what the best way of implementing a linked list is, having seen conflicting suggestions and examples. $\endgroup$ – JasTonAChair Jun 22 '16 at 7:39
  • $\begingroup$ So to clarify, the challenge was the catalyst for me to ask the question but I'm interested to see what the most logical way is to do this in any language. $\endgroup$ – JasTonAChair Jun 22 '16 at 7:41
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ tail may be a bad name since it often refers to all of the list but the first element. $\endgroup$ – Raphael Jun 22 '16 at 8:07
  • $\begingroup$ I take your point on next vs heaf. Cheers $\endgroup$ – JasTonAChair Jun 22 '16 at 8:20
0
$\begingroup$

One of the solutions can be:

enter image description here

enter image description here

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....

$\endgroup$
  • 1
    $\begingroup$ I'd like to mark this as correct but I have no idea what's going on, is this C++? I'm a n00b $\endgroup$ – JasTonAChair Jun 22 '16 at 6:35
  • $\begingroup$ This is 'C', you can go through cs.princeton.edu/courses/archive/spr11/cos217/lectures/… for basic of Linked lists with 'C'. $\endgroup$ – Maharaj Jun 22 '16 at 6:44
  • 2
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. (If the question can only be answered by showing C code, then it is off-topic here, and it's better to avoid answering off-topic questions.) $\endgroup$ – D.W. Jun 22 '16 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.