sorting linked list implementation, getting the same list

Question

I'm trying to implement a bubble sort on a linked list. However, I get access errors:

Unhandled exception at 0x001A8C7B in program.exe: 0xC0000005: Access violation reading location 0xCCCCCCCC.

This error occur in my bubble sort method:

if (current->data > nextElement->data)

call in main

list1.SortList();

struct

struct IntNode
{
    int data;
    IntNode * next;
};

bubble sort

void NodeSLList::SortList()
{
    if (head == NULL || head->next == NULL)
        return;

    IntNode * current = head;
    IntNode * nextElement = current->next;
    IntNode * temp = NULL;

    int changed = 1;


    while (changed)
    {
        changed = 0;
        for (current; current != NULL; current = current->next)
        {
            if (current->data > nextElement->data) //ACCESS ERROR
            {
                temp = current;
                current = nextElement;
                nextElement = temp;
                changed = 1;
            }
            nextElement = nextElement->next;
        }

    }

}

I changed the inside of the loop to:

for (current; (current != NULL) && (nextElement = NULL); )
{
    if (current->data > nextElement->data)
    {
        temp = current->next;
        current->next = nextElement->next;
        nextElement->next = temp;
        changed = 1;
    }
    current = current->next;
    nextElement = nextElement->next;
}

However, my list continues to output the same list.

Barry · Accepted Answer · 2014-11-15 20:57:05Z

2

You need to check if nextElement is NULL too. Consider a list of two elements:

A --> B --> NULL

On your first iteration through the while loop, first you'll have current == A and nextElement == B... and then you'll have current == B and nextElement == NULL, which you will still try to grab data off of, hence your access violation.

Just change your loop condition from:

for (current; current != NULL; current = current->next)

to

for (current; current != NULL && nextElement = NULL; current = current->next)

And maybe even move the nextElement = nextElement->next into the loop line too, for added clarity.

That solves your access violation, but it doesn't solve your "loop isn't actually sorting" problem. That's because you're not actually changing anything in your loop. Consider the above loop again and assume it's backwards and you need to switch it:

A --> B --> NULL
^     ^
crt   next

After your swap, you will end up with

A --> B --> NULL
^     ^
next  current

You successfully swapped the pointers, but you didn't actually change the list ordering. What you do need to change are the next pointers. Specifically, three of them: current's, nextElement's, and current's parent's.

answered Nov 15, 2014 at 20:57

Barry

312k32 gold badges734 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2577345 Over a year ago

I changed the inside of the for loop to : temp = current->next; current->next = nextElement->next; nextElement->next = temp; however the list is still the same.

Barry Over a year ago

@user2577345 You changed two next pointers, you have to change three.

Venkatesh · Accepted Answer · 2014-11-15 20:57:51Z

0

 for (current; current != NULL; current = current->next)

Here current may point to the last node, at this point nextElement = NULL.

so nextElement->data is invalid.

answered Nov 15, 2014 at 20:57

Venkatesh

1,57716 silver badges29 bronze badges

Collectives™ on Stack Overflow

sorting linked list implementation, getting the same list

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related