Thread: Problems with deleting a node in a singly linked list

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    20

    Problems with deleting a node in a singly linked list

    Hey guys I'm finally understanding linked lists to an extent, but I ran into this problem. Everything works fine until I go to delete a node from the list.

    Code:
    #include <iostream> //for standard i/o
    #include <cstddef> //for NULL
    #include <iomanip> //for setprecision
    #include <string> //for string
    
    using namespace std;
    
    struct Book
    {
    	string author;
    	string title;
    	int date;
    	float price;
    };
    
    struct Node
    {
    	Book data;
    	Node* next;
    };
    
    Node* head = NULL; //start of list is NULL
    Node* prev;
    Node* curr;
    
    void PrintContents(Node* head);
    void AddNode(Node* head);
    void DeleteNode(Node* head, string targettitle);
    
    int main()
    {
    	int numBooks;
    	string targettitle;
    
    	head = new Node; //create first node in the list
    	
    	cout << "How many books would you like to enter into the list?: ";
    	cin >> numBooks;
    	cout << endl;
    	cin.ignore(100, '\n');
    	system("cls"); //clear screen
    
    	//Enquire for head node
    	cout << "Please enter the author of a book (e.g. Stephen King): ";
    	getline(cin, head->data.author);
    	cin.ignore(100, '\n');
    
    	cout << "Please enter the title of " << head->data.author << "'s book: ";
    	getline(cin, head->data.title);
    	cin.ignore(100, '\n');
    
    	cout << "Please enter the date of " << head->data.title << "'s publication: ";
    	cin >> head->data.date;
    	cin.ignore(100, '\n');
    
    	cout << endl;
    
    	cout << "Please enter the price of " << head->data.title << " at print time (e.g. $25.00): $";
    	cin >> head->data.price;
    	cin.ignore(100, '\n');
    
    	head->next = NULL;
    
    	system("cls");
    
    	for(int i = 0; i < (numBooks - 1); i++)
    	{
    		Node* temp = head; //assign node to be created to the first node in the list
    		temp->next = new Node; //create Node at the start of the list
    		temp = temp->next;
    
    		//Enquire for subsequent nodes
    		cout << "Please enter the author of a book (e.g. Stephen King): ";
    		getline(cin, temp->data.author);
    		cin.ignore(100, '\n');
    
    		cout << "Please enter the title of " << temp->data.author << "'s book: ";
    		getline(cin, temp->data.title);
    		cin.ignore(100, '\n');
    
    		cout << "Please enter the date of " << temp->data.title << "'s publication: ";
    		cin >> temp->data.date;
    		cin.ignore(100, '\n');
    
    		cout << endl;
    
    		cout << "Please enter the price of " << temp->data.title << " at print time (e.g. $25.00): $";
    		cin >> temp->data.price;
    		cin.ignore(100, '\n');
    
    		temp->next = NULL;
    
    		cout << endl << endl;
    
    		system("cls");
    	}//end for
    
    	cout << "List as originally entered: " << endl << endl;
    	PrintContents(head);
    	system("pause");
    	system("cls");
    
    	AddNode(head);
    	cout << "List after a new node is added: " << endl << endl;
    	PrintContents(head);
    	system("pause");
    	system("cls");
    
    	cout << "Please enter the name of the title whose book you will delete: ";
    	cin >> targettitle;
    	DeleteNode(head, targettitle);
    	cout << "List after a node is deleted: " << endl << endl;
    	PrintContents(head);
    	system("pause");
    	system("cls");
    
    	delete head;
    
    	return 0;
    }
    
    
    void PrintContents(Node* head)
    {
    	Node* temp = head;
    
    	cout << fixed << showpoint << setprecision(2);
    
    	cout << left << setw(20) << "Author" << setw(15) << "Title";
    	cout << setw(10) << "Date" << "Price" << endl;
    	cout << "--------------------------------------------------" << endl << endl;
    
    	while(temp != NULL)
    	{
    		cout << left << setw(20) << temp->data.author << setw(15) << temp->data.title;
    		cout << setw(10) << temp->data.date << "$" << temp->data.price << endl << endl;
    
    		temp = temp->next; //Traverse
    	}	
    
    	cout << endl;
    }
    
    void AddNode(Node* head)
    {
    	Node* temp = head;
    	Node* temp2;
    	Node* start_ptr = head;
    
    	temp = new Node;
    
        cout << "Please add another book to the list" << endl << endl;
    
    	cout << "Please enter the author of a book (e.g. Stephen King): ";
    	getline(cin, temp->data.author);
    	cin.ignore(100, '\n');
    
    	cout << "Please enter the title of " << temp->data.author << "'s book: ";
    	getline(cin, temp->data.title);
    	cin.ignore(100, '\n');
    
    	cout << "Please enter the date of " << temp->data.title << "'s publication: ";
    	cin >> temp->data.date;
    	cin.ignore(100, '\n');
    
    	cout << endl;
    
    	cout << "Please enter the price of " << temp->data.title << " at print time (e.g. $25.00): $";
    	cin >> temp->data.price;
    	cin.ignore(100, '\n');
    
    	temp->next = NULL; 
    
        if (start_ptr == NULL)
            start_ptr = temp;
        else
    	{ 
    		temp2 = start_ptr;
    
    		while (temp2->next != NULL)
    		         temp2 = temp2->next;
            
    
    		temp2->next = temp;
    	}
    
    	system("cls");
    }
    
    void DeleteNode(Node* head, string targettitle)
    {
    	prev = NULL;
    	curr = head;
    
    	while((curr != NULL) && (curr->data.title != targettitle));
    	{
    		prev = curr;
    		curr = curr->next;
    	}
    
    	prev->next = curr->next;
    
    	delete curr;
    }
    All is good until I input the title of the book to be deleted and return -- I then get only the cursor at the next line. Is the problem with how I'm using getline()?

    Thanks in advance for any help

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Your delete-function aren't very stable if you're deleting the first element, from an empty list or something that doesn't exist in a list. prevcan be NULL but you don't check for this when doing prev->next.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    since you already using std::string, what have you got against std::list? If you're writing this for learning purposes, that's cool, just be aware that you don't have to reinvent the wheel.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  4. #4
    Registered User
    Join Date
    Oct 2005
    Posts
    20

    Still learning

    I'm not familiar with the <list> library at all, but my professor insists that we do all this by hand....
    Last edited by omishompi; 02-23-2006 at 04:59 PM.

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    double-linked list for any data type:
    Code:
    std::list<std::string> List; //Create list
    
    List.push_back("Hello"); //Add an element to the end of the list
    
    List.pop_back(); //Remove the last element in the list
    
    //Remove the (first occurance of) string "Hello", if it exists
    std::list<std::string>::iterator i = List.find("Hello");
    if(i != List.end()) List.erase(i);
    
    //Quicker but more dangerous way of doing the same
    List.erase(List.find("Hello"));
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by omishompi
    I'm not familiar with the <list> library at all, but my professor insists that we do all this by hand....
    That's fair enough. Writing your own linked list is a good learning exercise. You'll understand linked lists better by doing it. Then once you've finished, compare it to using std::list. Unless you happen to be some sort of C++ prodigy, you'll find that list is better. then you can throw yours away and never use it again.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  7. #7
    Registered User
    Join Date
    Oct 2005
    Posts
    20
    Magos: thanks for the example.

    ChaosEngine: I've definately found that there is an easier way to everything I had done previously. I'm currently in the highest level "programming" course at university, and I asked my professor if we were ever going to get into any STL or MFC stuff and she said "uh..no". I understand the logic behind teaching the long way around things, but yet the short way is left for yourself to decipher, which has never made much sense to me.

    But anyway to the topic, I think my problem is within the getline() that I'm using as input and passed to the Delete function. That's the algorithm I've always used for a search delete and it has always worked before. Then again, my logic could be all wrong.

  8. #8
    Registered User
    Join Date
    Oct 2005
    Posts
    20
    I found a better way..thanks for all the help everyone

    Code:
    void DeleteNode(Node* head, string targettitle)
    {
    	if(targettitle == head->data.title)
    	{
    		prev = head;
    		head = head->next;
    	}
    	else
    	{
    		curr = head;
    		
    		while(curr->next->data.title != targettitle)
    			curr = curr->next;
    
    		prev = curr->next;
    		curr->next = curr->next->next;
    	}
    	
    	delete prev;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory Leak
    By jtullo in forum C Programming
    Replies: 7
    Last Post: 12-11-2006, 11:45 PM
  2. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  3. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 05:41 PM
  4. Big help in Astar search code...
    By alvifarooq in forum C++ Programming
    Replies: 6
    Last Post: 09-24-2004, 11:38 AM
  5. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM