CODEWITHSUNDEEP
clinked-list
kachilous
kachilous

Reputation: 2529

Writing linked list functions

The following function exchanges the first node in the list with the second node and returns a pointer to the front of the edited list. If the original list contains fewer than two nodes, no changes are made, and the original pointer to the front of the list will be returned.

This function was written by a professor, but I am having trouble understanding why he sets
list->next = newFront->next.

I understand that he creates a new pointer to equal the address of the second node and the next of that newly created pointer will equal the address of the first node but why is it necessary to set the address of the second node in the original list equal to newFront->next: list->next = newFront->next. Is this step even necessary?

Here is the entire code:

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

struct node* swapFirstTwo(struct node* list) {
     if(list == NULL || list->next == NULL) return list;
     struct node* newFront = list->next;
     list->next = newFront->next;
     newFront->next = list;
     return newFront;
}

Upvotes: 2

Views: 661

Answers (2)

Wyzard
Wyzard

Reputation: 34563

list is the (original) first item in the list and newFront is the (original) second. Assigning
list->next = newFront->next gets the pointer to the third item in the list, and stores it into what used to be the first item, since it's now going to be the second item. Without that step, you'd end up with the two nodes pointing to each other, and the remainder of the list would be lost.

Upvotes: 0

Mac
Mac

Reputation: 14791

Setting list->next = newFront-next ensures that the third element in the list (if there is one), and hence all following elements, is correctly linked with list, which has become the second element.

Say there was originally 3 elements in the list, element1, element2 and element3. Your list looks like this:

element1 => element2 => element3

You set newFront = list->next, which is element2 since list = element1, which effectively moves element2 to the start. Then, to prevent element3 "falling off", you need to set element1->next to element2->next (which is now the same as newFront->next) to get the following:

element2 (i.e. newFront) => element3
element1 (i.e. list) => element3

This means that the element that's now going to be second in the list (element1 a.k.a. list) correctly points to the third element in the list. The only thing remaining is to actually make element1 the second item in the list, which is achieved by setting newFront->next to list, which is in fact element1. So you now have:

element2 (i.e. newFront) => element1 (i.e. list) => element3

Note that whatever element3 links to is unaffected, so this still works just fine even if there are four or more elements in the list.

Upvotes: 2

Related Questions