link list insertByPosition

[Trekker182]

I'm new to link lists and have to write a few modified functions from the book to do additional things. I have to modify insert to insert by the 2nd number passed in and have it replace that position and move the number that was there up. It's inserting the number, but before the position specified. If I insert 80 and position 0, that works fine. If I insert 50 at position 20, greater then the actual length of the list, it inserts it at the end like I want. But when I try to insert 87 at position 2, it will insert the number at position 3. If I want to insert 99 in position 3, it will insert it in position 5.

Any help would be appreciated.

Thanks.

void NumberList::insertByPosition(double x, int pos)
{
        ListNode *newNode;             //create a new node
        ListNode *nodePtr;            // To traverse the list
        ListNode *previousNode = 0;  //the previous node
        int position = 0;
        
        //allocate a new node and store x there 
        newNode = new ListNode;
        newNode->value = x;
        
        //position nodePtr at the head of the list
        nodePtr = head;
        
        // Initialize previousNode to NULL.
        previousNode = 0;
        
        //skip all nodes wholse position is less then pos
        while (nodePtr !=0 && position < pos)
        {      
               previousNode = nodePtr;
               nodePtr = nodePtr->next;
               position++;   
        }
        
        if (pos == 0)
          {
	         head = newNode;
	         newNode->next = nodePtr;
           }
        
        else if (pos == position || pos > position)
        {
                previousNode->next = newNode;
                newNode->next = nodePtr;   
        }     
       
     
}

[skatamatic]

Hmmm perhaps you should be comparing to position - 1, since 0 is counted. While something may be in 3rd in the list, it would be counted as 2nd since position starts at 0. Position will always equal the pos due to the above loop. I think a simple else would suffice.

[Trekker182]

You mean wherever I have position referenced in the code above, put it as (position-1) or do something in the else to that effect?

Thanks.

[Lerner]

That might help.

But before making the change I think you need to try to express the problem more clearly.

Will the head node be considered position zero or position 1? For example, if list is 80->50 and you want 87 to be at position 2 do want the list to look like this:
80->50->87 //head node == 0 position
or this
80->87->50//head node == 1 position

[Trekker182]

The head node will be considered position 0.

Here's the code I updated, it fixed part of the problem. Right now if I do

mylist.insertByPosition(87, 3);
mylist.insertByPosition(99, 2);
mylist.insertByPosition(80, 0);
mylist.insertByPosition(55, 20);

I get

80
10
99
16
87
20
30
55

It's putting the 99 in the right place in position 2, but not 87.

Here's my updated code:

void NumberList::insertByPosition(double x, int pos)
{
    ListNode *newNode;             //create a new node
    ListNode *nodePtr;            // To traverse the list
    ListNode *previousNode = 0;  //the previous node
    int position = 1;
    
    //allocate a new node and store x there
    newNode = new ListNode;
    newNode->value = x;
    
    //position nodePtr at the head of the list
    nodePtr = head;
    
    // Initialize previousNode to NULL.
    previousNode = 0;

    if (pos <= 1)
    {
        head = newNode;
        newNode->next = nodePtr;
    }
    else
    {
        //skip all nodes whose position is less then pos
        while (nodePtr !=0 && position < pos)
        {
            previousNode = nodePtr;
            nodePtr = nodePtr->next;
            position++;
        }
        previousNode->next = newNode;
        newNode->next = nodePtr;
    }
}

[skatamatic]

I think the if(pos <= 1) should be if(pos < 1), since 0 is the head.

[Trekker182]

Thanks for the suggestion, I tried it and it's still sorting the same way with the 87 in position 4 instead of 3.

[skatamatic]

The position should still be -1, so in the while loop, use

while (nodePtr !=0 && position < pos - 1)

also, init position to 0, not 1

[Trekker182]

I tried that and 87 is still in position 4. I had to adapt the same code for characters and with these lines:

mylist.insertByPosition('L', 3);
  mylist.insertByPosition('M', 4);
  mylist.insertByPosition('N', 0);
  mylist.insertByPosition('K', 6);

And I get :

N
B
C
L
M
K
D
Z

Interesting K is in position 5 instead of 6, the opposite of that of number list where 87 is in position 4 instead of 3.

They are both exactly the same code except for the line

newNode->character = mychar

which lets it work with characters.

void CharList::insertByPosition(char mychar, int pos)
{
    ListNode *newNode;             //create a new node
    ListNode *nodePtr;            // To traverse the list
    ListNode *previousNode = 0;  //the previous node
    int position = 0;
    
    //allocate a new node and store x there
    newNode = new ListNode;
    newNode->character = mychar;
    
    //position nodePtr at the head of the list
    nodePtr = head;
    
    // Initialize previousNode to NULL.
    previousNode = 0;

    if (pos < 1)
    {
        head = newNode;
        newNode->next = nodePtr;
    }
    else
    {
        //skip all nodes whose position is less then pos
        while (nodePtr !=0 && position < pos - 1)
        {
            previousNode = nodePtr;
            nodePtr = nodePtr->next;
            position++;
        }
        previousNode->next = newNode;
        newNode->next = nodePtr;
    }
}

#endif

[skatamatic]

Arrg I'll compile it and see what I can find out for you :P. Post the whole code (or better yet attach a zip of the whole project)

[Trekker182]

Thanks, here are both the charlist and numlist and their .h files.

[skatamatic]

This seems to be working fine... I made a list of 5, 10, 20, 30, and then insertedbypostion @ 2, and got the list 5, 2, 10, 20 , 30. Isn't this what you want?

[Trekker182]

Yah but it's not doing it for the all of the inserts by position for the list.

I took out the rest of the inserts and just tried the one I was originally having problems with.

mylist.insertByPosition(87, 3);

and I got

10
16
87
20
30

Isn't 87 in position 2, not 3? 10 is in position 0.

[skatamatic]

Well it's up to you, really. Taking out the - 1 in the while loop will adjust it to what you want.

[skatamatic]

here's what i used to test it:

#include "NumberList.h"
#include<iostream>
using namespace std;

int main()
{
  NumberList mylist;
  cout<<"Adding 5..."<<endl;
  mylist.appendNode(5);
  cout<<"Adding 10..."<<endl;
  mylist.appendNode(10);
  cout<<"Adding 20..."<<endl;
  mylist.appendNode(20);
  cout<<"Adding 30..."<<endl;
  mylist.appendNode(30);
  cout<<"mylist:\n";
  mylist.displayList();
  mylist.insertByPosition(2, 0);
  mylist.insertByPosition(4, 2);
  cout <<"\nmylist with 2 inserted @ 0 and 4 @ 2\n";
  mylist.displayList();  

  //mylist2.displayList();

  cin.ignore(cin.rdbuf()->in_avail()).get();


  return 0;
}

[Trekker182]

Ok sorry for the cunfusion guys. For some reason I wasn't thinking after you do you more numbers, it throws the original position given off of course of the previous. I tried it with this

mylist.insertByPosition(80, 0);
  mylist.insertByPosition(55, 20);
  mylist.insertByPosition(87, 3);

and they are exactly where they should be. Thanks for your help everyone and patience!

:)