4 Replies - 932 Views - Last Post: 15 April 2012 - 05:16 AM Rate Topic: -----

#1 dekker13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 42
  • Joined: 12-September 11

Insert in linked list error?

Posted 14 April 2012 - 03:25 PM

I've spent some time trying to fix this small issue. My program runs fine, but I have one of those "off by one" errors. I'm trying to add an insert function that takes a data parameter and a parameter for what position in the linked list it should be placed. This code is textbook code and I'm trying to add functions to it.

Here's my attempt at this function. I know the issue comes somewhere in the 'for' loop. I've never done a linked list and I'm sure this would be a quick fix if I had more experience.
template< class NODETYPE >
void List< NODETYPE >::insertMiddle( const NODETYPE &value, int position )
{
    ListNode< NODETYPE > *newPtr = getNewNode( value );
    ListNode< NODETYPE > *curr = firstPtr;

    if ( isEmpty() )
        firstPtr = lastPtr = newPtr;

    else {
        if (position == 1)
            insertAtFront( value );
        else
            for (int i = 1; i < position; i++) {
                curr = curr->nextPtr;
            newPtr->nextPtr = curr->nextPtr;
            //curr->nextPtr = newPtr;
            curr->nextPtr = newPtr;
        }
    }
}

Posted Image
list.h
// Fig. 21.4: list.h
// Template List class definition.
#ifndef LIST_H
#define LIST_H

#include <iostream>

using std::cout;

#include <new>
#include "listnode.h"  // ListNode class definition

template< class NODETYPE >
class List {

public:
   List();      // constructor
   ~List();     // destructor
   void insertAtFront( const NODETYPE & );
   void insertAtBack( const NODETYPE & );
   void insertMiddle( const NODETYPE &, int);
   bool removeFromFront( NODETYPE & );
   bool removeFromBack( NODETYPE & );
   bool removeMiddle( NODETYPE &, int );
   bool isEmpty() const;
   void print() const;

private:
   ListNode< NODETYPE > *firstPtr;  // pointer to first node
   ListNode< NODETYPE > *lastPtr;   // pointer to last node

   // utility function to allocate new node
   ListNode< NODETYPE > *getNewNode( const NODETYPE & );

}; // end class List

// default constructor
template< class NODETYPE >
List< NODETYPE >::List() 
   : firstPtr( 0 ), 
     lastPtr( 0 ) 
{ 
   // empty body

} // end List constructor

// destructor
template< class NODETYPE >
List< NODETYPE >::~List()
{
   if ( !isEmpty() ) {    // List is not empty
//      cout << "Destroying nodes ...\n";

      ListNode< NODETYPE > *currentPtr = firstPtr;
      ListNode< NODETYPE > *tempPtr;

      while ( currentPtr != 0 )         // delete remaining nodes
      {  
         tempPtr = currentPtr;

// commented out the output -- no need to print what we are deallocating
//         cout << tempPtr->data << '\n';  

         currentPtr = currentPtr->nextPtr;
         delete tempPtr;

      }

   }

//   cout << "All nodes destroyed\n\n";

} // end List destructor

// insert node at front of list
template< class NODETYPE >
void List< NODETYPE >::insertAtFront( const NODETYPE &value )
{
   ListNode< NODETYPE > *newPtr = getNewNode( value );

   if ( isEmpty() )  // List is empty
      firstPtr = lastPtr = newPtr;

   else {  // List is not empty
      newPtr->nextPtr = firstPtr;
      firstPtr = newPtr;

   } // end else

} // end function insertAtFront

// insert node at back of list
template< class NODETYPE >
void List< NODETYPE >::insertAtBack( const NODETYPE &value )
{
   ListNode< NODETYPE > *newPtr = getNewNode( value );

   if ( isEmpty() )  // List is empty
      firstPtr = lastPtr = newPtr;

   else {  // List is not empty
      lastPtr->nextPtr = newPtr;
      lastPtr = newPtr;

   } // end else

} // end function insertAtBack

template< class NODETYPE >
void List< NODETYPE >::insertMiddle( const NODETYPE &value, int position )
{
    ListNode< NODETYPE > *newPtr = getNewNode( value );
    ListNode< NODETYPE > *curr = firstPtr;

    if ( isEmpty() )
        firstPtr = lastPtr = newPtr;

    else {
        if (position == 1)
            insertAtFront( value );
        else
            for (int i = 1; i < position; i++) {
                curr = curr->nextPtr;
            newPtr->nextPtr = curr->nextPtr;
            //curr->nextPtr = newPtr;
            curr->nextPtr = newPtr;
        }
    }
}

// delete node from front of list
template< class NODETYPE >
bool List< NODETYPE >::removeFromFront( NODETYPE &value )
{
   if ( isEmpty() )  // List is empty
      return false;  // delete unsuccessful

   else {  
      ListNode< NODETYPE > *tempPtr = firstPtr;

      if ( firstPtr == lastPtr )
         firstPtr = lastPtr = 0;
      else
         firstPtr = firstPtr->nextPtr;

      value = tempPtr->data;  // data being removed
      delete tempPtr;

      return true;  // delete successful

   } // end else

} // end function removeFromFront

// delete node from back of list
template< class NODETYPE >
bool List< NODETYPE >::removeFromBack( NODETYPE &value )
{
   if ( isEmpty() )
      return false;  // delete unsuccessful

   else {
      ListNode< NODETYPE > *tempPtr = lastPtr;

      if ( firstPtr == lastPtr )
         firstPtr = lastPtr = 0;
      else {
         ListNode< NODETYPE > *currentPtr = firstPtr;

         // locate second-to-last element
         while ( currentPtr->nextPtr != lastPtr )
            currentPtr = currentPtr->nextPtr;

         lastPtr = currentPtr;
         currentPtr->nextPtr = 0;

      } // end else

      value = tempPtr->data;
      delete tempPtr;

      return true;  // delete successful

   } // end else

} // end function removeFromBack

template<class NODETYPE >
bool List< NODETYPE >::removeMiddle( NODETYPE &value, int position )
{





}

// is List empty?
template< class NODETYPE > 
bool List< NODETYPE >::isEmpty() const 
{ 
   return firstPtr == 0; 
   
} // end function isEmpty

// return pointer to newly allocated node
template< class NODETYPE >
ListNode< NODETYPE > *List< NODETYPE >::getNewNode( 
   const NODETYPE &value )
{
   return new ListNode< NODETYPE >( value );

} // end function getNewNode

// display contents of List
template< class NODETYPE >
void List< NODETYPE >::print() const
{
   if ( isEmpty() ) {
      cout << "The list is empty\n\n";
      return;

   } // end if

   ListNode< NODETYPE > *currentPtr = firstPtr;

   cout << "The list is: ";

   while ( currentPtr != 0 ) {
      cout << currentPtr->data << ' ';
      currentPtr = currentPtr->nextPtr;

   } // end while

   cout << "\n\n";

} // end function print

#endif


listnode.h
// Fig. 21.3: listnode.h
// Template ListNode class definition.
#ifndef LISTNODE_H
#define LISTNODE_H

// forward declaration of class List 
template< class NODETYPE > class List;  

template< class NODETYPE >
class ListNode {
   friend class List< NODETYPE >; // make List a friend

public:
   ListNode( const NODETYPE & );  // constructor
   NODETYPE getData() const;      // return data in node

private:
   NODETYPE data;                 // data
   ListNode< NODETYPE > *nextPtr; // next node in list

}; // end class ListNode

// constructor
template< class NODETYPE >
ListNode< NODETYPE >::ListNode( const NODETYPE &info )
   : data( info ), 
     nextPtr( 0 ) 
{ 
   // empty body

} // end ListNode constructor

// return copy of data in node
template< class NODETYPE >
NODETYPE ListNode< NODETYPE >::getData() const 
{ 
   return data; 
   
} // end function getData

#endif


main.cpp
// Test program for HW 8
//

#include <iostream>

using std::cin;
using std::endl;

#include <string>

using std::string;

#include "list.h"  // List class definition

void instructions();

// function to test a List
template< class T >
void testList( List< T > &listObject, const string &typeName )
{
   cout << "Testing a List of " << typeName << " values\n";

   instructions();  // display instructions

   int choice;
   T value;
   int pos;

   do {
      cout << "? ";
      cin >> choice;

      switch ( choice ) {
         case 1:
            cout << "Enter " << typeName << ": ";
            cin >> value;
            listObject.insertAtFront( value );
            listObject.print();
            break;

         case 2:
            cout << "Enter " << typeName << ": ";
            cin >> value;
            listObject.insertAtBack( value );
            listObject.print();
            break;

         case 3:
            cout << "Enter " << typeName << ": ";
            cin >> value;
	    cout << "Enter position to insert: ";
	    cin >> pos;
            listObject.insertMiddle( value , pos );
            listObject.print();
            break;

         case 4:
            if ( listObject.removeFromFront( value ) )
               cout << value << " removed from list\n";

            listObject.print();
            break;

         case 5:
            if ( listObject.removeFromBack( value ) )
               cout << value << " removed from list\n";

            listObject.print();
            break;

         case 6:
	    cout << "Enter position to delete: ";
	    cin >> pos;
            if ( listObject.removeMiddle( value, pos ) )
               cout << value << " removed from list\n";

            listObject.print();
            break;

      } // end switch

   } while ( choice != 7 );  // end do/while

   cout << "End list test\n\n";

} // end function testList

// display program instructions to user
void instructions()
{
   cout << "Enter one of the following:\n"
        << "  1 to insert at beginning of list\n" 
        << "  2 to insert at end of list\n" 
	<< "  3 to insert at anywhere in the list\n"
        << "  4 to delete from beginning of list\n" 
        << "  5 to delete from end of list\n" 
	<< "  6 to delete from anywhere in the list\n"
        << "  7 to end list processing\n";

} // end function instructions

int main()
{
   // test List of int values
   List< int > integerList;
   testList( integerList, "integer" ); 

   // test List of double values
   List< double > doubleList;
   testList( doubleList, "double" ); 

   return 0;

} // end main



Is This A Good Question/Topic? 0
  • +

Replies To: Insert in linked list error?

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 5951
  • View blog
  • Posts: 23,210
  • Joined: 23-August 08

Re: Insert in linked list error?

Posted 14 April 2012 - 04:12 PM

I would suggest this is a good time to get to know your debugger! Compile in debug mode, set a breakpoint in your insertMiddle method, and step through the code line by line to diagnose the problem.
Was This Post Helpful? 0
  • +
  • -

#3 dekker13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 42
  • Joined: 12-September 11

Re: Insert in linked list error?

Posted 14 April 2012 - 04:20 PM

View PostJackOfAllTrades, on 14 April 2012 - 04:12 PM, said:

I would suggest this is a good time to get to know your debugger! Compile in debug mode, set a breakpoint in your insertMiddle method, and step through the code line by line to diagnose the problem.


Are there any good tutorial websites for 'gdb'? I use a text editor and compile with g++ on my Mac. I found some in Google, but they aren't clear enough.
Was This Post Helpful? 0
  • +
  • -

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 5951
  • View blog
  • Posts: 23,210
  • Joined: 23-August 08

Re: Insert in linked list error?

Posted 15 April 2012 - 03:08 AM

Sigh...you can't get much clearer than the tutorials out there.

Open a Terminal window.
Navigate to the directory with your code.
Compile your code in debug mode and full warnings with g++ -ggdb3 -Wall -pedantic <cpp files> -o <output executable>.

Start gdb with your program
gdb ./progname

Set a breakpoint on your function (not sure how to do this with a template -- I'm mainly a C programmer -- so we'll set it on the first line of the function)
gdb> break list.h:112

Run the program
gdb> run

When the program stops, use step to step to the next line, and print <varname> to print the contents of a variable.

Note the step and print functions will accept just the first letter as well, like s and p <varname>.

Typing help at the gdb> prompt will, naturally, give you help.
Was This Post Helpful? 1
  • +
  • -

#5 dekker13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 42
  • Joined: 12-September 11

Re: Insert in linked list error?

Posted 15 April 2012 - 05:16 AM

View PostJackOfAllTrades, on 15 April 2012 - 03:08 AM, said:

Sigh...you can't get much clearer than the tutorials out there.

Open a Terminal window.
Navigate to the directory with your code.
Compile your code in debug mode and full warnings with g++ -ggdb3 -Wall -pedantic <cpp files> -o <output executable>.

Start gdb with your program
gdb ./progname

Set a breakpoint on your function (not sure how to do this with a template -- I'm mainly a C programmer -- so we'll set it on the first line of the function)
gdb> break list.h:112

Run the program
gdb> run

When the program stops, use step to step to the next line, and print <varname> to print the contents of a variable.

Note the step and print functions will accept just the first letter as well, like s and p <varname>.

Typing help at the gdb> prompt will, naturally, give you help.


Thanks! I still don't understand what exactly to do in gdb. I tried the 'step' command and got infinite output for a call that was working in the first place. I'm better off working it on paper. I appreciate your time in writing the tutorial. :balloon:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1