1

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:

  1. Insert an item (string) into an ascending ordered list
  2. Delete an item (string) from an ascending ordered list
  3. Edit an item (string) in an ascending ordered list
  4. 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?

8
  • 1
    Step 1: Make a find function that takes the string to be found and returns the found node (or null if not found). Step 2: Write a remove function that takes a pointer to a node remove the node from the list and 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. Commented Oct 19, 2020 at 3:07
  • How would I go about writing that though? I'm sorry, I'm a very young student and I have been struggling really bad with Linked Lists. I'm also on a time crunch (its due in an hour and 45 minutes) and I'm stressing really bad about getting it done on time Commented Oct 19, 2020 at 3:16
  • This is not an answer to your question but you can checkout this video youtu.be/JfmTagWcqoE about how to write leak-free algorithms. The speaker is very prominent figure in C++ community. I think you can learn something to apply to your project. Commented Oct 19, 2020 at 3:18
  • 1
    Finding the node you want to remove should be easy. Start at the beginning and loop through all the items in the list until you find the node holding the string (return the node) or you run out of nodes (return 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. Commented Oct 19, 2020 at 3:31
  • 1
    One last note: Because the functions all build on one another, exhaustively test the smurf out of each one individually as you go. You can't get a working removal if you made a mistake in insert, ad if you waste time debugging removal for a bug in insert, that's time wasted you could have spent on other homework or a beer at the pub. Or in my case running a Champions game. Come to think of it, the main reason I had time for RPGs is I was introduced early to the debugger. Learn to use whatever debugger came with your development tools. Save you years of debugging. Commented Oct 19, 2020 at 3:37

1 Answer 1

1

Presuming you have constructed a valid doubly-linked list (where Head->prev is nullptr as is Tail->next [or the last node]), then removing any one node is straight forward. (I would encourage adding a Tail pointer, e.g. Node *Head, *Tail; where Tail always points to the last node in the list - though doing an in-order insertion eliminates the benefit of the O(1) insertion it would provide at the end)

To add or remove nodes efficiently, you must understand the concept of iterating over your list using both the address of the pointer, and pointer itself. This eliminates any special cases.

In a bit more detail, in your linked-list, each Node is a pointer to an allocated struct Node, each of the pointers also has its very own address. By using both the address of the pointer and pointer to node, you can replace what is at the current pointer address with another pointer (the next in your list) and then delete the allocated struct that was originally stored at that address (the original pointer there). This makes things much easier and is more fully discussed at Linus on Understanding Pointers

With a doubly-linked list, you have only to update the prev pointer for the node you will store at the current pointer address to point to what was the value of the prev pointer for the current node.

By using both the address of the current pointer and the pointer itself, when you change what is stored at the address of the current pointer -- you still have a pointer to the original struct Node that was there -- which you can use with delete.

Putting it altogether, you could do:

bool List::Delete (std::string data)
{
    Node **ppn = &Head;                     /* pointer to pointer to node */
    Node *pn = Head;                        /* pointer to node */

    /* iterate over each node using the address of poiner and pointer to node */
    for (; pn; ppn = &pn->next, pn = pn->next) {
        if (pn->data == data) {             /* if node data matches data */
            if (pn->next)                   /* if next not nullptr */
                pn->next->prev = pn->prev;  /* update next->prev to current->prev */
            *ppn = pn->next;                /* set node at current address to next */
            delete pn;                      /* delete original node at address */
            return true;                    /* return success */
        }
    }
    
    return false;       /* return failure (node not found) */
}

(note: suggest passing a reference rather than the string itself as a parameter, e.g. std::string& data -- slightly more efficient)

Untested, but should work fine. Look things over, try it, and let me know if you have any questions.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.