C++ Data Structures List addToPosistion

[karmstrong]

I am having and issue getting my add to list function to work in my data structure list class. I have all functions working except addToPostion. addToHead, addToTail, deleteFromhead, deleteFromTail, and DeleteFromPosistion all work as expected. I'm confused on the addToPosistion. The entire .cpp file is posted. Any and all help would be greatly appreciated along with any ideas on improving the overall code.

Problem Area

//*****************************************************************
// METHOD: addByPosistion
// PURPOSE: Adds a Node to some posistion in the list
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::addByPosition(int index, Salesmen *pItem)
{
	if (index < 0)
    {
        return;  // Invalid index
    }

    // Empty List
    if (pHead == 0)
    {
		return;
    }

    // List is size of 1
    if (pHead == pTail) 
    {
        if (index !=0)
        {
            return;
        }
        // addToHead(Salesmen *pItem);
        return;
    }

    // Multiple Items in List
    if (index == 0)
    {
		pHead = pTail = pItem;
        return;
    } 

    Salesmen *pTemp = pHead;
    int tempIndex = 0;

    Salesmen *pPrev = pHead;

    while (pTemp != NULL)
    {
        if (tempIndex == index)
        {
            // Add Item to List
            pPrev->setNext(pTemp->getNext());
            
            if (pTemp == pTail)
            {
                pTail = pPrev;
            }

            delete pTemp;
            count--;

            return;
        }

        pPrev = pTemp;
        tempIndex++;
        pTemp = pTemp->getNext();
    }
}

The rest of the .cpp File

//=================================================================
#include "SalesmenList.h"
#include "Salesmen.h"
#include <iostream>
//=================================================================


//*****************************************************************
// METHOD  Constructor
// PURPOSE:  Constructor
// PARAMETERS: pHead, pTail list_size
//*****************************************************************
SalesmenList::SalesmenList()
	{
		pHead = pTail = 0;
        count = 0;
	}


//*****************************************************************
// METHOD: Destructor
// PURPOSE: Destructor
// PARAMETERS: N/A
//*****************************************************************
SalesmenList::~SalesmenList()
{
    Salesmen *p = pHead;
	while ( p != NULL )
	{
        p = p->getNext();
		delete p;
	}
    count = 0;
}

//*****************************************************************
// METHOD: IsInList 
// PURPOSE: Check if List is free
// PARAMETERS: N/A
//*****************************************************************
bool SalesmenList::isInList(Salesmen *pItem) const
{
	Salesmen *pTemp;

    pTemp = pHead;
    while ( pTemp != NULL )
    {
        if ( pTemp->getName() == pItem->getName() )
        {
            break;
        }
        pTemp = pTemp->getNext();
    }
	return pTemp !=0;
}



//*****************************************************************
// METHOD: deleteFromHead
// PURPOSE: Inserts Salesmen at the front of the list
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::deleteFromHead()
{
	Salesmen *pTemp = pHead;
	
	if (pHead == pTail)
    {
		pHead = pTail = 0;
        count = 0;
    }
	else
    {
		pHead = pHead->getNext();
        count--;
    }
	
	delete pTemp;
}


//*****************************************************************
// METHOD: deleteByPosition
// PURPOSE: Remove Salesmen Object
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::deleteByPosition(int index)
{
	if (index < 0)
    {
        return;  // Invalid index
    }

    // Empty List
    if (pHead == 0)
    {
        return;
    }

    // List is size of 1
    if (pHead == pTail) 
    {
        if (index !=0)
        {
            return;
        }
        delete pHead;
        pHead = NULL;
        pTail = NULL;
        count = 0;
        return;
    }

    // Multiple Items in List
    if (index == 0)
    {
        deleteFromHead();
        return;
    }

    Salesmen *pTemp = pHead;
    int tempIndex = 0;

    Salesmen *pPrev = pHead;

    while (pTemp != NULL)
    {
        if (tempIndex == index)
        {
            // Delete item and readjust Next Pointer
            pPrev->setNext(pTemp->getNext());
            
            if (pTemp == pTail)
            {
                pTail = pPrev;
            }

            delete pTemp;
            count--;

            return;
        }

        pPrev = pTemp;
        tempIndex++;
        pTemp = pTemp->getNext();
    }
}

//*****************************************************************
// METHOD: deleteFromTail
// PURPOSE: Deletes Salesmen at the tail of the list
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::deleteFromTail()
{
	Salesmen *pTemp = pHead;

    if (pTemp == NULL)
    {
        // Empty List
        return;
    }

    if (pHead == pTail)
    {
        // Single item in List
        delete pTail;
        pHead = NULL;
        pTail = NULL;
        count = 0;
        return;
    }

    // Multiple Items in List

    Salesmen *pPrev = NULL;

    while (pTemp != pTail)
    {
        pPrev = pTemp;
        pTemp = pTemp->getNext();
    }
    delete pTemp;
    pTail = pPrev;
    pTail->setNext(NULL);
    count--;
 }

//*****************************************************************
// METHOD: addToHead
// PURPOSE: Inserts Salesmen at the front of the list
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::addToHead(Salesmen *pItem)
{
	Salesmen *pTemp = pHead;
    pHead = pItem;
    pItem->setNext(pTemp);
    count++;
}

//*****************************************************************
// METHOD: addByPosistion
// PURPOSE: Adds a Node to some posistion in the list
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::addByPosition(int index, Salesmen *pItem)
{
	if (index < 0)
    {
        return;  // Invalid index
    }

    // Empty List
    if (pHead == 0)
    {
		return;
    }

    // List is size of 1
    if (pHead == pTail) 
    {
        if (index !=0)
        {
            return;
        }
        // addToHead(Salesmen *pItem);
        return;
    }

    // Multiple Items in List
    if (index == 0)
    {
		pHead = pTail = pItem;
        return;
    } 

    Salesmen *pTemp = pHead;
    int tempIndex = 0;

    Salesmen *pPrev = pHead;

    while (pTemp != NULL)
    {
        if (tempIndex == index)
        {
            // Add Item to List
            pPrev->setNext(pTemp->getNext());
            
            if (pTemp == pTail)
            {
                pTail = pPrev;
            }

            delete pTemp;
            count--;

            return;
        }

        pPrev = pTemp;
        tempIndex++;
        pTemp = pTemp->getNext();
    }
}


//*****************************************************************
// METHOD: addToTail
// PURPOSE: Inserts salesmen at the end of the list
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::addToTail(Salesmen *pItem)
{
	if (pTail != 0)
	{
        pTail->setNext(pItem);
		pTail = pItem;
	}
	else
    {
		pHead = pTail = pItem;
    }
    count++;
}




#if 0
//*****************************************************************
// METHOD: isEmpty
// PURPOSE: Inserts salesmen at the end of the list
// PARAMETERS: N/A
//*****************************************************************
int SalesmenList::isEmpty()
{
	return pHead == 0;
}
#endif

//*****************************************************************
// METHOD: print
// PURPOSE: prints the current list of salesmen
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::print()
{
    cout << "Debug: count = " << count << endl;
    Salesmen *pCurr = pHead;
    while ( pCurr != NULL )
    {
        pCurr->PrintToStream(cout);
        pCurr = pCurr->getNext();
    }
}

[Zvjezdan23]

What is your program basically supposed to do????

[Zvjezdan23]

Also, you can use a vector for a lot of this. Or even arrays.

[Zvjezdan23]

void SalesmenList::deleteFromHead()
{
Salesmen *pTemp = pHead;

if (pHead == pTail)
{
pHead = pTail = 0;
count = 0;
}

have pHead = 0;
pTail = 0;
count = 0;

[karmstrong]

We are not allowed to use the vector class or dynamic arrays. It must be a list class. The only one I am having issues with is addToPosition. Basically one should give a position being the index and the node should be added to that location. Unless of course that position does not exist. At which time it should add it to either pHead or pTail

[Kanoisa]

Ok this isnt exactly what you want but i think you may be stepping to far to fast.

What i find helps this kind of problem is to draw on paper 4 boxes in a row, make them your pretend elements.

Then draw your class as a box at the top or bottom and write in your pointers.

Draw all of these in pen then get a pencil. Start with your constructor and draw what the code is doing, (draw the links of what pointer points to whom) and check the code makes sence logically.

Do the same with a destructor and add routines. I can see what im sure is a memory leak in your destructor.

I would like to give you code and show you where i think mistakes are but i found this same problem occours time after time so being able to work this one out on your own is key to progressing and understanding object/ pointer manipulation.

Best of luck.

[karmstrong]

Ok this isnt exactly what you want but i think you may be stepping to far to fast.

What i find helps this kind of problem is to draw on paper 4 boxes in a row, make them your pretend elements.

Then draw your class as a box at the top or bottom and write in your pointers.

Draw all of these in pen then get a pencil. Start with your constructor and draw what the code is doing, (draw the links of what pointer points to whom) and check the code makes sence logically.

Do the same with a destructor and add routines. I can see what im sure is a memory leak in your destructor.

I would like to give you code and show you where i think mistakes are but i found this same problem occours time after time so being able to work this one out on your own is key to progressing and understanding object/ pointer manipulation.

Best of luck.

Thanks and agreed I'm not necessary looking for exact answer but guidance. Like I said I have all functions working except addToPosistion. having a tough time figuring out the logic. I have boxes drawn now and am getting there. as far as memory link in the destructor. is it because it is not virtual?

[Kanoisa]

No look again with the boxes and see what happens to your pointers, the contents of the while loop you will want to look at closely.

If the code works currently its a case of luck, the delete call should have interesting implications.

For the destructor in this kind of problem i use two pointers.

Hope these clues get you to the realisation of what is happening there.

And im glad to see you making progress its a very good feeling when you figure out a tough problem :)

[karmstrong]

Ok Almost there

//*****************************************************************
// METHOD: addByPosistion
// PURPOSE: Adds a Node to some posistion in the list
// PARAMETERS: N/A
//*****************************************************************
void SalesmenList::addByPosition(int index, Salesmen *pItem)
{
    if (index < 0)
    {
        return;  // Invalid index
    }

    // Empty List
    if (pHead == 0)
    {
        if (index == 0)
        {
        addToHead(pItem);
        } 
        return;
    }

    // List is size of 1
    if (pHead == pTail) 
    {
        if (index == 0)
        {
            addToHead(pItem);
        }

        if (index == 1)
        {
            addToTail(pItem);
        }
        return;
    }

    // Multiple Items in List

    if (index == 0)
    {
        addToHead(pItem);
        return;
    }

    if (index == getCount()-1)
    {
        addToTail(pItem);
        return;
    }

    if (index > 0 && index < getCount() -1)
    {
        index->getNext(pItem);
        count++;
    }
}

The issue is this line

index->getNext(pItem);

My thought is this. I know the index I wish to put the item in. So I take the item and the index number and pass it to the getNext() function

The problem is index is an int.

[Kanoisa]

Im not entirely sure how you are using index? it is the position in the llist you want the item to be placed?

if thats the case then what you can do is after your checks for 0 or 1 item is to do a counter to find the item you need to insert after and insert the new item

SalesMan* pFound = pHead;
/* seek the item we wish to insert after */
for( int n = 0; n < index; n++ )
{
  if( NULL == pFound )
  {
    /* ran out of space :( boo 
     * this index is out of range
     */
     break; /* stop the loop or we will seg fault by dereferncing NULL pointer*/
  } 
  pFound = pFound->next;
}

if( NULL != pFound )
{
   /* item found insert here */
}
else
{
   /* out of range, reset pFound to head and loop untill 
    * pFound->next == NULL then pFound is the end of the list
    * and add the item here, assuming the out of range 
    * index is not an error 
    */
}

[karmstrong]

So your saying this. i think

/*if (index > 0 && index < getCount() -1)
	{
		pItem->getNext(index);
		count++;
    } */
	Salesmen pTemp = *pItem;
	for (int n = 0; n < index; n++)
	{
		pItem->getNext();
	}
}

It compiles however addToPoisstion does not work. I think its because the getNext() function is pointing to the pItem but it don't know where to put it?

Sorry I'm just not getting this

Current Output
Test 1: Adding 4 Nodes to list
Debug: count = 4
name=" Mike Cohen" id=301 sales= 2128.04 gender=Male
name=" Paul Thor" id=310 sales= 1387.02 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female
name=" Hanna Barnes" id=600 sales= 287.08 gender=Female

Test 2: Deleting 2 Nodes from head
Debug: count = 2
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female
name=" Hanna Barnes" id=600 sales= 287.08 gender=Female

Test 3: Adding 2 Nodes to Head
Debug: count = 4
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Dana" id=500 sales= 1287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female
name=" Hanna Barnes" id=600 sales= 287.08 gender=Female

Test 4: Deleting 1 node from tail
Debug: count = 3
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Dana" id=500 sales= 1287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female

Test 5: Delete 1 Node from middle
Debug: count = 2
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female

Test 6: Add 1 Node to the middle of list
Debug: count = 2
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female

[karmstrong]

So your saying this. i think

/*if (index > 0 && index < getCount() -1)
	{
		pItem->getNext(index);
		count++;
    } */
	Salesmen pTemp = *pItem;
	for (int n = 0; n < index; n++)
	{
		pItem->getNext();
	}
}

It compiles however addToPoisstion does not work. I think its because the getNext() function is pointing to the pItem but it don't know where to put it?

Sorry I'm just not getting this

Current Output
Test 1: Adding 4 Nodes to list
Debug: count = 4
name=" Mike Cohen" id=301 sales= 2128.04 gender=Male
name=" Paul Thor" id=310 sales= 1387.02 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female
name=" Hanna Barnes" id=600 sales= 287.08 gender=Female

Test 2: Deleting 2 Nodes from head
Debug: count = 2
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female
name=" Hanna Barnes" id=600 sales= 287.08 gender=Female

Test 3: Adding 2 Nodes to Head
Debug: count = 4
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Dana" id=500 sales= 1287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female
name=" Hanna Barnes" id=600 sales= 287.08 gender=Female

Test 4: Deleting 1 node from tail
Debug: count = 3
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Dana" id=500 sales= 1287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female

Test 5: Delete 1 Node from middle
Debug: count = 2
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female

Test 6: Add 1 Node to the middle of list
Debug: count = 2
name=" Jet Lee" id=600 sales= 287.08 gender=Male
name=" Erica Barnes" id=500 sales= 1287.08 gender=Female

[Kanoisa]

Your not moving the pointer by doing that.

Do you have a debugger for this? its the kind of thing if you stepped through the code you would see what is happening there.

If you still have the page with the boxes doodles on it, this add element to the middle is the perfect use for it. look at your list on paper, and try to work out what the code is doing.

What can also work is to in a similar fashon draw out 2 elements connected to each other and one below them and in the middle of them (so make joining arrow pretty long) and ask yourself, how do i change this to look like 3 nodes in a line? once you solve it on paper you should see the issues with the code. I always find, nothing helps solve a logical coding problem than a picture or timing diagram or whatever suits the problem.

[karmstrong]

I got this figured out. Thanks for your help. I will now go back and look at my delete operations and look for memory leak issues that where mentioned in the above post. Its nice to have something that is at least for the time being complileing and producing expected results. Now time to clean up the code a bit.

Thanks to you all.