Linked Lists....Trouble.

[Amaz1ng]

#include <stdio.h>
#include <stdlib.h>

struct node
{
	int x;
	struct node *next;
};

//this function is to build a list by creating a node then appending it on the end of the list
node * create_append(int x, node * oldtail);

//navigate and print list
void print_list(node * list);

void main()
{
	node *head;
	node *tail;
	node *insert;

	head = (node*)malloc(sizeof(node));
	tail = head;
	head->next = tail;
	tail->next = NULL;

	/*insert = (node*)malloc(sizeof(node));
	insert->x = 6;
	insert->next = NULL;*/

	for(int i = 0; i <= 5; i++)
	{
		create_append(i, tail);
		
	}

	print_list(head);
}

node * create_append(int x, node * oldtail)
{
	node * temp;
	temp = (node*)malloc(sizeof(node));
	oldtail->next = temp;
	temp->x = x;
	temp->next = NULL;
	return temp;
}

void print_list(node * list)
{
	node * end;
	end = (node*)malloc(sizeof(node));
	end = list;
	while(end->next != NULL)
	{
		printf("%d\r\n", end->x);
		end = end->next;
	}
}

Code not working. O_o I'm about to get out some notebook paper and write everything down instead of doing it in my head but in the meantime I thought I'd post here. This code doesn't do what I want (look through and append new node to end, then print). Any ideas?

Ultimate goal is to do this:
"Insert in order Given a linked list of integers sorted from smallest (at the head end) to largest, and a pointer to a single node containing an integer, insert the node in the linked list so that it remains sorted."

[ThermoSight]

Just a quickie comment/question: in function create_append, are you updating 'tail' to point to each new insertion ?

It seems to me that the 'x' argument is in ascending order, and I think your requirement is ascending order, but using 'oldtail' which does not appear to change (at least I don't see where it is changed) AND your unequivocally setting temp->Next to NULL seems to indicate that neither the sorting nor the linkage is maintained.

I dunno, just a thought after a quickie glance at the code.

Perhaps the easiest way to update the 'tail' is simply to change "create_append(i, tail); " to something like "tail = create_append(i, tail);" (which is probably what you had intended all along, and the omission is simply a typo).

Incidentally, I'd probably make the insertion the last part of the create+append function ... I note that you link it in BEFORE you insert the value and NULLify the next pointer.

Incidentally, a short time ago I tried the suggested modification on my 'chine and it seemed to be working, at least according to the debugger output (if I'm reading it corectly!). Also, my earlier comment about "unequivocally setting temp->Next to NULL " would probably be true if your intent was to insert newbies at the list head, but then the function probably wouldn't be named create_append, would it?


Ya know, after re-reading the requirement, I think we have not yet quite satisfied the assignment. With the above suggested change, we now have the sorted linked list. Now it's time to remove the commenting you have around the code that creates a new node, move those lines to a point AFTER the creation of the linked list, and perhaps create, then call, a new function (possibly called "insert_sorted(node* newbie)" ?) which will insert the new node in the correct spot in the list.

the following seems to work on my 'chine; ain't necessarily the finest function but it seems to be serviceable ....

// **********************************************************
void insert_sorted(node* newbie) {

	node* listEntry = head;
	node* lastCandidate = nullptr;

	// if trivial case of empty list ...
	// set head and tail to point to new guy
	// (NOTE that our list does not employ the 
	//       dummy node from the original code)
	if (listEntry == nullptr)
		head = tail = newbie;

	else {// it's the non-trivial case...

		while (listEntry != nullptr) {
			// if the listEntry is less than newbie, THEN
			//    if the next is null handle End of List.
			if (listEntry->x < newbie->x)
				// if there's another node in this list, get it!
				if (listEntry->next != nullptr){
					lastCandidate = listEntry;
					listEntry = listEntry->next;
				}
				else {// handle End of List; link ourselves in at EOL.
					listEntry->next = newbie;
					tail = newbie;
					break;
				}
			else {// handle case where listEntry is >= newbie
				// whether listEntry is > or == to new guy, we'll
				// insert new guy 'preceding' listEntry, 
				// so newbie->next must point to listEntry.
				newbie->next = listEntry;

				// then, if this is the head of the list,
				// set the list head to point to new guy
				// else set previous listEntry->next to point to new guy.
				if (lastCandidate == nullptr)
					head = newbie;
				else
					lastCandidate->next = newbie;
				break;
			}// end ELSE listEntry is >= new guy
		}// end WHILE (listEntry != nullptr);
	}//end ELSE this ain't the trivial 'empty list' case
}// end function 'insert_sorted'
// ************************************************************************

Anyway, ... just a comment or two from some OldFool, and worth exactly what you paid for it.

-bill-

[Amaz1ng]

Hey I have another question concerning this code:

void insertNodeInOrder( Node *newNode, Node *&head ) {
    // Precondition: newNode points to a node.
    // head is the head link of a sorted linked list.
    Node **linkP = & head ;
    // Let linkP point to the link after which we must insert
        // Invariant: linkP points to a link and the data
        // fields of all nodes before *linkP are smaller
        // than newNode->data.
        while( *linkP != 0 && (*linkP)->data < newNode->data ) 
            linkP = & (*linkP)->next ;

    // Now insert the node
        newNode->next = *linkP ;
        *linkP = newNode ;
}

What does this do? I don't understand why the & is there?

Node *&head

can you break this down aswell. What happening here?

 Node **linkP = & head ;

[ThermoSight]

"Node **linkP = & head ;"

Well, it appears to me that "linkP' is a pointer, not to a Node, but to a Node*. In other words, it's a Node-pointer pointer. It points to a Node pointer.

And the ampersand returns the address rather than the value associated with the target (as I recall).

Consequently, I'm thinking that the statement above places THE ADDRESS of 'head' (which a is a Node *) into 'linkP' which is a Node-pointer pointer. That seems logically consistent.

[Amaz1ng]

So linkp is a pointer to a pointer that holds the address of a node * that holds the address of the beggining of the list?

I think I get it now. LoL

[ThermoSight]

Yeah, it sounds a little silly, but when ya think about it ....

If one wishes to modify an integer, one may use an integer pointer to point to the integer to be modified.

BUT, when you want to make the integer pointer point to A DIFFERENT integer, one needs to modify the pointer ... and how does one do that, you ask .... simple! by using a pointer pointer, i.e. an int **.

In your case, that statement uses a Node**

Incidentally, I've found it helpful (especially when one is concerned about 'const-ness' and determining just what is 'const') to read the type statement backward such that

Node** linkP may be thought of as reading: linkP is a pointer to a Node pointer. Consequently, it should be initialized with an ADDRESS - either null (or in C#/C++ case: 'nullptr') or THE ADDRESS of a Node *.

Thus, "Node** linkP = &head" (where 'head' is a declared Node *) seems logically consistent to me.

Almost time for "60 Minutes" ... gotta scoot. Best wishes.

OldFool

[itsmeandnobodyelse]

Pointer to pointer is a C-style coding for passing 'changeable' pointers to a function. In C++ you got an additional reference type which turns the argument type to an input/output argument.

void insertNode(Node*& head);

Here the 'head' argument is a Node pointer which can have NULL value and when the function insertNode assigns a different value to head, the calling function will get the new (pointer value) returned:

void insertNode(Node*& head, int i)
{
     Node * p = new Node;
     p->data = i;
     p->next = NULL;

     if (head == NULL)       
    {
         head = p;    // here you also change the variable passed in the calling function

         return;
     } 
     ...
}

int main()
{
     Node * list = NULL;
     insertNode(list, 0);   

     // after the call 'list' has a valid pointer to Node
     ...
}