Why can't I get my pointer based linked list bubble swap to work?

Question

class Node {
    
    
public:
    int data;
    Node* next;

    Node() { //default constructor
        data = NULL;
        next = NULL;
    }

    Node(int value) {
        this->data = value;
        this->next = NULL;
    }
};

class linkedList {
    Node* head;

public:
    linkedList() {
        head = NULL;
    }

    void insertVal(int val)
    {
        Node* newNode = new Node(val);
        if (head == NULL)
        {
            head = newNode;
            return;
        }
        Node* temp = head; //iterator
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = newNode;

    }

    void deleteAtIndex(int index)
    {
        int listLen = 1;
        if (head == NULL)
        {
            std::cout << "cannot delete from null list\n";
            return;
        }

        Node* temp = head;
        while (temp != NULL)
        {
            temp = temp->next;
            listLen++;
        }
        
        if (index > listLen)
        {
            std::cout << "deletion index out of bounds\n";
        }

        temp = head;
        if (index == 1)
        {
            head = head->next;
            delete temp;
            return;
        }

        Node* temp2 = NULL;

        while (index-- > 1)
        {
            temp2 = temp;
            temp = temp->next;
        }
        temp2->next = temp->next;
        delete temp;
    }

    void print() {
        Node* temp = head;

        if (temp == NULL)
        {
            std::cout << "no printo from listo emptyo\n";
            return;
        }
        while(temp != NULL)
        {
            std::cout << temp->data << std::endl;
            temp = temp->next;
        }
    }

    void bubbleSort()
    {
        if (!head || !head->next) // checks if list is empty or singleton
        {
            std::cout << "already sorted\n";
            return;
        }

        bool swapped; // checks if a pass occured with no swaps

        Node* current;
        Node* lastSorted = NULL;

        do {
            swapped = false;
            current = head;

            while (current->next != lastSorted)
            {
                if (current->data > current->next->data)
                {
                    Node* temp = current->next;
                    temp->next = current;
                    temp->next->next = current->next->next; // AAAAAARRRRRRRRRRRRRRRRRGHHHHHHHHHHHHHHH!!!!!!!

                    
                    current = temp;
                }
                current = current->next;
            }
        } while (swapped);
    }
};

I have set up the linkedlist node based but when I go to print a swapped list I feel like my swapping algorithm is just deleting the whole list? It won't print anything at all, not even initial elements of the list that are already sorted.

I tried rewriting the algorithm like 4 times, and I'm completely lost. My professor said for our programming test We would have to make pointer based swapping work but the example which our TAs gave is a value based swap.

Answer 1

Think about how the current pointer changes when you swap. I suggest perhaps you might make out better with two temp pointers, tempA and tempB.

Pointers can be tricky. Draw some pictures of the links as they change with each line of code.

Here's a suggestion: Think about your delete method. How would you insert an item into the list just after a given item pointer in the list? You could swap by deleting the current item and inserting it back after the smaller item.

Minor: lastsorted is never updated, so it acts like an alias for null. Use null when you mean null.

Answer 2

Your program implements a singly linked list. To swap two nodes, you need to keep the track of previous node of current processing node to link it with the node replacing the current node in the list while sorting.

In your bubbleSort() function, you can do:

    do {
        swapped = false;
        Node* current = head;
        Node* prev = nullptr;

        while (current->next != nullptr) {
            if (current->data > current->next->data) {
                swapped = true;
                Node* temp = current->next;
                if (prev) {
                    prev->next = temp;
                } else {
                    head = temp;
                }
                current->next = temp->next;
                temp->next = current;
                current = temp;
            }
            prev = current;
            current = current->next;
        }       
    } while (swapped);

Additional:

1). In your default constructor, you are assigning NULL to a int type variable:

        data = NULL;

Compiler must be throwing warning on it. You don't need default constructor at all. So, either remove it or if you want to keep it, ensure to assign some integer value to data, may be -1.

2). Use nullptr instead of NULL.