Linked List nodes reversal

This is a discussion on Linked List nodes reversal within the C++ Programming forums, part of the General Programming Boards category; How do you reverse the nodes in a singly linked list? Here is the struct and a definition of a ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    1

    Exclamation Linked List nodes reversal

    How do you reverse the nodes in a singly linked list?
    Here is the struct and a definition of a function i was working on.
    Code:
    // ptr, passed from main, points to the first node in the linked list
    // i think. In this function i'm trying to reverse the list and print
    // the 'name' members in each node in the reversed arrangement.
    
    ...
    
    struct Elephant {
       string name;
       Elephant* next;
    }; 
    
    ...
    
    void reverse_elephant( const Elephant* ptr )
    {
     const Elephant *temp[50], *curr, *first;
     int x=0;
    
     curr = ptr;
    
     while ( ptr != 0) {
      temp[x++] = ptr;
      ptr = ptr -> next;
      }
     cout << "x= " << x << '\n';
     ptr = curr;
    
     first = ptr = temp[x];
    
     for (int i=x-1; i>0; i--){
       ptr =  ptr -> next = temp[x];
       cout << "Name= " << ptr -> name << '\n';
      }
    
    }
    im lost. I know this is a sorry attempt but i'm out of ideas. Can anyone help?

  2. #2
    Registered User
    Join Date
    Feb 2003
    Posts
    60

    Arrow

    Have you thought about a more object orientated approach?
    Like, a class to manage the list. Say you have LinkedList class, when this class gets some data, it will pass it on to a special type of node (called HeadNode???). HeadNode only knows to pass any data comming to it on the whatever it's myNext pointer is fixed on. At first it will be TailNode. TailNode will know to create a new InternalNode and give it's *this(TailNodes) to the new InternalNode, and return the address of the InternalNode to whoever did the original passing. With this structure you can perform all sorts of tests to decide whether or not to pass data past or place it before InternalNodes. Once they have been sorted, simply walk the list, counting objects as you go, then give each object their respective number. This number can then be used in a loop to iterate them anyway you like. You probably know all this, but I thought I'd post it just in case. I recently learnt about a few different types of linked lists.

  3. #3
    Peace
    Join Date
    Aug 2001
    Posts
    1,510
    Info on this can be found from the link in my signature.

    Singly Linked Lists

    and

    Handled Doubly Linked Lists

    specifically.

    The Handled Doubly Linked List is something of what NickESP is refering to, and is also a solution to your problem. Refer to the section of the main site regarding classes if you dont fully understand whats happening.
    "There's always another way"
    -lightatdawn (lightatdawn.cprogramming.com)

  4. #4
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>How do you reverse the nodes in a singly linked list?
    Just go through the list like you're going to delete each node, but reset the pointers instead :-)
    Code:
    NODE *reverse(NODE *list)
    {
      NODE *temp;
      NODE *current = list;
      NODE *new_head = 0;
    
      while (current != 0)
      {
        temp = current->next;
        current->next = new_head;
        new_head = current;
        current = temp;
      }
    
      return new_head;
    }
    *Cela*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21