Linked Lists Confusion

[JesusFreak43]

Hi, what I am confused about is the insertNode function in this class. Under the first else where it says:

 if (newitem >= first->info)//e.g., 25 > 3
            {
                newNode->link = first->link;
                first->link = newNode;
                first = newNode;
            }

I am confused what first points to. Isn't first just a pointer and it doesn't have a link to it? I'm confused because in the class they declared first like this: nodeType<Type> *first; Why did the make first like a node instead of making it just a regular pointer that points to the first element?

So I am confused about that, but also when it says first->link = newNode; wouldn't that have the first element of the list point to newNode? (I saw in my textbook its useful to have first point to the last element of a circular linked list, so I was thinking that was what they were doing here.) I suppose I need some more explanation of how this works.

This is declared in my code:

template <class Type>
struct nodeType
{
    Type info;
    nodeType<Type> *link;
};

And this is declared in the protected region of my class code:

nodeType<Type> *first;

This is the insertNode function in my class:

    void insertNode(const Type& newitem)
    {
        nodeType<Type> *current; //pointer to traverse the list
        nodeType<Type> *trailCurrent; //pointer just before current
        nodeType<Type> *newNode;  //pointer to create a node
        
        bool  found;
        
        newNode = new nodeType<Type>; //create the node
        
        newNode->info = newitem;   //store newitem in the node
        newNode->link = NULL;      //set the link field of the node
        //to NULL
        
        if (first == NULL)  //Case 1    e.g., 3
        {
            first = newNode;
            first->link = newNode;
            count++;
        }
        else
        {
            if (newitem >= first->info)//e.g., 25 > 3
            {
                newNode->link = first->link;
                first->link = newNode;
                first = newNode;
            }
            else
            {
                trailCurrent = first; //e.g., 1 < 3
                current = first->link;
                found = false;
                
                while (current != first && !found)
                    if (current->info >= newitem)
                        found = true;
                    else
                    {
                        trailCurrent = current;
                        current = current->link;
                    }
                
                trailCurrent->link = newNode;
                newNode->link = current;
            }
            
            count++;
        }//end else
    }
    
    

[keskiverto]

Lets call:

first == A
first->link == B // B is after A
newnode == C

List has {A,B} and first points to A.

C->link = B; // C will be before B
A->link = C; // C is after A
first = C;

List has {A,C,B} and first points to C.
List is circular, and therefore you could show it as {C,B,A}.

[dhayden]

I'm confused because in the class they declared first like this: nodeType<Type> *first; Why did the make first like a node instead of making it just a regular pointer that points to the first element?

Is it just a pointer. That's what the "*" in the declaration does. first is "pointer to nodeType<Type>"

Isn't first just a pointer and it doesn't have a link to it?

first is a pointer. *first is the thing that first points to. (*first).link is the link field of the thing that first points to. first->link is the same as (*first).link.

I saw in my textbook its useful to have first point to the last element of a circular linked list, so I was thinking that was what they were doing here.

Yes, I think you're right, although for the life of me, I can't understand why you'd call it "first" if it actually points to the last item.

Here is the code with different comments and with "first" renamed to be "last". I've also incremented count in just one place. This might make the logic clearer.

void
insertNode(const Type & newitem)
{
    nodeType < Type > *current;			 //pointer to traverse the list
    nodeType < Type > *trailCurrent;		 //pointer just before current
    nodeType < Type > *newNode;			 //pointer to create a node

    bool found;

    // Create the new node and populate it. For now we'll set
    // its link to NULL
    newNode = new nodeType < Type >;
    newNode->info = newitem;
    newNode->link = NULL;

    // If the list is empty them make newNode the only node
    if (last == NULL) {
	// newNode becomes the first and last node.
	// It points to itself.
	last = newNode;
	last->link = newNode;

    } else if (newitem >= last->info) {
	// If the new node is larger than the last node then add
	// it to the end
	newNode->link = last->link;		 // link it back to first node
	last->link = newNode;			 // insert it after last
	last = newNode;				 // now it's the last node
    } else {
	// NewNode goes somewhere in the middle
	trailCurrent = last;			 //e.g., 1 < 3
	current = last->link;			 // remeber, last->link is first node
	found = false;

	while (current != last && !found)
	    if (current->info >= newitem)
		found = true;
	    else {
		trailCurrent = current;
		current = current->link;
	    }

	trailCurrent->link = newNode;
	newNode->link = current;
    }

    count++;
}