I am having trouble trying to implement my recursive method for inserting into a linked list. I made the recursive method private because it needs acces to the head pointer. Not sure where to go from here . Any help would be appreciated. Here is the code.
The .h file:
// *********************************************************
// Header file ListP.h for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include "ListIndexOutOfRangeException.h"
typedef int ListItemType;
class List
{
public:
// constructors and destructor:
List(); // default constructor
List(const List& aList); // copy constructor
~List(); // destructor
// list operations:
bool isEmpty() const;
int getLength() const;
void insert(int index, ListItemType newItem)
throw (ListIndexOutOfRangeException);
void remove(int index)
throw (ListIndexOutOfRangeException);
void retrieve(int index, ListItemType& dataItem) const
throw (ListIndexOutOfRangeException);
void insertRec(ListItemType newItem);
//void InsertFront(const ListItemType & newItem);
//void linkedListInsert(ListItemType newItem);
private:
struct ListNode // a node on the list
{
ListItemType item; // a data item on the list
ListNode *next; // pointer to next node
}; // end struct
int size; // number of items in list
ListNode *head; // pointer to linked list of items
ListNode *find(int index) const;
void linkedListInsert(ListNode *&head, ListItemType newItem);
//Returns a pointer to the index-th node
//in the linked list.
}; // end class
// End of header file.
the out of range .h file:
#include <stdexcept>
#include <string>
using namespace std;
class ListIndexOutOfRangeException: public out_of_range
{
public:
ListIndexOutOfRangeException(const string & message = "")
: out_of_range(message.c_str())
{ }
}; // end ListIndexOutOfRangeException
the .cpp file:
// *********************************************************
// Implementation file ListP.cpp for the ADT list.
// Pointer-based implementation.
// *********************************************************
#include <iostream>
using namespace std;
#include "RListP.h" // header file
#include <cstddef> // for NULL
#include <cassert> // for assert()
List::List(): size(0), head(NULL)
{
} // end default constructor
List::List(const List& aList): size(aList.size)
{
if (aList.head == NULL)
head = NULL; // original list is empty
else
{ // copy first node
head = new ListNode;
head->item = aList.head->item;
// copy rest of list
ListNode *newPtr = head; // new list pointer
// newPtr points to last node in new list
// origPtr points to nodes in original list
for (ListNode *origPtr = aList.head->next;
origPtr != NULL;
origPtr = origPtr->next)
{ newPtr->next = new ListNode;
newPtr = newPtr->next;
newPtr->item = origPtr->item;
} // end for
newPtr->next = NULL;
} // end if
} // end copy constructor
List::~List()
{
while (!isEmpty())
remove(1);
} // end destructor
bool List::isEmpty() const
{
return size == 0;
} // end isEmpty
int List::getLength() const
{
return size;
} // end getLength
List::ListNode *List::find(int index) const
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the
// desired node.
// Postcondition: Returns a pointer to the desired
// node. If index < 1 or index > the number of
// nodes in the list, returns NULL.
// --------------------------------------------------
{
if ( (index < 1) || (index > getLength()) )
return NULL;
else // count from the beginning of the list
{ ListNode *cur = head;
for (int skip = 1; skip < index; ++skip)
cur = cur->next;
return cur;
} // end if
} // end find
void List::retrieve(int index,
ListItemType& dataItem) const throw(ListIndexOutOfRangeException)
{
if ((index < 1) || (index > getLength()))
throw ListIndexOutOfRangeException(
"ListIndexOutOfRangeException: retrieve index out of range");
else
{ // get pointer to node, then data in node
ListNode *cur = find(index);
dataItem = cur->item;
cout<<dataItem<<endl;
} // end if
} // end retrieve
void List::insert(int index, ListItemType newItem) throw(ListIndexOutOfRangeException)
{
int newLength = getLength() + 1;
if ((index < 1) || (index > newLength))
throw ListIndexOutOfRangeException(
"ListIndexOutOfRangeException: insert index out of range");
else
{ // create new node and place newItem in it
ListNode *newPtr = new ListNode;
size = newLength;
newPtr->item = newItem;
// attach new node to list
if (index == 1)
{ // insert new node at beginning of list
newPtr->next = head;
head = newPtr;
}
else
{ ListNode *prev = find(index-1);
// insert new node after node
// to which prev points
newPtr->next = prev->next;
prev->next = newPtr;
} // end if
} // end if
} // end insert
void List::remove(int index) throw(ListIndexOutOfRangeException)
{
ListNode *cur;
if ((index < 1) || (index > getLength()))
throw ListIndexOutOfRangeException(
"ListIndexOutOfRangeException: remove index out of range");
else
{
--size;
if (index == 1)
{ // delete the first node from the list
cur = head; // save pointer to node
head = head->next;
}
else
{ ListNode *prev = find(index-1);
// delete the node after the
// node to which prev points
cur = prev->next; // save pointer to node
prev->next = cur->next;
} // end if
// return node to system
cur->next = NULL;
delete cur;
cur = NULL;
} // end if
} // end remove
void linkedListInsert(ListNode *&head, ListItemType newItem);
{
if ((head == NULL) || (newItem < head->item))
{ // base case: insert newItem at beginning
// of the linked list to which headPtr points
ListNode *newPtr = new ListNode;
newPtr->item = newItem;
newPtr->next = head;
head = newPtr;
}
else
linkedListInsert(newItem);
} // end linkedListInsert
int main()
{
List aList;
aList.linkedListInsert(5);
aList.linkedListInsert(4);
int a = 0;
//a = aList.getLength();
//cout<<a<<endl;
}
