Вставить узлы в списке в Связанный список?

Question

Я пытаюсь написать функцию-член, Link* add_ordered (Link* n), которая добавляет узел в лексикографическом порядке в списке, однако, когда я пытаюсь распечатать упорядоченный список, печатается только последний добавленный узел, то есть "Poseidon".

Вот как мой интерфейс узла выглядит следующим образом:

struct God { 
    // public members of God 
    std::string name; 
    std::string mythology; 
    std::string vehicle; 
    std::string weapon; 

    // constructor 
    God (std::string n, std::string m, std::string v = " ", std::string w = " ") 
     : name(n), mythology(m), vehicle(v), weapon(w) { } 
}; 
//------------------------------------------------------------------------ 

class Link { 
public: 
    God god; 

    // consructor 
    Link (God g, Link* p = 0, Link* s = 0) 
     : god(g), prev(p), succ(s) { } 

    // modifying member functions 
    Link* insert (Link* n); 
    Link* add (Link* n); 
    Link* add_ordered (Link* n); 
    Link* erase (void); 
    Link* find (const std::string& v); 

    // non - modifying member functions 
    Link* advance (int n); 

    const Link* find (const std::string& n) const; 

    Link* previous() { return prev; } 
    Link* next() { return succ; } 

private: 
    Link* prev; 
    Link* succ; 
}; 

член функция используется в add_ordered():

Link* Link::insert (Link* n) { 

    if (n == 0) return this; 
    if (this == 0) return n; 

    n->succ = this; 
    n->prev = prev; 

    if (prev) prev->succ = n; 

    prev = n; 

    return n; 
} 

Наконец, здесь есть функция, которая выполняет сортировку узлов:

Link* Link::add_ordered (Link* n) { 

    // check if nodes valid 
    if (n == 0) return this; 
    if (this == 0) return n; 

    // pointer to this object 
    Link *p = this; 

    // order in lexicographically increasing order in terms of link's god's name 
    while (p) { 

     // if new node value smaller than the one in current node, insert before current node. 
     if (n->god.name < p->god.name){ 
      insert(n); 
      break; 

     // otherwise go to previous node in the list 
     } else { 
      p = prev; 
     } 
    } 

    // return the newly added, ordered Link 
    return n; 
} 

Вот как я пытаюсь создать упорядоченный двойной список:

int main() { 

    // God(name(n), mythology(m), vehicle(v), weapon(w)) 
    // Greek mythology list of Gods 

    Link* greek_gods = new Link(God("Zeus", "Greek", "", "lightning")); 
    greek_gods = greek_gods->add_ordered(new Link(God("Hera", "Greek"))); 
    greek_gods = greek_gods->add_ordered(new Link(God("Athena", "Greek"))); 
    greek_gods = greek_gods->add_ordered(new Link(God("Ares", "Greek"))); 
    greek_gods = greek_gods->add_ordered(new Link(God("Poseidon", "Greek"))); 

    // print the list 
    std::cout <<"{"; 

    while (greek_gods) { 

     std::cout << greek_gods->god.name <<", " 
       << greek_gods->god.mythology <<", " 
       << greek_gods->god.vehicle <<", " 
       << greek_gods->god.weapon; 

     // I've tried both directions, using greek_gods->next() 
     if (greek_gods = greek_gods->previous()) std::cout <<'\n'; 
    } 

    std::cout <<"}"; 
} 

Я пробовал какое-то время, чтобы заставить его работать, безуспешно, поэтому любая помощь будет высоко оценена. Я действительно не вижу, что не так с add_ordered().

---

P.S. Если я создаю тот же список, используя add() или insert(), весь список будет напечатан отлично.

Answer 1

Основываясь на замечаниях @Frerich Raabe, функция add_ordered() была изменена так, что всегда возвращает начальный узел списка. Кроме того, новый условный, if, оператор добавил проверить, является ли новый узел уже в порядке и добавить его в передней части списка, если так:

Link* Link::add_ordered (Link* n) { 

    // check if nodes valid 
    if (n == 0) return this; 
    if (this == 0) return n; 

    // pointer to this object 
    Link *p = this; 

    // if node already in order, add it in front of the list 
    if (n->god.name < p->god.name) { 
     add(n); 

     // return current first node of the list 
     return n; 
    } 

    // traverse existing list till new node's name smaller than current node's 
    while (!(n->god.name < p->god.name) && p) { 

     // previous node 
     Link* temp = p; 

     // if last node's name is smaller than new node's, add new at the end 
     if (!(p = p->prev)) { 
      n->prev = nullptr; 
      n->succ= temp; 

      temp->prev = n; 
      return this; 
     } 
    } 

    // add n in front of current node 
    n->succ = p->succ; 
    n->prev = p; 

    if (p->succ){ 
     p->succ->prev = n; 
    } 

    p->succ = n; 

    // return current first node 
    return this; 
} 

Answer 2

Link::add_ordered всегда возвращает свой аргумент (или this в случае, если аргумент равен null, эта ветка не выполняется в вашем случае). Таким образом, все

greek_gods = greek_gods->add_ordered(new Link(God("Hera", "Greek"))); 

линии в вашей программе будет постоянно делать greek_gods пункт вставленной ссылки.