Single Linked List - reverse order/sorting.

[Maartin]

Hi there. I'm trying to make a program that:
From: Pineapple->Apple->Ash->Abc->Pearl->Bonfire->Ball (input)
Turns into: Abc->Ash->Apple->Ball->Bonfire->Pearl->Pineapple
1) It sorts alphabetically (only after first char)
2) Prints out reverse order: - Still alphabetically after first char, but the first input is last, and the last one is first. (Example: At first - (Apple-Ash-Abc) After - (Abc-Ash-Apple). I hope you got my point, because my english isn't great.
I've to use linked lists!
I've working function, that sorts strings after first char:

void List::add_element (string city)
{
     Node *p = new Node (city);
     //case 1 - empty
     if (first == NULL) first = p;
     else{
     current = first;
     Node* trail = NULL;
     // Traverse list to find insertion location
     while(current != NULL)
        {
          if (current->data.at(0) > p->data.at(0)) break;
          else trail = current; current = current->next;
        }
     //case 2 - insert at the head
     if (current == first)
     {
        p->next = first;
        first = p;
     }
     // case 3 - after the head
     else{
        p->next = current;
        trail->next = p;
     }
     }
};

And function that prints out reverse order - also working (but prints reverse whole list - what I do not need - check again examples)

 void reversedLinkedList()
    {
    if(first == NULL) return;

    Node *prev = NULL, *current = NULL, *next = NULL;
    current = first;
    while(current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // now let the head point at the last node (prev)
    first = prev;
    }

I'm pretty sure I've to combine both functions, so this works, but I've no clue how to do it. Any help will be perfect.

Whole program code:

#include <iostream>
#include <string>


using namespace std;
class Node
{
    public:
    string data;
    Node *next;
    Node (string city) { data = city; next = NULL; };
};
class List
{
    protected:
        Node *first, *last;
    public:
        Node *current;
    public:
        List () { first = last = current = NULL; };

     void add_element (string city); // Sorted
     void delete_element ();
     ~List();

     bool is_empty () { return (first == NULL); };
     void start () { current = first; };
     bool end () { return (current == NULL); };
     void next(){if (!end())current = current -> next;};
     void print();


    void reversedLinkedList()
    {
    if(first == NULL) return;

    Node *prev = NULL, *current = NULL, *next = NULL;
    current = first;
    while(current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // now let the head point at the last node (prev)
    first = prev;
    }


};




int main()
{
    string s = "spple";
    List l;


    l.add_element("Pineapple");
    l.add_element("Apple");
    l.add_element("Ash");
    l.add_element("Abc");
    l.add_element("Apple");
    l.add_element("Pearl");
    l.add_element("Bonfire");
    l.add_element("Ball");

   // Apple, Abc, Ash, Apple   ;   Ball, Bonfire   ;   Pearl, Pineapple

    cout << "Normal: " << endl;
    l.print();
    l.reversedLinkedList();
    cout << "Reversed: " << endl;
    l.print();




    return 0;
}

void List::add_element (string city)
{
     Node *p = new Node (city);
     //case 1 - empty
     if (first == NULL) first = p;
     else{
     current = first;
     Node* trail = NULL;
     // Traverse list to find insertion location
     while(current != NULL)
        {
          if (current->data.at(0) > p->data.at(0)) break;
          else trail = current; current = current->next;
        }
     //case 2 - insert at the head
     if (current == first)
     {
        p->next = first;
        first = p;
     }
     // case 3 - after the head
     else{
        p->next = current;
        trail->next = p;
     }
     }
};




void List::delete_element ()
{
     Node *p = first;
     if(!is_empty())
     { if (current == first) current = first-> next;
     first = first -> next;
     delete p;
     if(is_empty())last = NULL;
     }
};
void List::print()
{
    for (start(); !end(); next())
    {
    cout << current->data << endl;
    }
    cout << endl;

};




List::~List()
{
    while (!is_empty())
 {
   delete_element();
 };
 cout << "Whole memory deleted!"<< endl;
};

[keskiverto]

It does seem like you should conceptually have a list of "buckets". One bucket per unique initial. Your input has initials {P, A, B}. Furthermore, the buckets should be ordered according to the initials {A, B, P}.

Each new value (a word) is added to appropriate bucket, and within the bucket they maintain the order of insertion (each bucket has a list of words).

It is probably more logical to insert new buckets in order, so that the list of buckets is always sorted.

With such data structure it is easy to iterate over the buckets (i.e. sorted), and within each bucket show items in reverse order.

If you want to do that with lists, then you do need a second list type. A list of Buckets. Perhaps with:

struct Bucket {
  const char initial;
  List list;
  Bucket * next;
  // other code
};

Note that reversing a list and simply showing the elements of a list in reverse are different.
The first changes the list and shows nothing.
The second does not change the list, but shows the elements.

[Maartin]

As I try to vision that, I see that more difficult than the way I was thinking at first. Maybe I just didn't get it exactly. Could you write more code or comments about your idea?
And.. Is there any possible way to only use a list - like a I've (or more, if needed) to finish the task with what I've? Thanks for reply.