1

I have created a singly linked list using structure. The structure holds an integer and a struct pointer next. I am sorting the list in ascending order. I am passing the head pointer to a sorting function. The sorting algorithm is working fine but the change is not reflected when I pass the same head to a display function after sorting. I have also tried using pointer-to-pointer, if that's a recommended solution. Following is a sample code of my program which reproduces the same bug:-

#include<iostream>
class List
{
public:
    struct ListNode
    {
        int Number;
        ListNode *next;
    }*head;

    int TotalNodes;

    List()
    {
        head = NULL;
        TotalNodes = 0;
    }

    void CreateList(int Number)
    {
        ListNode *newNode, *nodePtr;
        newNode = new ListNode;
        newNode->Number = Number;
        newNode->next = NULL;
        ++TotalNodes;

        if(!head)
        {
            head = newNode;
        }
        else
        {
            nodePtr = head;
            while(nodePtr->next) nodePtr = nodePtr->next;
            nodePtr->next = newNode;
        }
    }

    void SortList(ListNode *HEAD, int NODECOUNT)
    {
        int i, Passes = (((NODECOUNT * NODECOUNT) + NODECOUNT) / 2);

        ListNode *nodePtr, *lastNode, *lastNodePREV;

        for(i=0; i <= Passes; i++)
        {
            lastNode = HEAD;
            nodePtr = lastNode->next;
            while(nodePtr->next && lastNode->Number < nodePtr->Number)
            {
                lastNodePREV = lastNode;
                lastNode = lastNode->next;
                nodePtr = nodePtr->next;
            }
            if(lastNode == HEAD)
            {
                HEAD->next = nodePtr->next;
                nodePtr->next = HEAD;
                HEAD = nodePtr;
            }
            else
            {
                lastNodePREV->next = nodePtr;
                lastNode->next = nodePtr->next;
                nodePtr->next = lastNode;
            }
        }

        nodePtr = HEAD;
        while(nodePtr)
        {
            std::cout<<" "<<nodePtr->Number;
            nodePtr = nodePtr->next;
        }
    }

    void Display(ListNode *HEAD)
    {
        ListNode *nodePtr;
        nodePtr = HEAD;
        while(nodePtr)
        {
            std::cout<<" "<<nodePtr->Number;
            nodePtr = nodePtr->next;
        }
    }
};

int main()
{
    List list;

    for(int i=10; i >= 0; i--)
    {
        list.CreateList(i);
    }

    list.Display(list.head); //before sorting

    std::cout<<"\n\n";
    list.SortList(list.head, list.TotalNodes);

    std::cout<<"\n\n";
    list.Display(list.head); //after sorting

    return 0;
}

Output of the above program:-

10 9 8 7 6 5 4 3 2 1 0

0 1 2 3 4 5 6 7 8 9 10

10

I think this has something to do with sorting function creating a copy of the list but then what do I do to edit the same list itself?

Thank you.

PS:- I had also tried returning the pointer but then I had got the error about not being able to convert from ListNode* to List* for the function:-

ListNode* List::SortList(...)
{
    ....
    ....
    return HEAD;
}

called in main() as

list.head = list.SortList(...);

PPS:- The solution to this problem is simply using *&HEAD instead of *HEAD in the arguments of function Sortlist()

PPPS:- I want to clarify one more thing that I am using pass-by-reference because I am dealing with several linked lists in my actual program. This is just a sample of it.

Deepak
  • 33
  • 9
  • The idea of having a container structure like `List` is so you can call things like `list.sort()` or `list.display()`. This mixed object-oriented/procedural style is missing the point. – tadman Sep 03 '17 at 19:23
  • 1
    Have you tried `void SortList(ListNode *& HEAD, int NODECOUNT)`? Agree with tadman and recommend [upgrading your reading material.](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) – user4581301 Sep 03 '17 at 19:26
  • Pass the pointer by reference. – Raindrop7 Sep 03 '17 at 19:27
  • @tadman I am sorry but I didn't understand. Should I use a class within a class instead of structure or I shouldn't use class itself for this program? – Deepak Sep 03 '17 at 19:30
  • @user4581301 WOW! Thanks! That worked. Really grateful to you. PS:- can your comment be marked as solution? Else my question will remain unsolved (technically). – Deepak Sep 03 '17 at 19:32
  • 1
    @Deepak tadman's point is `List` knows the `HEAD` and `NODECOUNT` already so there is no need to pass them in. `List::SortList` can use the `head` and `TotalNodes` member variables and directly modify itself. `void SortList(ListNode *& HEAD, int NODECOUNT)` allows deviant behaviour like `list.SortList(otherlist.head, otherlist.TotalNodes);` where list is sorting a different list's data. – user4581301 Sep 03 '17 at 19:38
  • @user4581301 That's exactly what I'm doing in my actual program :) I am using the same functions for several lists. So now the above code is validated? – Deepak Sep 03 '17 at 19:43
  • The same member function (aka method) works on all `List`s and each `List` knows it's own `head` and `TotalNodes` thanks to the hidden `this` variable. By calling `list.SortList();`, you are effectively calling `SortList(&list);`. Inside `SortList` you can `int i, Passes = (((TotalNodes * TotalNodes) + TotalNodes) / 2);` and the program knows which `List` object's `TotalNodes` to use. This will be be covered in the opening chapters of [any competent C++ text](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) and is what you are taking advantage of in `CreateList` – user4581301 Sep 03 '17 at 19:53
  • @user4581301 I guess you're considering that I have used multiple objects. That's not the case. I have multiple linked lists in the same object. I have used separate heads and node counts for each list. You obviously don't know the objective of my actual program so you can't just assume things, right? :-) You've solved my problem so thank you for that. I'm done now. – Deepak Sep 03 '17 at 20:15
  • This is true. I have to be careful what assumptions I make, but what you describe has what's called in the industry a "bad code smell". It might not be the wrong solution, but it probably is and will be viewed with suspicion. – user4581301 Sep 03 '17 at 20:27
  • My suggestion for multiple linked lists in one object is multiple `List` objects each responsible for exactly one linked list wrapped inside another object. This divides the responsibilities into a List (which can be independently tested and verified) and a List Manager (which can also be independently tested and verified). When you compose larger objects of many smaller objects instead of one big object, bugs can be easily isolated and tested. – user4581301 Sep 03 '17 at 20:34
  • Okay. I a nutshell, what I've done in my program is take a stream of integers from the user, segregate the negative and non-negative (considering 0) integers into two new lists, sort them and then merge them. Hence I required only one object. Again, to prevent you from assuming, I could have directly sorted the main list but that isn't the objective. Anyways, thanks for your time investment and suggestions. I'll always keep them in mind. – Deepak Sep 03 '17 at 21:11

0 Answers0