Delete Function to Delete a Node in a Doubly Linked List (C++)

Question

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?

Delete Function to Delete a Node in a Doubly Linked List (C++)

Answers (1)

Related Questions