For a project in my Data Structures class, we have been instructed to make a program that creates a linked list.
Here is the assignment instruction: Your assignment is to define and implement a List ADT as an in-memory, ordered, double linked list. Your data will come from an input text file called ThingsToDo.txt. The List class will define, along with a constructor and destructor, the core functionality for a list:
- Insert an item (string) into an ascending ordered list
- Delete an item (string) from an ascending ordered list
- Edit an item (string) in an ascending ordered list
- Print the ordered list
I have created the following header file:
using namespace std;
//create a node with data and link fields
struct Node
{
string info;
Node * next;
Node * prev;
};
//the List ADT definition
class List
{
public:
// construct a List object
List();
// Destroy a list object
~List();
// Insert a string into its correct alpha location in the list and return true if the function worked and false otherwise
bool Insert(string);
// Delete a string from its location in the list and return true if the function worked and false otherwise (no string found)
bool Delete(string);
// Edit a string from its location in the list and return true if the edit worked and false otherwise.
bool Edit(string, string);
// Print all of the nodes info from the beginning to end.
void Print() const;
private:
Node * Head;
};
My problem is that I do not know how to make a good delete function in my c++ file.
I have made the following Insert and Edit functions, but if anyone could help me create a good Delete function it would be greatly appreciated.
bool List::Edit(string target, string replace)
{
bool Success = false;
// first delete the target node calling the Delete function
if (Delete(target))
{
// if deleted, then insert the replace node
if (Insert(replace))
{
Success = true;
}
}
// will only return true if Delete and add both worked , otherwise false
return Success;
}
/*Function description: insert data into the doubly linked list by placing
* it into its correct ascending alpha location
*/
bool List::Insert(string data)
{
bool wasSuccessful = false;
// Allocate memory for a node and store the address in p. If new returns
// false, then memory could not be allocated and the function will exit
// with failure.
Node* p = new Node;
if (p != NULL)
{
//store the KEY data in the node
p->info = data;
// Logic that handles the insert empty case (CASE 1)
if (Head == NULL)
{
p->next = NULL;
p->prev = NULL;
Head = p;
wasSuccessful = true;
}
else
{
//Logic if the List is not empty, cur is the traversal pointer, p points
//to the node to be inserted (CASES 2, 3 AND 4), set traversal
//pointer cur
Node* cur = Head;
//Loop until the node was successfully inserted, the loop
//looks for the correct insertion point which could be front
//middle, or last
while (!wasSuccessful)
{
//insert node (p) still greater than current node (cur)
if (p->info > cur->info)
{
//are we at the last node? condition for last insertion (CASE 2)
if (cur->next == NULL)
{
//insert node at end of list
p->next = NULL;
p->prev = cur;
cur->next = p;
wasSuccessful = true;
}
else
{
//move the current pointer to the next node
cur = cur->next;
}
}
else
{
//we have found an insertion point, the node to be inserted
//is lesser than the current node in the list
//Is it an insert front condition? (CASE 3)
if (Head == cur)
{
p->next = Head;
p->prev = NULL;
Head->prev = p;
Head = p;
}
else
{
//Logically, this has to be an insert middle case (CASE 4)
p->next = cur;
p->prev = cur->prev;
cur->prev->next = p;
cur->prev = p;
}
wasSuccessful = true;
}
}
}
}
return wasSuccessful;
}
The only thing I have written for the Delete function is this:
bool List::Delete(string data)
{
}
Is there any way someone could write the code for me for the delete function?
deletes it. Step 3: Write the delete function. Use the find function to find the node you want removed and if found, use the remove function to remove it. General rule of thumb: When a problem is too big for your brain to swallow, chop it up into smaller problems.nullptr).removing the node... gets tricky because you need to attach the node before to the node after and vise versa without accidentally invalidating any of the pointes while you still need it. This is where checking your logic by drawing pictures really comes in handy.