Writing a Delete Algorithm in an ordered linked list

This is a discussion on Writing a Delete Algorithm in an ordered linked list within the C++ Programming forums, part of the General Programming Boards category; I am trying to write a delete algorithm for an ordered linked list. Search and traverse I think I have ...

  1. #1
    Registered User
    Join Date
    Oct 2013
    Posts
    2

    Writing a Delete Algorithm in an ordered linked list

    I am trying to write a delete algorithm for an ordered linked list. Search and traverse I think I have down but delete is giving me fits. It crashes every time. Any help is greatly appreciated!

    I have a private pointer to a ListNode strcuture called head in my TestLL class. The ListNode structure contains int Key, double dataValue, and ListNode *next. The function returns true if the node to delete was found and deleted or false if it was not found.


    Code:
    bool TestLL::Delete(int Key)
    {
        ListNode *back = NULL, *temp = head;
        //Search for the node to delete
        while((temp != NULL) && (key != temp -> key))
        {
            //advance the pointers
            back = temp;
            temp = temp->next;
        }
        //Check for node to delete not being found
        if( temp == NULL)
        {
            return false;
        }
        //Check for deleting the head of the list
        else if( back == NULL) //I'm very unsure of my else if and else
        {
            return false;
        }
        else// Remove node other than at the head
        {
            delete temp;
        }
    
        //deallocate memory used by the removed node
    
        free(temp);
        return true;
    
    }


  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    You do not want to use delete and free together. Delete is enough.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    Registered User
    Join Date
    Oct 2013
    Posts
    2
    Thank you for the reply! So simply removing free(temp); is my only issue? My logic and syntax is correct otherwise?

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Trust me, it's far better you try to find out yourself. Take a piece of paper and a pencil and draw what your function would do at a list. Use a 3 noded list for example. Do not forget to draw your pointers and, if needed, keep track of the values of your variables in a table. Here you do not need to keep track of your values.

    Welcome to the forum.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You should only delete things you got from new; free should only be used with malloc. Since this is C++, I would suspect you are using new and delete.

    Before you delete your object though, you need to fix your pointers; otherwise you have a "hole" in your list and no way to bridge the gap. You need to make the element before the to-be-deleted object point at the element after it, and vice versa.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Delete all from linked list
    By lio in forum C Programming
    Replies: 4
    Last Post: 12-01-2010, 02:15 PM
  2. delete doubly linked list
    By bazzano in forum C Programming
    Replies: 4
    Last Post: 05-01-2007, 03:42 PM
  3. ordered linked list
    By redmondtab in forum C Programming
    Replies: 48
    Last Post: 10-22-2006, 06:09 AM
  4. problme with ordered linked list
    By palku in forum C Programming
    Replies: 5
    Last Post: 09-19-2005, 04:33 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21