Reverse function for linked list
I have the following code example that creates a linked list:
Code:
#include <iostream.h>
/* Here is our Node (our structure) that contains the information
we want along with a memory address to the next Node on the list.
When the list is empty, our there is no next. In fact, there is
no Node at all, as you will see in a moment.
*/
class Node
{
public:
int x; /* The information we really want to store. */
Node *next;/* The address to the next Node in the list. */
Node() { next = NULL; } /* Start of with no next Node. */
/* Here, we want to get rid of the next Node before getting rid of
this one. Why? It's a tricky way to get rid of all the nodes, by
simply getting rid of the first once. Think "chain-reaction".
*/
~Node() { if (next != NULL) delete next; }
};
/* Here is our List, which manages all the Nodes. using the List
interface, we can add nodes, remove nodes, or print out the nodes
that are in the list.
*/
class List
{
/* The "head" is a variable that points to the first node in our
list. Keep in mind, "head" isn't a Node itself. It's just the
memory address of the first actual node. In the beginning, when
there are no items in our list, "head" doesn't have an address
and that means head = NULL.
*/
Node *head;
/* The "tail" is similar to the "head" except it has the memory
address of the last actual node. It's not a necessary variable,
but it's handy for adding elements because we don't have to
go through the entire chain to find the last element in our
list.
*/
Node *tail;
/* The size of the list will be the number of elements in it. It's
not really necessary, just something that might come in handy.
*/
int size;
public:
List() { size = 0; head = NULL; tail = NULL; }
/* Deleting the head removes ALL the links in the linked list. Why?
Think "chain-reaction". The head doesn't disappear until head's
"next" variable disappears, which doesn't disappear until it's own
"next" variable disappears, and so on...
*/
~List() { delete head; }
/* Some typical linked list functions */
void add(int x);
void del(int x);
void reverse();'//reverse a list
void print();
};
/* How do we add an element to a linked list? We create a new Node using
new Node (hmm, C++ syntax makes sense I guess). We give it the data
we want (in this case, just a number). Then, we make the tail's "next"
variable (which is the last element on the list) be the temp Node.
We have to take care of the special case when this is the first node
on the list, otherwise "head" won't be have any "next" address (that is,
"head" won't be pointing to anything).
*/
void List::add(int x)
{
Node *temp;
temp = new Node;
temp->x = x;
if (size == 0) {
head = temp;
tail = temp;
} else {
tail->next = temp;
tail = temp;
}
/* Our list is now one size bigger. */
size++;
cout << "List::add(" << temp->x << ")." << endl;
}
/* How do we delete an element from a linked list? Well, for this
procedure, think "heart bypass surgery". We have a chain of Nodes
like this:
A --> B --> C --> D --> E --> Null
and to delete C, we would simply have B point to D. So we have
A --> B C --> D --> E --> Null
||
\-----------/
and C is no longer part of the chain. Still, we should get rid of
the memory allocated for C, and we do that using the delete
keyword in C++.
Note: Before we can delete C, we need to let C's "next" variable
be NULL. Why? Remember, C won't disappear until C's "next" also
disappears, and so on, and we'll end up getting rid of D and E as
well. That's not what we want.
A --> B --------> D --> E --> Null
*/
void List::del(int x) {
Node *temp = head, *prev = head;
for (int i=0; i<size; i++)
{
if (temp->x == x) {
prev->next = temp->next;
if (head == temp)
head = temp->next;
temp->next = NULL;
delete temp;
i = size;
}
else {
prev = temp;
temp = temp->next;
}
}
size--;
cout << "List::del(" << x << ")." << endl;
}
void List::reverse() {
/*Node *temp;
temp = head;
cout << "List size: " << size + 1 <<endl;
Node *reverse(Node *x) {
Node *current = x;
Node *previous = NULL;
while (current != NULL) {
Node *next = current->next;
current->next = previous;
// switch to new node
previous = current;
current = next;
}
return previous;
}*/
}
/* How do we print out all of the elements in the list?
One way to do it, is with a single loop. Use a temporary
variable, which is reassigned to have the value which it's own
"next" variable has, during each loop.
Run the program to see what the output looks like.
*/
void List::print()
{
Node *temp;
temp = head;
cout << "List::print() output: ";
do {
cout << "[" << temp->x << "] --> ";
temp = temp->next;
} while (temp != NULL);
cout << "NULL" << endl;
}
/* And here is the great main function. We just do a few simple
operations on the list, to try out the creation. It's nothing
really special. Then again, I've always thought that the
most precious things in life are the simple things in life.
*/
int main(void)
{
List list;
list.add(1);
list.add(2);
list.add(3);
list.print();
list.del(3);
list.print();
//list.reverse();
list.print();
cout << "Done, press enter." << endl;
char c;
cin >> c;
return 0;
}
Everything works except for the reverse function. Any ideas what I might do here?
