Swap position in singly linked list in C

Question

I have been given an assignment to create various methods for a linked list in C. I am stuck on the swap method which just seems to mess up the entire linked list. Does anybody have any advice on where I am going wrong? Cheers!

Here is my code.

int main(int argc, char* argv[])
{
    // A list of  pointers to Reminders 
    const int MAX_ENTRIES = 10;
    int numOfEntries = 0 ;
    reminder_t* pFirst = (reminder_t*) malloc ( sizeof(reminder_t));
    reminder_t* pSecond = (reminder_t*) malloc ( sizeof(reminder_t));
    reminder_t* pThird = (reminder_t*) malloc ( sizeof(reminder_t));
    reminder_t* pStart = NULL;
    if (pFirst != NULL)
    {
        strcpy( pFirst->message, "Mikes Birthday");
        pFirst->dateOfEvent.day= 1;
        pFirst->dateOfEvent.month= 1;
        pFirst->dateOfEvent.year= 2013;
        pFirst->pNext = NULL;
    }

    if (pSecond != NULL)
    {   
        strcpy( pSecond->message, "Als Soccer Match");
        pSecond->dateOfEvent.day= 2;
        pSecond->dateOfEvent.month= 2;
        pSecond->dateOfEvent.year= 2013;
        pSecond->pNext = NULL;
    }

    if ( pThird != NULL)
    {
        strcpy( pThird->message, "School Concert");
        pThird->dateOfEvent.day= 3;
    pThird->dateOfEvent.month= 3;
    pThird->dateOfEvent.year= 2013;
    pThird->pNext = NULL;
}

pFirst->pNext = pSecond;
pSecond->pNext = pThird;
pThird->pNext = NULL;
pStart = pFirst;

printf("\n------Before------\n");
listEntries(pStart);
swapPositonOf(pFirst,pThird);

printf("\n------After-aa-----\n");
listEntries(pStart);

getchar();
return 0;
}

void listEntries(reminder_t * pList) 
{
    printf("\n");
    while (pList != NULL)
    {
            printf("%s\n", pList->message);
        pList = pList->pNext;
    }
}

void swapPositonOf(reminder_t* first , reminder_t* second)
{
    reminder_t* pFirst = (reminder_t*) first;
reminder_t* pSecond = (reminder_t*) second;
reminder_t* temp = second->pNext;

pSecond->pNext = pFirst->pNext;
pFirst->pNext = temp;
temp = pSecond;
pSecond = pFirst;
pFirst = temp;
}

Expected output:

------Before------

Mikes Birthday
Als Soccer Match
School Concert

------After-aa-----
School Concert
Als Soccer Match    
Mikes Birthday

Output:

------Before------

Mikes Birthday
Als Soccer Match
School Concert

------After-aa-----

Mikes Birthday

Answer 1

If you want to swap the content of the list nodes, then it's not hard: you can just do a swap for message and dateOfEvent fields in the two nodes.

But if you want to swap the positions of these nodes (as the name of the function suggests), then you have to pay attention to the pNext data member.
In fact, just swapping the node pointers is not enough.
You need to find the positions of the nodes before first and last, and do something like:

/* reminder_t* beforeFirst, reminder_t* beforeSecond */
beforeFirst->pNext = second;
beforeSecond->pNext = first;

and swap first->pNext and second->pNext.

Moreover, in these list implementations, in general it's important to pay attention to special cases like head node and tail node.

Answer 2

You are not swapping it right, what about the node BEFORE the first node and the node BEFORE the second node?

Answer 3

With a singly-linked list, you cannot directly locate the list element previous to the element you want to swap. You have first, second, and you can directly manipulate them, but you don't have first.prev and second.prev.

You need to traverse your list, and find the nodes which are previous to the two nodes you want to swap (first_previous, second_previous). Then you node swap needs to also swap the next of each of these previous nodes.

reminder_t* first_prev, *second_prev;
first_prev = second_prev = pStart;
reminder_t* iter;
for( iter = pStart; iter; iter=iter->next )
{
    if( iter->next == first ) first_prev = iter;
    if( iter->next == second ) second_prev = iter;
}

You will need to fix the above to handle empty list, one element list, and passing first or second at head of list...

Answer 4

You are not modifying the pNext pointer for the nodes just before first and second nodes.

You need to point the pNext of the node preceding "first node" to "second node" and vice versa.

Suppose the linked list:

Node_A -> Node_B -> Node_C -> Node_D -> Node_E

You have to swap Node_B and Node_D:
Total links to break and form:

1. Old Link: Node_A -> Node_B.... New Link: Node_A -> Node_D
2. Old Link: Node_B -> Node_C.... New Link: Node_D -> Node_C
3. Old Link: Node_C -> Node_D.... New Link: Node_C -> Node_B
4. Old Link: Node_D -> Node_E.... New Link: Node_B -> Node_E

Also remember the corner cases like NULL pointers and consecutive nodes.