Thread: Reverse function for linked list

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    26

    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?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Create a removeFromHead function to complement your addToHead function.

    Then reverse is simply
    while ( node = old.removeFromHead ) new.addToHead( node );
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  3. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM