Trying to swap 2 adjacent nodes in a linked list in plain C without double pointers

Question

[ WOW - Someone gave me and negative point for my question ] [ You could at least put a comment why you did not like my question ]

I am stuck. I remember doing something similar in C++ but for some reason, I can't get it to work in plain C.

I'm trying to swap 2 nodes in a singly linked list.

The starting list is populated as [9,8,7,5,3,2] and I'm trying to bubble sort it, 2 nodes at a time to final list of [2,3,5,7,8,9]

The first iteration(swap) works find with the head. The list returns perfect with [8,9,7,5,3,2] ...but in the second iteration, I loose the 7 and get [8,9,5,3,2] which is WTF and I tried changing the code a bit but I have lost hope.

Can someone actually find what I did wrong. Please no double pointers... if it's only possible with double pointers... Why and How? since I have no idea what are double pointers?

Here is my program so far:

/*
    ___ENTER TITLE HERE___
    Author : Patrick Miron
    Date : Oct 20, 2021
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct listNode
{
    int data;
    struct listNode *next;
} listNode;

typedef struct list
{
    struct listNode *head;
    struct listNode *tail;
} list;

int isEmpty( const list *l) 
{
    return (l == NULL);
}

void printList(list *ptrToList, char *title)
{
    int counter = 0; //Counter to count the listItem printed so we can add a carriage return at each 5th element.
    printf("%s\n", title);
    listNode *ptrToCurrentItem = ptrToList->head;
    while (ptrToCurrentItem != NULL)
    {
        counter++;
        printf("%d", ptrToCurrentItem->data);
        if (counter % 5 != 0)
        {
            printf(" : ");
        }
        else
        {
            printf("\n");
        }
        ptrToCurrentItem = ptrToCurrentItem->next;
    }
}

list *createListWithHeadData(int data)
{
    list *ptrList = malloc((sizeof(ptrList)));
    listNode *ptrNewNode = malloc(sizeof(listNode));
    ptrNewNode->data = data;
    ptrList->head = ptrNewNode;
    ptrList->tail = ptrNewNode;
    return ptrList;
}

void addToFrontList(list *ptrList, listNode *ptrListNode)
{
    listNode *tempPtr = ptrList->head;
    ptrList->head = ptrListNode;
    ptrListNode->next = tempPtr;
}

list *arrayToList(int data[], int size)
{
    list *ptrToNewList = createListWithHeadData(data[0]);
    for (int i = 1; i < size; i++)
    {
        listNode *ptrToNewListNode = malloc(sizeof(listNode));
        ptrToNewListNode->data = data[i];
        addToFrontList(ptrToNewList, ptrToNewListNode);
    }
    return ptrToNewList;
}

int count(listNode *ptrToHead)
{
    if (ptrToHead == NULL)
    {
        return 0;
    }
    else
    {
        return (1 + count(ptrToHead->next));
    }
}

void concat(listNode *head1, listNode *head2)
{
    assert(head1 != NULL);
    if (head1->next == NULL)
    {
        head1->next = head2;
    }
    else
    {
        concat(head1->next, head2);
    }
}

void insert(
    listNode *p1, // first element
    listNode *p2, // second element
    listNode *q) // new element to insert between first and second element
    {
        assert(p1->next == p2);
        p1->next = q;
        q->next = p2;
    }

void delete(listNode *listNode)
{
    assert(listNode != NULL);
    listNode = NULL;
}

void deleteList(list *list)
{
    if (list->head != NULL)
    {
        list->head = list->head->next;
        deleteList(list);
    }
}

void swapListNodeWithNext(listNode *ptrToListNode1)
{
    //Swap items
    listNode *ptrTempNode1 = ptrToListNode1->next;
    listNode *ptrTempNode2 = ptrToListNode1->next->next;

    //Set the next node from temp1 (ptrToListNode->next->next) to itself
    //Could be written as ptrToListNode->next->next = ptrToListNode
    ptrTempNode1->next = ptrToListNode1;
    ptrToListNode1->next = ptrTempNode2;
    ptrToListNode1 = ptrTempNode1;

    ptrTempNode1 = NULL;
    ptrTempNode2 = NULL;
}

void sortList(list *ptrToListToSort)
{
    if (ptrToListToSort->head == NULL)
    {
        return;
    }
    listNode *ptrToCurrentItem = ptrToListToSort->head;
    listNode *ptrToLastUnsortedItem = ptrToListToSort->tail;

    while (ptrToLastUnsortedItem != ptrToListToSort->head)
    {
        ptrToCurrentItem = ptrToListToSort->head;
        while(ptrToCurrentItem->next != NULL)
        {
            if (ptrToCurrentItem->data > ptrToCurrentItem->next->data)
            {
                listNode *ptrToHead = ptrToListToSort->head;
                if (ptrToCurrentItem == ptrToListToSort->head)
                {
                    ptrToHead = ptrToCurrentItem->next;
                }
                //Swap items
                swapListNodeWithNext(ptrToCurrentItem);
                ptrToListToSort->head = ptrToHead;
            } 
            else 
            {
                ptrToCurrentItem = ptrToCurrentItem->next;
            }
        }
        ptrToLastUnsortedItem = ptrToCurrentItem;
    }
}

int main(void)
{  
    printf("\n");

    list listOfInt;
    int data[6] = { 2, 3, 5, 7, 8, 9 };
    list *ptrToNewList = arrayToList(data, 6);
    printList(ptrToNewList, "Array to Element List");

    sortList(ptrToNewList);

    printList(ptrToNewList, "Sorted List");

    printf("\n");
    printf("...End of line...\n");
    printf("\n");
    return 0;
}

Answer 1

I found a couple issues but the major one was that I did not change my previous ptr's next ( ptrPreviousItem->next) to point to the correct item after the swap. I was only changing the pointer to current item which was just a copy of the head advancing thru my iterations and the previous->next was still pointing to the original item.

Why in the world did it work for my first iteration? Probably because I would not update the last item since it was in correct order it would not get updated after that.

I have included a correct version of my singly linked list bubble sort with pointers. It works and I hope it can help the next person. Believe me alot of the tutorial on the subject barely make the code more readable then identifiers like "a" and "b"...

Oh, and @chqrlie, I don't understand some of the corrections you made in my previous question, some of them are quite unnecessary the others were formated like that when I put the code in brackets and the * in pointers can be put where you want. int* likeThis; int * likeThis; or int *likeThis. But I do usually format it like you with the asterix right against the identifier. I use a space between them when I mean the dereferenced value. Cheers!

/*
    Singly Linked List Bubble Sort with Pointers
    Author : Patrick Miron
    Date : Nov 17, 2021
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct listNode
{
    int data;
    struct listNode * next;
} listNode;

typedef struct list
{
    struct listNode *head;
    struct listNode *tail;
} list;

int isEmpty( const list *l) 
{
    return (l == NULL);
}

void printList(list *ptrToList, char *title)
{
    int counter = 0; //Counter to count the listItem printed so we can add a carriage return at each 5th element.
    printf("%s\n", title);
    listNode *ptrToCurrentItem = ptrToList->head;
    while (ptrToCurrentItem != NULL)
    {
        counter++;
        printf("%d", ptrToCurrentItem->data);
        if ((counter % 5) != 0 && (ptrToCurrentItem->next != NULL))
        {
            printf(" : ");
        }
        else
        {
            printf("\n");
        }
        ptrToCurrentItem = ptrToCurrentItem -> next;
    }
}

list *createListWithHeadData(int data)
{
    list *ptrList = malloc((sizeof(list)));
    listNode *ptrNewNode = malloc(sizeof(listNode));
    ptrNewNode->data = data;
    ptrNewNode->next = NULL;
    ptrList->head = ptrNewNode;
    ptrList->tail = ptrNewNode;
    
    return ptrList;
}

void addToFrontList(list *ptrList, listNode *ptrListNode)
{
    listNode *tempPtr = ptrList->head;
    ptrList->head = ptrListNode;
    ptrListNode->next = tempPtr;
}

list *arrayToList(int data[], int size)
{
    list *ptrToNewList = createListWithHeadData(data[0]);
    for (int i =1; i<size; i++)
    {
        listNode *ptrToNewListNode = malloc(sizeof(listNode));
        ptrToNewListNode->data = data[i];
        addToFrontList(ptrToNewList, ptrToNewListNode);
    }
    return ptrToNewList;
}

int count(listNode *ptrToHead)
{
    if (ptrToHead == NULL)
    {
        return 0;
    }
    else
    {
        return (1 + count(ptrToHead->next));
    }
}

void concat(listNode *head1, listNode *head2)
{
    assert(head1 != NULL);
    if (head1->next == NULL)
    {
        head1->next = head2;
    }
    else
    {
        concat(head1->next, head2);
    }
}

void insert(
    listNode *p1, // first element
    listNode *p2, // second element
    listNode *q) // new element to insert between first and second element
    {
        assert(p1->next == p2);
        p1->next = q;
        q->next = p2;
    }

void delete(listNode *listNode)
{
    assert(listNode != NULL);
    listNode = NULL;
}

void deleteList(list *list)
{
    if (list->head != NULL)
    {
        list->head = list->head->next;
        deleteList(list);
    }
}

void swapListNodeWithNext(listNode *ptrToCurrentNode, listNode *ptrToPreviousNode)
{
    //Swap items
    listNode *ptrTempNode1 = ptrToCurrentNode->next;
    listNode *ptrTempNode2 = ptrToCurrentNode->next->next;

    //Set the next node from temp1 (ptrToListNode->next->next) to itself
    //Could be written as ptrToListNode->next->next = ptrToListNode
    ptrTempNode1->next = ptrToCurrentNode;
    ptrToCurrentNode->next = ptrTempNode2;
    ptrToCurrentNode = ptrTempNode1;
    if (ptrToPreviousNode != NULL)
    {
        ptrToPreviousNode->next = ptrToCurrentNode;
    }
    ptrTempNode1 = NULL;
    ptrTempNode2 = NULL;
}

void sortList(list *ptrToListToSort)
{
    if (ptrToListToSort->head == NULL)
    {
        return;
    }
    listNode *ptrToCurrentItem = ptrToListToSort->head;
    listNode *ptrToPreviousItem = NULL;
    int sizeOfList = count(ptrToListToSort->head);
    int innerLoopCounter = 0;
    int unsortedElementLeft = sizeOfList;
    listNode *ptrToHead = ptrToListToSort->head;
    int swappedAtLeastOneItem = 0;

    for (int indexOuterLoop = 0; indexOuterLoop < sizeOfList; indexOuterLoop++)
    {
        ptrToCurrentItem = ptrToListToSort->head;
        while((ptrToCurrentItem->next != NULL) && (innerLoopCounter < unsortedElementLeft))
        {
            // If the data in the next item greater then the current item, swap nodes.
            if (ptrToCurrentItem->data > ptrToCurrentItem->next->data)
            {
                swappedAtLeastOneItem = 1;
                // If the current item is the head of the list, and since it will be swap, point to the next item.
                if (ptrToCurrentItem == ptrToListToSort->head)
                {
                    ptrToHead = ptrToCurrentItem->next;
                }
                //Swap items
                swapListNodeWithNext(ptrToCurrentItem, ptrToPreviousItem);
                //if the ptrToHead has changed, then update the changes.
                if (ptrToListToSort->head != ptrToHead)
                {
                    ptrToListToSort->head = ptrToHead;
                }
            } 
            // if the nodes do not need to swap, make sure to update the current item and previous items.
            else 
            {
                if (ptrToCurrentItem->next != NULL)
                {
                    ptrToCurrentItem = ptrToCurrentItem->next;
                }
            }
            if (ptrToPreviousItem != NULL)
            {
                ptrToPreviousItem = ptrToPreviousItem->next;
            }
            else
            {
                ptrToPreviousItem = ptrToHead;
            }
            innerLoopCounter++;
        }
        // If during the first loop no items were swap then exit early all items are already in order.
        if (!swappedAtLeastOneItem) 
        {
            printf("**List is already sorted!**\n");
            return; 
        }
        unsortedElementLeft--;
        innerLoopCounter=0;
        ptrToPreviousItem = NULL;
        if (ptrToCurrentItem->next == NULL)
        {
            ptrToListToSort->tail = ptrToCurrentItem;
        }
    }
}

int main(void)
{  
    printf("\n");

    int data1[6] = {2,3,5,7,8,9};
    list *ptrToNewList = arrayToList(data1,6);
    printList(ptrToNewList, "Array to Element List");
    sortList(ptrToNewList);
    printList(ptrToNewList, "Sorted List");
    printf("\n");
    printf("----------------------------\n");
    printf("\n");

    int data2[8] = {10,11,2,3,5,7,8,9};
    ptrToNewList = arrayToList(data2,8);
    printList(ptrToNewList, "Array to Element List");
    sortList(ptrToNewList);
    printList(ptrToNewList, "Sorted List");
    printf("\n");
    printf("\n");
    printf("----------------------------\n");
    printf("\n");

    int data3[10] = {10,11,2,3,5,7,8,1,9,1};
    ptrToNewList = arrayToList(data3,10);
    printList(ptrToNewList, "Array to Element List");
    sortList(ptrToNewList);
    printList(ptrToNewList, "Sorted List");
    printf("\n");    
    printf("\n");
    printf("----------------------------\n");
    printf("\n");

    int data4[10] = {1,1,1,1,1,1,1,1,1,1};
    ptrToNewList = arrayToList(data4,10);
    printList(ptrToNewList, "Array to Element List"); 
    sortList(ptrToNewList);
    printList(ptrToNewList, "Sorted List");
    printf("\n");    
    printf("\n");
    printf("----------------------------\n");
    printf("\n");

    int data5[10] = {21,19,16,13,10,9,6,2,1,1};
    ptrToNewList = arrayToList(data5,10);
    printList(ptrToNewList, "Array to Element List");
    sortList(ptrToNewList);
    printList(ptrToNewList, "Sorted List");
    printf("\n");    
    printf("\n");
    printf("----------------------------\n");

    printf("\n");
    printf("...End of line...\n");
    printf("\n");
    return 0;
}

Please note, I did not finish my commenting so don't judge me, I always complete it last.

Hope this helps for anyone having similar issues to me.