Thread: Linked List Node Deletion based on Data

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    10

    Post Linked List Node Deletion based on Data

    I was given an Assignment to Create a C++ program to input ID, Semester, Name of a student via Linked Lists. The functions to be implemented were Add, Search and Delete a Student.
    I have completed it as far as could go , but am facing difficulty in implementing the Delete Function .....
    Here is the code of the program that I have written

    Code:
    #include<iostream.h>
    /*Delete based on ID pending*/
    
    struct Student {
    	int id, sem;
    	char name[30];
    	Student *next;
    };
    Student *start=NULL, *ptr=NULL, *traverse=NULL, *temp=NULL;
    void displayList() {
    	traverse = start;
    	cout<<"\n----Linked List Elements----\n";
    	while(traverse!=NULL) {
    		cout<<(traverse->id)<<" ";
    		traverse = traverse->next;
    	}
    }
    int main() {
    	cout<<"\n----Enter Your Choice----\n";
    	cout<<"1. Add Student\n"
    		 <<"2. Search Student\n"
    		 <<"3. Delete Student\n";
    	void deleteStudent();
    	void searchStudent();
    	void addStudent();
    	char cont = 'y';
    	do {
    	int user_choice;
    	cout<<"Enter your Choice: ";
    	cin>>user_choice;
    		switch(user_choice) {
    			case 1: addStudent();
    					  break;
    			case 2: searchStudent();
    					  break;
    			case 3: deleteStudent();
    					  break;
    			default: cout<<"Wrong Choice!!";
    		}
    	cout<<"\n\nDo you want to continue? (y/n): ";
    	cin>>cont;
    	} while(cont=='y'||cont=='Y');
    	return 0;
    }
    
    void deleteStudent() {
    	traverse = start;
    	if(traverse==NULL)
    		cout<<"Database Empty!!";
    	else {
    		int temp_ID;
    		cout<<"Enter ID to be deleted: ";
    		cin>>temp_ID;
    		while(traverse!=NULL) {
    			if(traverse->id==temp_ID) {
    				cout<<"DELETED!!";
    				cout<<"#####################################\n";
    				cout<<"ID: "<<traverse->id<<endl;
    				cout<<"Semester: "<<traverse->sem<<endl;
    				cout<<"Name: "<<traverse->name<<endl;
    				cout<<"#####################################\n";
    				cout<<traverse->id;
    				temp=traverse->next;
    				cout<<temp->id;
    				cout<<traverse->id;
    				delete traverse;
    				traverse=temp;
    				cout<<traverse->id;
                displayList();
    				break;
    			}
    			else {
    				traverse=traverse->next;
    			}
    		}
    	}
    }
    void searchStudent() {
    	cout<<"Enter ID to be Searched: ";
    	int data_search;
    	cin>>data_search;
    	traverse = start;
    	while(traverse!=NULL) {
    		if((traverse->id)==data_search) {
    				cout<<"\n----Linked List Linear Search Result----\n";
    				cout<<"ID: "<<traverse->id<<endl;
    				cout<<"Semester: "<<traverse->sem<<endl;
    				cout<<"Name: "<<traverse->name<<endl;
    				break;
    		}
    		else
    			traverse = traverse->next;
    	}
    }
    void addStudent() {
    	ptr = new Student;
    	if(ptr==NULL)
    	cout<<"Memory Full!!";
    	else {
    		cout<<"Enter Student ID: ";
    		cin>>ptr->id;
    		cout<<"Enter Semester: ";
    		cin>>ptr->sem;
    		cout<<"Enter Name(without space): ";
    		cin>>ptr->name;
    			if(start==NULL) {
    				start = ptr;
    				ptr->next = NULL;
    			}
    			else {
    				Student *temp;
    				temp = start;
    				start = ptr;
    				ptr->next = temp;
    			}
    	}
    }
    Please tell me where am I missing while deleting a Node based on the ID stored in it ....

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I've not studied your code in great detail, but I think you are doing two things wrong:
    1. You are not changing the link of the previous node. The "next" of the node before the one deleted should be set to the node pointed to by the deleted node.
    2. The debug printout here:
    Code:
    				temp=traverse->next;
    				cout<<temp->id;
    				cout<<traverse->id;
    				delete traverse;
    				traverse=temp;
    				cout<<traverse->id;
    will break if you just deleted the last one of the nodes, because temp would be NULL, and printing something where the reference address is NULL would be a bad thing to do.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by matsp View Post
    1. You are not changing the link of the previous node.
    That's exactly the problem you have. You remove one of the elements, invalidating all forward and back points pointing to that element, but you don't link up the previous and next elements.

    I.e. if you have A => B => C and you remove B, you then need to set A => C, otherwise you'll be pointing into random memory and that way danger lies.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    10
    Quote Originally Posted by QuantumPete View Post
    That's exactly the problem you have. You remove one of the elements, invalidating all forward and back points pointing to that element, but you don't link up the previous and next elements.

    I.e. if you have A => B => C and you remove B, you then need to set A => C, otherwise you'll be pointing into random memory and that way danger lies.

    QuantumPete
    Code:
                                   temp=traverse->next; //Stores Node to be deleted in temp
    				cout<<temp->id;
    				cout<<traverse->id;
    				delete traverse; //Deletes the Node
    				traverse=temp; //Assigns the previous node the value of deleted node
    				cout<<traverse->id;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 05:41 PM
  4. Help here with qsort!
    By xxxrugby in forum C Programming
    Replies: 11
    Last Post: 02-09-2005, 08:52 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM