Linked list reversal

[Deadweight77]

I've been trying to learn more about nodes and linked list and I'm not doing so hot. I've learned some of the concepts, but I need help with reversing the numbers I put in correctly and display them. This whole linked list concept is hard to fully grasp at.

 #include<iostream>
using namespace std;

class list
{
public:
	void add(double x);
	void del();
	void reverse();
	bool isMember(double x);
	list();
private:
	int data;
	list* next;
};
list::list()
{

}
class list* head;//global value
int main()
{
	list enter;
	head = NULL;//list is empty
	int num;
	double x;
	cout << "Enter in how many numbers you want:";
	cin >> num;
	cout << "Enter in what you want" << endl;
	for (int i = 0; i < num; i++)
	{
		cin >> x;
		enter.add(x);
	}
	cout << "Enter in a number to test: ";
	cin >> x;
	if (enter.isMember(x))
		cout << x << " " << "is on the list" << endl;
	else
		cout << x << " " << "isn't on the list" << endl;
	cout << "The reverse list is " << endl;
	enter.reverse();
	enter.del();
}

void list::add(double x)
{
	list* temp = new list;//creating a new node (keep in mind list=node for this program)
	temp->data = x;//dereferencing temp to access the fields of this node and change anything for this node 
	temp->next = head;
	head = temp;//the head (first value of the linked list) is equal to temp

}

bool list::isMember(double x)
{
	list* temp = head;
	while (temp != NULL)//while not empty
	{
		if (temp->data == x)
		{
			return true;//if number is found it is returned true
		}
		else
		{
			temp = temp->next;
		}
	}
	return false;
}

void list::del()
{
	list* temp = head;
	if (head != NULL)
	{
		head = head->next;
		delete temp;
		cout << "deletion done" << endl;
	}
	else
		cout << "List is empty" << endl;
}

void list::reverse()
{
	list* next;
	list* prev = NULL;
	list* curr = head;
	while (curr != NULL)
	{
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	head = prev;
	
}

[keskiverto]

Look at std::list http://www.cplusplus.com/reference/list/list/

It has members front(), push_front(), and pop_front()

(There is member reverse() too, but lets pretend there isn't.

std::list<int> original { 3, 2, 7 };
std::list<int> temp;

while ( ! original.empty() )
{
  temp.push_front( original.front() );
  original.pop_front();
}
swap( original, temp );
// original is now { 7, 2, 3 } and temp is empty 

Would you say that the code above is logically correct?

If yes, then how close are you from having equivalents of empty(), front(), push_front(), pop_front(), and swap() in your list?

[Deadweight77]

I'm afraid I still don't know how to do this. I was taught in class the one I did, but not the one you suggested. I still tried to do it so here:

void mylist::reverse(double x)
{
	list<int> temp;
	
	while (head != NULL)
	{
		temp.push_front((*head).front());
		(*head).pop_front();
	}
	swap(head, temp);
}

I changed the class to "mylist" instead of "list" because it looked like I needed the list library. I know this is wrong but I don't know how to combine these new concepts together.

[jonnin]

reversing a list is not so bad.
take the topmost node off the existing list and insert it at the top of the new list.
if you have 1 2 3 4
that means you take 1 off the list and insert it:
2 3 4
and new list 1
repeat this:
3 4
2 1
repeat again
4
3 2 1
and again
4 3 2 1

inserting and removal from the top should be easy after you have coded a list once; those are the most trivial cases. Can you do this?

if you want to preserve the original list, don't take them off of it each time, just build a new list by going to node->next repeatedly until null in the original. '

if you are rebuilding it in reverse, you don't need to make memory, just rearrange it. If you are making a copy, you have to get the memory.

[keskiverto]

Why does the mylist::reserve() take a parameter? What is it used for?

Does mylist have member front()? If not, is there something equivalent?
What do you get with head->data?

Does mylist have member pop_front()? If not, is there something equivalent?
What does head->del() do?

Swapping std::list and mylist ... how would you do it.

How about without std::list:

void mylist::reverse() {
  mylist* temp = head;
  head = nullptr;
  while ( temp ) {
    // node transfer
  }
}

Notice how we "swap" before the loop?


I feel necessary to point out that your code has other issues, but I won't list them.

[jonnin]

^^^ Truth. But, building a generic container is much, much harder than it looks. These exercises, IMHO, are really good stuff. They answer those nagging questions in the back of your head 'why did they DO it like THAT'. Having done it yourself, you will know why. This stuff is not trivial, so hang in there, keep asking until it clicks...

[dhayden]

Your code works for me. Remember that when you add items to the list, they go at the front, so if you add items 1,2,3,4. The list contains (starting from head) 4,3,2,1. Here's a version of your code that prints the two versions of the list:

#include<iostream>
using namespace std;

class list
{
public:
	void add(double x);
	void del();
	void reverse();
	bool isMember(double x);
	list();
    void print();
private:
	int data;
	list* next;
};
list::list()
{

}
class list* head;//global value
int main()
{
	list enter;
	head = NULL;//list is empty
	int num;
	double x;
	cout << "Enter in how many numbers you want:";
	cin >> num;
	cout << "Enter in what you want" << endl;
	for (int i = 0; i < num; i++)
	{
		cin >> x;
		enter.add(x);
	}
	cout << "The list is: ";
	enter.print();
	cout << "Enter in a number to test: ";
	cin >> x;
	if (enter.isMember(x))
		cout << x << " " << "is on the list" << endl;
	else
		cout << x << " " << "isn't on the list" << endl;
	cout << "The reverse list is " << endl;
	enter.reverse();
	cout << "The reversed list is: ";
	enter.print();
	
	enter.del();
}

void list::add(double x)
{
	list* temp = new list;//creating a new node (keep in mind list=node for this program)
	temp->data = x;//dereferencing temp to access the fields of this node and change anything for this node 
	temp->next = head;
	head = temp;//the head (first value of the linked list) is equal to temp

}

bool list::isMember(double x)
{
	list* temp = head;
	while (temp != NULL)//while not empty
	{
		if (temp->data == x)
		{
			return true;//if number is found it is returned true
		}
		else
		{
			temp = temp->next;
		}
	}
	return false;
}

void list::del()
{
	list* temp = head;
	if (head != NULL)
	{
		head = head->next;
		delete temp;
		cout << "deletion done" << endl;
	}
	else
		cout << "List is empty" << endl;
}

void list::reverse()
{
	list* next;
	list* prev = NULL;
	list* curr = head;
	while (curr != NULL)
	{
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	head = prev;
	
}

void list::print()
{
    for (list *p = head; p; p = p->next) {
	cout << p->data << ' ';
    }
    cout << '\n';
}

$ ./foo
Enter in how many numbers you want:4
Enter in what you want
1
2
3
4
The list is: 4 3 2 1
Enter in a number to test: 3
3 is on the list
The reverse list is
The reversed list is: 1 2 3 4
deletion done

[Deadweight77]

Thank you very much mate! My learning process isn't exactly by the books I'm afraid. I usually need to look at a solution and dissect it so thanks you!