Insertion into Linked Lists

[chaseshaw275]

I'm trying to use insertion into a linked list by position.
i.e.

numbers.insertByPosition(0.5, 0);

that's my function call and the first parameter is the value to be inserted and the second parameter is where in the list the first value will be inserted.

So like, if position equals 0, then the 0.5 will be inserted into the front of the list. If position equals 1, then 0.5 will be inserted into the second position of the list, etc. etc.

I have most of the code for the insert function...

insertByPosition(double value, int pos)
{
Listnode *newNode;
ListNode *nodePtr;
ListNode *previousNode = NULL;

newNode = new ListNode;
newNode -> value = value;

if (head != NULL)
{
head = newNode;
newNode -> next = NULL;
}
else
{
nodePtr = head;
previousNode = NULL;

while (nodePtr != NULL && nodePtr -> value < value)
{
previousNode = nodePtr;
nodePtr = nodePtr -> next;
}

if (previousNode == NULL)
{
head = newNode;
newNode -> next = nodePtr;
}
else
{
previousNode -> next = newNode;
newNode -> next = nodePtr;
}
}
}



The only thing that is giving me problems is how to insert each value into a certain position.

Thanks for you help.

[Duthomhas]

You do know you aren't supposed to be able to insert into a stack. ;-)

What you really need to do is get out a piece of blank paper and a pencil and draw some little boxes and arrows, then draw how to move them around to add a new box.

Good luck!

[seymore15074]

Duoas, there is nothing better than penciling it all out first...I can't stress my agreement enough. My whiteboard and I are very close!

[Gumbercules]

notice that

while (nodePtr != NULL && nodePtr -> value < value)

is comparing the values.

insertByPosition(double value, int pos)
{
	Listnode *newNode;
	ListNode *nodePtr;
	ListNode *previousNode = NULL;
	newNode = new ListNode;
	newNode -> value = value;
	nodePtr = head;
	previousNode = NULL;
	for(int i = 0; i < pos; ++i) { // iterate to the two nodes you want to insert between
		previousNode = nodePtr;
		nodePtr = nodePtr->next;
	}
	if (previousNode) { // if there is a previous node
		previousNode->next = newNode; // point the next of the node before to the new node
		newNode->next = nodePtr; // point the new node to the next node
	} else { // there is no previous node, nodePtr must be at head
		head = newNode; // point head to new node
		newNode->next = nodePtr; // point next to the old first
	}

}