How do I go back to the first node in a linked list (C++ question)?

Question

I have a linked list composed of structures, NodeTypes, containing an int 'value' and NodeType* 'next,' pointing to the next NodeType in the list.

The first node created is named 'head' and then the new nodes are created in a cycle like so:

NodeType* current = new NodeType;
//code to define value of current
current->next = head;
head = current;

And then, finally, after the cycle ends, the final head's next value is set to NULL. The problem is, now head is the last node in the list, and since there's no "previous" node in the list, I can't go back.

My best guess as to how to solve this is to create a "firstNode" at the beginning, and make head start off pointing to firstNode, and then resetting head back to it after the cycle ends. Would this work? If not, how would I go about doing this?

Answer 1

This looks a little backwards to me. You have current->next pointing to head, what does head-next point to? I think it should be something like:

NodeType* head = new NodeType;

NodeType* current = new NodeType;

head->next = current;



//loop until end

current->next = new NodeType;

current = current->next;

Answer 2

The problem is in the way you're handling the list. You have a linked list here where you are always inserting at the front, which is fine. The problem is that you always need a variable called "head" for this and "head" should never be set to NULL. Head is the only way you can ever find your list, and if you set head to NULL you'll lose the whole thing.



I think your mistake here is in the sentence "after the cycle ends, the final head's next value is set to NULL". I'm not sure what you mean by final head. There is only one head. You don't need to do anything special after the cycle ends. Head should always point at the beginning, and since I assume head starts out as NULL, your list will always be terminated properly. The very first time you create a new element, it's next pointer gets the value of head, which is NULL. No need to go back and set it to NULL later.



Hope this helps.

Answer 3

A lot of people do it the way you described, as far as keeping track of two nodes; the first node is usually called "trunk".



It looks like this



struct node *trunk = my_newnode_func();

struct node *current = trunk;



/* do whatever with current */

current = trunk;



The order you build the list in isn't important; e.g. both of these are fine:



struct node *trunk = my_newnode_func();

struct node *current = trunk;

current->next = my_newnode_func();

current = current->next;

(etc)



or

struct node *trunk = my_newnode_func();

struct node *current = my_newnode_func();

current->next = trunk->next;

trunk->next = current;

(etc)



Another way to do this is with a doubly linked list. Those look like this:



struct node

{

void *data;

struct node *next;

struct node *prev;

}



You initialize both next and prev to NULL. That way, the first prev and last next are already nullified.



The third way to do it is to use a recursive function, passing node->next to the function, and setting the function's escape condition to something like



if (node == NULL)

return;



So the recursive function would look like



void my_recursive_function(struct node *node)

{

if(node == NULL)

return;

my_recursive_function(node->next);

}



Finally, you can make a circular list, and either use an endless loop, or set your escape condition to test the data instead of the node pointer itself (also testing the pointer itself to avoid dereferencing a null), e.g.



if(node == NULL || node->data == 2)

return;



That way, you can link the final node back to the head node. You'll still need to keep trunk and current seperate when you create the list, but the difference between this and the first method is that you dont' have to keep track of trunk seperately once you leave the function scope; any old port in a storm will do at that point.

Answer 4

You want 2 variables, first and last, pointing you can guess where. That way you can easily got to the first or last node. Set first when you create the first node, keep updating last as you create new nodes or deleting the tail node. (Don't change it if you insert a node or delete a 'middle' node.)

Answer 5

Yes, you always need a pointer to the head node, which never gets modified. For iterating through the list you use a temporary pointer - you never modify the original head pointer.

Answer 6

Thats the ONLY way to do it with a single linked list.