Cheap and Secure Web Hosting Provider : See Now

[Solved]: Correct way to implement linked list

, , No Comments
Problem Detail: 

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.

Asked By : JasTonAChair

Answered By : Martin Kochanski

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59885

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback