In my cs2 class we are covering simple lists very quickly. I was assigned to add some functions to a basic list class, and after much thought I can not understand how to solve the problem.

Here is the assignment:

you will add the
following methods:

+ removeNode(val : int) : void This function receives an int as a
parameter and removes the node storing the value val if such node exist.

+ searchNode(val : int) : Node* This function receives an int as a
parameter and return a pointer pointing to the node storing the value val if
such node exist, else return NULL.

+ insertAfter(val : int, ptr : Node*): void This function receives an int
and a pointer to a node in the list as parameters and insert val in a new
node, and stores the new node in the list after the node to which ptr point.

Here is my code:

//******************************************************************************
//Programer: Kyle Willett
//Course:    CS-1513
//Program:   Assignment 7
//Purpose:   Functoins to remove a node, search for a node, and insert a node.
//Input:     Value to remove or value to search for or value for a new node.
//Calculate: Search or, manipulate ptr's for removal or insertion of nodes.
//Output:    Pointer to a node for two of the functions.
//******************************************************************************

#include<iostream>
#include<cstdlib>

using namespace std;

//******************************************************************************
class Node;

class Node
{
	private:
		int value;
		Node *next;
//************************************************		
	public:
	   //****CONSTRUCTORS****
    	Node()
		{
			value=0;
			next=NULL;	
		}
		Node(int val, Node *ptr)
		{
			value=val;
			next=ptr;
		}
//************************************************		
		int getValue()
		{
			return value;
		}
//************************************************
		void setValue(int val)
		{
			value=val;
		}
//************************************************
		Node* getNext()
		{
			return next;
		}
//************************************************
		void setNext(Node* ptr)
		{
			next=ptr;
		}
};
//******************************************************************************
class List
{
	private:
		int size;
		Node * head;
		Node * tail;
//************************************************
	public:
	   //****CONSTRUCTOR****
    	List()
		{
			size=0;
			head=NULL;
			tail=NULL;
		}
//************************************************
		int getsize()
		{
			return size;
		}
//************************************************
		Node* getHead()
		{
			return head;
		}
//************************************************
		Node* getTail()
		{
			return tail;
		}
//************************************************
		void setHead(Node *ptr)
		{
			head=ptr;
		}
//************************************************
		void setTail(Node* ptr)
		{
			tail=ptr;
		}
//************************************************
		void addFront(int val)
		{
			Node*  temp= new Node();
			(*temp).setValue(val);
			(*temp).setNext(head);
			
			head=temp;
			if(tail==NULL)
			{
				tail=temp;
			}
			
			size++;
		}
//************************************************
		void printValues()
		{
			Node* temp;
			temp=head;
			while(temp!=NULL)
			{
				cout << "Value in current Node is: ";
				cout <<(*temp).getValue() << endl;
				temp=(*temp).getNext();
			}
		}
//************************************************
		void addEnd(int val)
		{
			Node* temp= new Node(val, NULL);
			if(tail==NULL)
			{
				tail=temp;
				head=temp;
			}
			else
			{
				(*tail).setNext(temp);
				tail=temp;
			}                          
			size++;
		}
//************************************************
		void sortList1()
		{
			Node *temp1;
			Node *temp2;
			Node *temp3;

			temp1=temp2=head;
			
			int minVal;

			while(temp1!=NULL)
			{
				minVal=(*temp1).getValue();

				temp3=temp1;
				
				while(temp2!=NULL)
				{
					if((*temp2).getValue()< minVal)
					{
						minVal=(*temp2).getValue();
						temp3=temp2;
					}	
					temp2=(*temp2).getNext();
				}
				(*temp3).setValue((*temp1).getValue());
				(*temp1).setValue(minVal);
				temp1=(*temp1).getNext();
				temp2=temp1;
			}
		}
//************************************************
    void removeNode(int val)
    {
        
    }
//************************************************   
    Node* searchNode(int val)
    {
        Node* temp;
		temp=head;
			
        while(temp!=NULL)
        {
            if((*temp).getValue()==val)
            {
                return temp;
                //This statment returns the value in the node if it matches
                //the value searched for.
            }
            else if(temp!=NULL)
            {
                temp=(*temp).getNext();
            }
        //This statment goes to the next node if the search value wasn't found
        }
        if(temp==NULL)
        {
            return NULL;
        }
        //This return statment is used if the search value was not found.
    }
//************************************************
    void insertAfter(int val, Node* ptr)
    {
        Node *temp0;
        //used to hold a copy of the current list.
        Node *temp1;
        //used to know the value of the current element that must
        //be shifted down one.
        temp0=temp1=head;
        
        bool check=false;
        
        while(check==false)
        {
            
            if(temp0==ptr)
            {
                temp1=temp0;
                temp0= new Node(val, (*temp0).getNext());
                check=true;
                ptr=temp0;
            }
            temp0=(*temp0).getNext();
        }
    }	
};
//******************************************************************************
//******************************************************************************
int main()
{
	//create instance of class node.
	
	Node var1;
	var1.setValue(20);
	cout << var1.getValue() << endl;

	//create a list object.
	List var2;

	for(int n=0; n<10; n+=2)
	{
		var2.addFront(n);
		var2.addEnd(n+1);
	}

	cout << var2.getsize()<< endl;

	var2.printValues();
	
	var2.sortList1();
	
	cout << endl << endl << endl;	

	var2.printValues();

	cout << endl << endl << endl;	

    int value=0;
    Node *temp=NULL;
    cout << "Enter a value to search the list for: ";
    cin >> value;
    cout << endl;
    cout << "The value searched for is: ";
    temp=var2.searchNode(value);
    if(temp!=NULL)
    {
        cout << (*temp).getValue();
    }
    else if(temp==NULL)
    {
        cout << "NULL";
    }
    //The if statment is used because of errors if the value returned was
    //NULL, so the conditional statment doesnot let the computer attempt to 
    //dereference NULL.
    cout << endl << endl;

    int val;
    cout << "Input value for new Node: ";
    cin >> val;
    cout << endl;
    var2.insertAfter(88, var2.getHead());
    var2.printValues();
    cout << endl;
    
	return 0;
}
//******************************************************************************

if it helps here is an earlier version of the insertAfter function I was working on:

void insertAfter(int val, Node* ptr)
{
    Node *temp0;
    //used to hold a copy of the current list.
    Node *temp1;
    //used to know the value of the current element that must
    //be shifted down one.
    temp0=temp1=head;
    
    while(temp0!=NULL)
    {
        if(temp0==ptr)
        {
            temp1=temp0;
            temp0= new Node(val, temp1);
        }
    }
}

I need help with finishing the insertAfter function and I don't even know where to start with the removeNode function.

Since I spent so much time trying to understand everything the time I have to do this project has ran out, it is due tomorrow, so prompt help would be appreciated!

Thank You.

There are two things that occur to me about insertAfter() ; first, that in the current version you aren't testing for the end of the list; second, that you want to insert the new node after the node pointed to by ptr , but right now, you have it replacing ptr , instead.

//************************************************
    void insertAfter(int val, Node* ptr)
    {
        Node *temp0;
        //used to hold a copy of the current list.
        Node *temp1;
        //used to know the value of the current element that must
        //be shifted down one.
        temp0 = temp1 = head;
        
        while(temp0 != NULL)
        {
            
            if(temp0 == ptr)
            {
                temp1 = new Node(val, ptr->getNext());
                ptr->setNext(temp1);
                return;
            }
        }

        // reached the end of the list
        temp->setNext(new Node(val, NULL));
    }

I can't promise that this will work, but it should. Note the use of the member indirection operator ( -> ), which is basically a shorthand for dereferencing the pointer and getting the member from the dereferenced value.

Edited 5 Years Ago by Schol-R-LEA: n/a

I just noticed two serious problems with the code I posted. Here's the corrected code (I hope):

//************************************************
    void insertAfter(int val, Node* ptr)
    {
        if (head == NULL)
        {
            head = new Node(val, NULL);
            return;
        }

        Node *current;
        //used to hold a copy of the current list.
        Node *previous;
        //used to know the value of the current element that must
        //be shifted down one.
        

        current = previous = head;
        
        while(current != NULL)
        {
            if (current == ptr)
            {
                ptr->setNext(new Node(val, ptr->getNext()));
                return;
            }
            previous = current;
            current = current->getNext();
        }

        // reached the end of the list
        previous->setNext(new Node(val, NULL));
    }

Edited 5 Years Ago by Schol-R-LEA: n/a

Ok thank you very much for the help with the insert function, do you have any advice on the remove function?

Well the time came for me to have to submit the program thanks you for helping me though.

I the code I wound up using for the remove function was:

void removeNode(int val)
    {
        Node *previous;
        Node* temp;
		temp=previous=head;
		
		if((*temp).getValue()==val)
		{
            delete temp;
            temp=(*temp).getNext();
        }
		

		while(temp!=NULL && (*temp).getValue()!=val)
		{
            previous=temp;
            temp=(*temp).getNext();
        }
        
        if((*temp).getValue()==val)
        {
            (*temp).setNext((*previous).getNext());
            delete temp;
            //In this step I am trying to preserve the linking of the list, 
            //but it does not seem to work correctly.
        }      
   }

I know this doesn't work but I think it is close.

This article has been dead for over six months. Start a new discussion instead.