LINKEDLIST find the "Kth" Element and Delete it!!

[voteboo]

How can I find the Kth element in this code??(I personally don't know what the author of the book was referring to when he decided to say "find the Kth element and delete it, if the Kth element isn't in the list terminate the program", I understood the whole question except th "Kth element" part. I found a way to find the smallest out of the whole list(which was part of my homework in a different exercise, but can't figure out how to find the largest(assuming that Kth is the largest number in the list because the author of the book WAS NOT clear) and delete it from the list of numbers input by the user. .

The following code is what I tweaked a little to find the smallest number in a unordered list, but the LARGEST number is what I cannot find.

template <class Type>
void unorderedLinkedList<Type>::deleteSmallest()
{
	nodeType<Type> *current; 
	nodeType<Type> *trailCurrent; 

	nodeType<Type> *small; 
	nodeType<Type> *trailSmall;
	
	if (first == NULL)
		cout << "Cannot delete from an empty list." << endl;
	else
		if (first->link == NULL)
		{
			first = NULL;
			delete last;
			last = NULL;
		}
		else
		{
			small = first;
			trailCurrent = first;
			current = first->link;

			while (current != NULL)
			{
				if (small->info > current->info)
				{
					trailSmall = trailCurrent;
					small = current;
				}

				trailCurrent = current;
				current = current->link;
			}

			if (small == first)
				first = first->link;
			else
			{
				trailSmall->link = small->link;

				if (small == last)
					last = trailSmall;
			}

			delete small;
		}
}

[voteboo]

Here is the entire .h file for your reference. I couldn't fit the file on my first post.

#ifndef H_UnorderedLinkedList
#define H_UnorderedLinkedList 

#include "linkedList.h"

using namespace std;

template <class Type>
class unorderedLinkedList: public linkedListType<Type>
{
public:
    bool search(const Type& searchItem) const;
 
    void insertFirst(const Type& newItem);
     
    void insertLast(const Type& newItem);
      //Function to insert newItem at the end of the list.
 

    void deleteNode(const Type& deleteItem);
     

	void deleteAll(const Type& deleteItem);
	   //Delete all occurences of a given element

	 void deleteSmallest();
	   //Find and delete the node with the smallest info
};


template <class Type>
bool unorderedLinkedList<Type>::
                   search(const Type& searchItem) const
{
    nodeType<Type> *current; //pointer to traverse the list
    bool found = false;
    
    current = first; //set current to point to the first 
                     //node in the list

    while (current != NULL && !found)    //search the list
        if (current->info == searchItem) //searchItem is found
            found = true;
        else
            current = current->link; //make current point to
                                     //the next node
    return found; 
}//end search

template <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
{
    nodeType<Type> *newNode; //pointer to create the new node

    newNode = new nodeType<Type>;//create the new node

    assert(newNode != NULL);

    newNode->info = newItem;    //store the new item in the node
    newNode->link = first;      //insert newNode before first
    first = newNode;            //make first point to the
                                //actual first node
    count++;                    //increment count

    if (last == NULL)   //if the list was empty, newNode is also 
                        //the last node in the list
        last = newNode;
}//end insertFirst

template <class Type>
void unorderedLinkedList<Type>::insertLast(const Type& newItem)
{
    nodeType<Type> *newNode; //pointer to create the new node

    newNode = new nodeType<Type>; //create the new node
     
    assert(newNode != NULL);

    newNode->info = newItem;  //store the new item in the node
    newNode->link = NULL;     //set the link field of newNode
                              //to NULL

    if (first == NULL)  //if the list is empty, newNode is 
                        //both the first and last node
    {
        first = newNode;
        last = newNode;
        count++;        //increment count
    }
    else    //the list is not empty, insert newNode after last
    {
        last->link = newNode; //insert newNode after last
        last = newNode; //make last point to the actual 
                        //last node in the list
        count++;        //increment count
    }
}//end insertLast


template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
    nodeType<Type> *current; //pointer to traverse the list
    nodeType<Type> *trailCurrent; //pointer just before current
    bool found;

    if (first == NULL)    //Case 1; the list is empty. 
        cout << "Cannot delete from an empty list."
             << endl;
    else if (first->info == deleteItem) //Case 2 
        {
            current = first;
            first = first->next;
            //count--;
            if (first == NULL)    //the list has only one node
                first->last = NULL;
			else
				last = NULL;
            count--;
			delete current;
        }
        else //search the list for the node with the given info
        {
            found = false;
            current = first;  //set trailCurrent to point
                                   //to the first node
            //current = first->link; //set current to point to 
                                   //the second node

            while (current != NULL && !found)
                if (current->info != deleteItem) 
					found = true;
				else
					current = current->next;

                    //trailCurrent = current;
                    //current = current-> link;
                
            //end while

            if (current == NULL)
				cout << "The item to be deleted isn't in "
				     << "the list." << endl;
			else if(current->info == deleteItem)
            {
				trailCurrent = current->back;
                trailCurrent->next = current->next;
                
                if (current->next != NULL)   //node to be deleted 
                                       //was the last node
                    current->next->back = trailCurrent;//update the value 
                                         //of last
                if(current== last)
					last = trailCurrent;//delete the node from the list
				count--;
				delete current;
            }
            else
                cout << "The item to be deleted is not in "
                     << "the list." << endl;
	}//end else
    //end else
}//end deleteNode


template <class Type>
void unorderedLinkedList<Type>::deleteAll(const Type& deleteItem)
{
	nodeType<Type> *current; //pointer to traverse the list
	nodeType<Type> *trailCurrent; //pointer just before current

	if (first == NULL)    //Case 1; list is empty. 
		cout << "Can not delete from an empty list." << endl;
	else
	{
		current = first;

		while (current != NULL)
		{
  			if (current->info == deleteItem) 
			{
				if (current == first)
				{
					first = first->link;
					delete current;
					current = first;
					if(first == NULL)
						last = NULL;
				}
				else
				{
					trailCurrent->link = current->link;
					
					if(current == last)
						last = trailCurrent;

					delete current;

					current = trailCurrent-> link;
				}
			}
			else
			{ 
				trailCurrent = current;
				current = current->link;
			}
		} // end while
	}
} //end deleteAll

template <class Type>
void unorderedLinkedList<Type>::deleteSmallest()
{
	nodeType<Type> *current; 
	nodeType<Type> *trailCurrent; 

	nodeType<Type> *small; 
	nodeType<Type> *trailSmall;
	
	if (first == NULL)
		cout << "Cannot delete from an empty list." << endl;
	else
		if (first->link == NULL)
		{
			first = NULL;
			delete last;
			last = NULL;
		}
		else
		{
			small = first;
			trailCurrent = first;
			current = first->link;

			while (current != NULL)
			{
				if (small->info > current->info)
				{
					trailSmall = trailCurrent;
					small = current;
				}

				trailCurrent = current;
				current = current->link;
			}

			if (small == first)
				first = first->link;
			else
			{
				trailSmall->link = small->link;

				if (small == last)
					last = trailSmall;
			}

			delete small;
		}
}

#endif 

[bartoli]

Finding the Kth element means find the element at position K. The author probably meant make a function that takes a position K in argument, and if the list has at least K elements, it deletes the one at position K.

[voteboo]

Here are the question specifically:

"Write a function that returns the info of the Kth element of the linked list. If no such element exists terminate the program."

"Write a function that deletes the Kth element of the linked list. If no such file exists, terminate the program."

The problem here is that the book never mentioned how to find the Kth element throughout the whole chapter. So, in simple words, I'm lost because I don't even know where to start.

Any replies will be much appreciated. Thanks

[bartoli]

OK, a linked list is composed of items . Each item has a pointer to the previous AND/OR the next elements in the list.
In your case, each item has some info (the info attribute), and a pointer to the next element (the link attribute)
So starting from the first element (pointed by first), you can browse all the list by reading successively each element's "link" to the next element

[moorecm]

Perhaps it would help to picture the data structure as a chain. The links only touch adjacent links. If you were to traverse the linked list (such as electricity would pass through a chain), you would start at the root node (or first link).

To get the the 2nd link, you would pass through the 1st.
To get to the 3rd, you would pass through the 1st and then the 2nd.
...
To get to the Nth link, you would pass through all N-1 links.

So, you are writing a function that takes a number, K, and counting how many times you follow the pointer to the next node. Check each node for validity before moving to the next.

[voteboo]

Perhaps it would be better if you guys can illustrate your explanation with codes rather than words. I understood the area of going from the first to the second, the second to the third, etc... but the issue here is, "What exactly is the Kth element?". Put it this way, if I need to print the Kth element, what'd it look like??

What would it be the Kth element in the following list which is my actual output?

Here is my current output:

Enter numbers ending with -999:
23
23
5
2
234

525624
86
767
-999

List: 23 23 5 2 234 525624 86 767
Length of the list: 8

List before deleting all occurences
23 23 5 2 234 525624 86 767
Length of the list: 8

List after deleting the smallest element
23 23 5 234 525624 86 767
Length of the list: 7

[Here is where the Kth element should be located in the output]{not part of actual output for reference only}

List after deleting all occurences of 23 23 5 234 525624 86 767
Length of the list: 0

Press any key to continue . . .

The numbers you guys see are random numbers enter by the user, so the list is in fact not ordered.

[bartoli]

For the Kth element, you would simply look K times at the elements next element
K is a number. If it is 1, you will look at the first element. If it is 2, yo will look at the second element,...
K is a number that you are supposed to ask the user in your program. And then , make a function that, based on the value of K returns the correct element, if the list is big enough to have K elements

[voteboo]

The former code of the code I posted above did that bartoli; it actually asked the user to enter the number out the ones the user entered at the beginning of the code. Then, the program would eliminate that number and leave the list exactly as it is(in the same order as the list was first input), but without the number the program asked the user to enter on the second question, which was the number to be deleted. I do have that code, but the issue here bartolli is the Kth element.

I did a search online and found several forums with people asking for the Kth smallest or the Kth largest. In my case, I do know(I suppose) that the question can't ask about the smallest when it refers to the " Kth element" because I already found it and have a function that eliminates(deletes) the smallest regardless the location of the number in the list(first, second, last, fifth,,etc), the smallest element was the first challenge out of two I need to complete. The issue,as I said before, is that the author does not specify what he meant by "Kth element" nor does he had an example illustrating a possible similar solution in the book.

I don't know if by Kth element he's(author of the book) referring to the "largest element" or "smallest element"???

As I said before, I found the smallest element before I post this thread, so it cannot be the smallest(I think) because that'd be kind of redundant to ask the same question again. So, my supposition is that the author is asking for the "largest", but still not sure.

[bartoli]

I'm sorry, but at this point, i don't understand what you don't understand..

[voteboo]

That's why I wasn't able to get that clear in the first place. I need some code to show how to. I posted my code above because I need to extend the linkedlist.h file and create another function that finds the Kth element. Unfortunately, no one posted any code that could fulfill my question that at least showed me a similar way to solve the problem I'm facing. Will try to see how to solve it in the meantime. Hopefully somebody will post something back.

[shacktar]

bartoli wrote:

For the Kth element, you would simply look K times at the elements next element. K is a number

voteboo wrote:

The former code of the code I posted above did that bartoli

If you're referring to the code you posted here, then no it doesn't. I see functions for deleting the smallest, or the largest, or deleting some entry in the list matching an input, but I don't see any that delete the Kth element.

I don't know if by Kth element he's(author of the book) referring to the "largest element" or "smallest element"???

He's referring to neither. He's referring to the Kth element from the front of the list.

Let's say the list has 5 elements in it.

node1 -> node2 -> node3 -> node4 -> node5 -> (null)

Here, K can be any number from 1 to 5. e.g. Deleting the Kth element (where K==1), would be deleting node1 from the list (see the list above). e.g. Deleting the Kth element (where K==3) would be deleting node3 from the list.

I need some code to show how to

On this board, we don't give out full solutions to problems, only explanations to help get through any roadblocks or misunderstandings. If we were to show you the code for this, it would be giving you the full solution. But, hopefully you should be able to figure it out from here. To reiterate, the "Kth element" means the Kth element in the list from the front. What you need to do is start at the head of the list. If K==1, you've found the element to delete. Otherwise, check the link. If it's not null, set the current node to the next. Stop when you've done K-1 moves or if the next node is null. If you've reached a null entry before reaching the Kth node, then the list does not have a Kth element. Otherwise, after K-1 moves you've reached the Kth node, then all you have to do is delete the node.

[voteboo]

The code I posted above is what I'm doing. I already completed most of it except for the Kth element. I'm not asking for the solution of the whole problem because I worked through most of it, except of course the Kth element(which would be a partial solution). The code above is the whole program minus the main.cpp file which I didn't upload. I actually never said I found the Kth element. What I meant to say was that the code above looked for the smallest number only, not the largest. What's confusing me a lot is that Kth element? What is it? There is no reference on my book at all nor the author explains what he meant by"finding the Kth element". If you need some code to work with, the code is posted above. I can't create another .h file or .cpp file because I need to stay within three files only. All I can do is extend the unordered.h file as well as on the linkedlist.h file.

these are the specific questions coming from the author:

"Write a function that returns the info of the Kth element of the linkedlist. If no such element exists terminate the program."

"Write a function that deletes the Kth element of the linkedlist. If no such file exists, terminate the program."

[shacktar]

What's confusing me a lot is that Kth element? What is it? There is no reference on my book at all nor the author explains what he meant by"finding the Kth element".

shacktar wrote:

He's referring to the Kth element from the front of the list.

Let's say the list has 5 elements in it.

node1 -> node2 -> node3 -> node4 -> node5 -> (null)

Here, K can be any number from 1 to 5. e.g. Deleting the Kth element (where K==1), would be deleting node1 from the list (see the list above). e.g. Deleting the Kth element (where K==3) would be deleting node3 from the list.

Still confused? If so, then I'm sorry I don't know how to make it any clearer.

[voteboo]

Now,that I understood. The question here is that I have to ask the user to enter the number to be deleted, or do I have to make the code to do it by itself? Remember that the numbers I ask the user to enter are random numbers(doesn't follow a specific order).

There was actually a part on my former code that ask the user to delete one number of the list with the list keeping its current order.

On the examples you showed above, your pointing to a specific node(node2, node3, node4, etc). Is there a way to point randomly?

[Azagaros]

Kth, Nth, Xth they are all synonymous for being some count into a list or other object. In other words I start from the top and start counting down to the Kth number. Another way to look at it if I want the 13th element of the structure.

an example:

Listptr* LinkedList::FindAtCountKth(int Count)
{
       // input: Count is my count I want to find
       Searchptr = Listheadptr;
       while( SearchPtr )
       {
                Count --;
                if( !Count )  break;
                SearchPtr = SearchPtr->next;
        }
        return SearchPtr;
}

This is how I would write one of these kind of functions, I don't have all the error traps in it but it is a choice where I would do them. This looks like you don't understand one nuance of the English language for you not to understand the kth statement. It is a poor choice of words by the other to describe the problem at hand.

[voteboo]

Some technical terms I do not understand in C++, not english itself. The problem here arouse because the book never explained how to solve problems like this one. That's all. The kth statement isn't covered in the book I'm using.


I don't know whether this is an insult or not? What are you trying to say here ? I'm not following you!!

Azagaros "This looks like you don't understand one nuance of the English language"

[Azagaros]

It wasn't an insult. Many of the people who program on this site aren't native English speakers so I made an assumption of that, and I apologize. That term is usually associated with math or science, which computer science is part of.

[sohguanh]

We may not express ourselves adequately in English but the source code we write are definitely in English. I wonder if there are programming languages that are in language not English which should be possible since down to the hardware level it is just a set of instructions and opcodes. We just need some "step(s)" to translate our non-English code into the equivalent set of instructions and opcodes and we are ready to go isn't it ?

But due to maintenance reasons or not so attractive business venture, most programming languages are still written in English. But that does not stop us from putting in non-English comments in our source code too :)

PS I think Ruby is created by a Japanese researcher but it is still in English too!

[voteboo]

sohguanh I don't have a problem with what you said.

Azagaros, apology accepted, but next time do not assume. Assumptions create problems most of the time, better be sure than not to be. I've been writing with errors on my posts because this program is important for me. I'm still rushing to finish it. This is due for tomorrow.

Thanks for your help though. (this does not mean that my code is finished yet)