I would like to know how to modify insert in the implementation file so that the previous and next items in the list are stored correctly.
Issue is at line 134. In the insert function.
Below is the implementation file.
#include "ListP.h" // header file
#include <stddef.h> // for NULL
#include <assert.h> // for assert()
#include <iostream>
usingnamespace std;
List::List(): size(0), head(NULL)
{
} // end default constructor
List::List(const List & L): size(L.size)
{
if (L.head == NULL)
head = NULL; // original list is empty
else
{ // copy first node
head = new ListNode;
assert(head != NULL); // check allocation
head->item = L.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 = L.head->next;OrigPtr != NULL;OrigPtr = OrigPtr->next)
{ NewPtr->next = new ListNode;
assert(NewPtr->next != NULL);
NewPtr = NewPtr->next;
NewPtr->item = OrigPtr->item;
} // end for
NewPtr->next = NULL;
} // end if
} // end copy constructor
List::~List()
{
bool Success;
while (! isEmpty())
remove(1, Success);
} // end destructor
bool List::isEmpty() const
{
returnbool(size == 0);
} // end ListIsEmpty
int List::getLength() const
{
return size;
} // end ListLength
List::ListNode * List::find(int Position) const
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: Position is the number of the
// desired node.
// Postcondition: Returns a pointer to the desired
// node. If Position < 1 or Position > the number of
// nodes in the list, returns NULL.
// --------------------------------------------------
{
if ( (Position < 1) || (Position > getLength()) )
return NULL;
else // count from the beginning of the list
{ ListNode * Cur = head;
for (int Skip = 1; Skip < Position; ++Skip)
Cur = Cur->next;
return Cur;
} // end if
} // end find
void List::retrieve(int Position,ListItemType & Dataitem, bool & Success) const
{
ListNode * Cur;
Success = bool( (Position >= 1) && (Position <= getLength()) );
if (Success)
{ // get pointer to node, then data in node
Cur = find(Position);
Dataitem = Cur->item;
if(Cur->previous != NULL)
{
cout<<"Previous cell is "<<Cur->previous->item<<endl;
}
else
{
cout<<"Previous cell is empty!"<<endl;
}
if(Cur->next != NULL)
{
cout<<"Next cell is "<<Cur->next->item<<endl;
}
else
{
cout<<"Next cell is empty!"<<endl;
}
} // end if
} // end retrieve
void List::insert(int NewPosition,ListItemType Newitem, bool & Success)
{
ListNode * Prev;
ListNode * NewPtr;
int NewLength = getLength() + 1;
Success = bool( (NewPosition >= 1) && (NewPosition <= NewLength) );
if (Success)
{ // create new node and place Newitem in it
NewPtr = new ListNode;
Success = bool(NewPtr != NULL);
if (Success)
{ size = NewLength;
NewPtr->item = Newitem;
// attach new node to list
if (NewPosition == 1)
{ // insert new node at beginning of list
NewPtr->next = head;
head = NewPtr;
if(NewPtr-> next != NULL)
{
//This is where I am having trouble getting the program to work.
NewPtr->next->Prev=NewPtr->next;
}
}
else
{ Prev = find(NewPosition-1);
// insert new node after node
// to which Prev points
NewPtr->next = Prev->next;
Prev->next = NewPtr;
} // end if
} // end if
} // end if
} // end insert
void List::remove(int Position, bool & Success)
{
ListNode * Cur;
ListNode * Prev;
Success = bool( (Position >= 1) && (Position <= getLength()) );
if (Success)
{ --size;
if (Position == 1)
{ // delete the first node from the list
Cur = head; // save pointer to node
head = head->next;
}
else
{ Prev = find(Position-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
typedefchar ListItemType;
class List
{
public:
List(); // default constructor
List(const List & L); //copy Constructor
~List(); //Destructor
// list operations:
bool isEmpty() const;
// Determines whether a list is empty.
// Precondition: None.
// Postcondition: Returns true if the list is empty;
// otherwise returns false.
int getLength() const;
// Determines the length of a list.
// Precondition: None.
// Postcondition: Returns the number of items
// that are currently in the list.
void insert(int index, ListItemType newItem,bool & success);
// Inserts an item into the list at position index.
// Precondition: index indicates the position at which
// the item should be inserted in the list.
// Postcondition: If insertion is successful, newItem is
// at position index in the list, and other items are
// renumbered accordingly, and success is true;
// otherwise success is false.
// Note: Insertion will not be successful if
// index < 1 or index > getLength()+1.
void remove(int index, bool & success);
// Deletes an item from the list at a given position.
// Precondition: index indicates where the deletion
// should occur.
// Postcondition: If 1 <= index <= getLength(),
// the item at position index in the list is
// deleted, other items are renumbered accordingly,
// and success is true; otherwise success is false.
void retrieve(int index, ListItemType & dataItem,bool & success) const;
// Retrieves a list item by position.
// Precondition: index is the number of the item to
// be retrieved.
// Postcondition: If 1 <= index <= getLength(),
// dataItem is the value of the desired item and
// success is true; otherwise success is false.
private:
struct ListNode // a node on the list
{
ListItemType item; // a data item on the list
ListNode *next; // pointer to next node
ListNode *previous; //previous
}; // end struct
int size; // number of items in list
ListNode *head; // pointer to linked list of items
ListNode *find(int index) const;
// Returns a pointer to the index-th node
// in the linked list.
}; // end List class
// End of header file.
I get a headache looking at all those variables-named-as-if-they-were-classes, so this is how I'd do it if I were writing it (with changes to style and naming conventions to assuage my headache.)
void List::insert(int pos, ListItemType item, bool & success)
{
success = false;
if (pos < 1 || pos > size + 1) return;
ListNode* node = new ListNode{ item, nullptr, nullptr };
success = true;
if (++size == 1)
head = node;
else {
ListNode * prev = head;
for (std::size_t i = 0; i < pos; ++i)
prev = prev->next;
node->previous = prev;
node->next = prev->next;
prev->next = node;
if ( node->next ) node->next->previous = node;
}
}
caveat: untested code
Are you wedded to the idea of taking the "success" indicator by reference? It would be more usual to return the value. Note that you've named the pointer representing the previous node as previous in the ListNode type, and not Prev as you're trying to use currently in insert.
yes, i am going to stick with this indicator for this reference. I would like to get this program running first and of course then i would try other ways to make it work, especially if it is better. thanks for the input. I am working to place it in my code now.
void List::insert(int NewPosition,ListItemType Newitem, bool & Success)
{
ListNode * Prev;
ListNode * NewPtr;
int NewLength = getLength() + 1;
Success = bool( (NewPosition >= 1) && (NewPosition <= NewLength) );
if (Success)
{ // create new node and place Newitem in it
NewPtr = new ListNode;
Success = bool(NewPtr != NULL);
if (Success)
{ size = NewLength;
NewPtr->item = Newitem;
// attach new node to list
if (NewPosition == 1)
{ // insert new node at beginning of list
NewPtr->next = head;
head = NewPtr;
if (NewPtr-> next != NULL)
{
NewPtr->previous= Prev;
NewPtr->next = Prev->next;
Prev->next = NewPtr;
if ( NewPtr->next ) NewPtr -> next -> previous = NewPtr;
}
}
else
{ Prev = find(NewPosition-1);
// insert new node after node
// to which Prev points
NewPtr->next = Prev->next;
Prev->next = NewPtr;
} // end if
} // end if
} // end if
} // end insert
It is not possible for line 12 to be reached if line 11 doesn't succeed rendering the check on line 13 superfluous.
On line 24 (and the following lines,) Prev has some unspecified value, but you treat it as if it contains a valid non-null value. This will result in undefined behavior and memory corruption.
Btw, I suggest you ignore our local troll SakurasouBusters when he asks you to send him a PM. As you can see he doesn't want people to know he's requesting PMs and deletes the contents of his posts.
