Sorted a Linked Node

[techjohnny]

Need help sorting this constructor:

I know the while loop should include another statement, but a little confused on the rest.

 void List::AddNode(int addData)
	
{
	// definition of the AddNode function
	nodePtr n = new node;
	
	n->next = NULL;// last element in the list
	n->data = addData;

	
	if (head != NULL) // last value always set to null 
		// if there is already an element in the list.
	{
		curr = head;
		while (curr->next != NULL)
		{
		
				curr = curr->next;
		}
		
		curr->next = n;
	}
	else // we do not have an element in the list
	{
		head = n;
	}
}

;

[Mantorr22]

void List::AddNode(int addData)
	
{
	// definition of the AddNode function
	nodePtr n = new node;
	
	n->next = NULL;// last element in the list
	n->data = addData;
	
	if (head == NULL) // last value always set to null 
		// if there is already an element in the list.
	{
		head = n;
	}
	else
	{
		nodePtr it = head;
		while (it->next != NULL)
		{
			it = it->next;
		}
		it->next = n;
	}
}

[techjohnny]

This is what worked for me too.

void List::AddOrdered(int ordData)

{
	bool found;
	nodePtr n = new node;
	n->data = ordData;
	n->next = NULL;

	if (head == NULL)
	{
		head = n;
		trail = n;
	}
	else
	{
		curr = head;
		found = false;

		while (curr != NULL && !found)
			if (curr->data >= ordData)
				found = true;
			else
			{
				trail = curr; 
				curr = curr->next;
			}
		if (curr == head)
		{
			n->next = head;
			head = n;

		}
		else
		{
			trail->next = n;
			n->next = curr;
			if (curr == NULL)
			
				last = n;
			
			
		}
	}
}

;

[Mantorr22]

This is what worked for me too.

It does not. If you really intend to make a SortedList class, remove List::AddNode() and only keep the List::AddOrdered() function. By the way List::AddOrdered() does not look like it does the job, whether the function is actually correct or not.

[dhayden]

Although it harder to understand, the code is much easier if you use a headOrNext pointer. This points to head, or the previous node's next pointer.

void List::AddOrdered(int data)
{
    nodePtr *headOrNext;		// points to head, or some node's next pointer
    nodePtr cur;			// current node we're looking at

    // point headOrNext at the nodePtr where the new node should go.
    for (headOrNext = &head; (cur = *headOrNext); headOrNext = &cur->next) {
	if (cur->data > data) break;
    }

    // headOrNext now points to the pointer to the next item.

    nodePtr n = new Node;
    n->data = data;
    n->next = *headOrNext;
    *headOrNext = n;

    if (cur == nullptr) {
	// Inserting at the end. Update tail
	tail = n;
    }
}