Writing linked list functions

Question

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;
}

You already understand this for lists with zero or one element: now just draw it out for lists with two and three elements and work through it. It's easier to do on paper, so I'm not going to kill myself with ASCII art unless you still can't get it. — Useless
– Useless, Commented Dec 16, 2011 at 13:25

Mac · Accepted Answer · 2011-12-16 13:45:53Z

2

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.

edited Dec 16, 2011 at 13:45

answered Dec 16, 2011 at 13:25

Mac

14.8k11 gold badges65 silver badges83 bronze badges

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

1 Comment

kachilous Over a year ago

thank you for the detailed explanation. it makes a lot more sense now

Matthew Murdoch · Accepted Answer · 2011-12-16 13:51:15Z

0

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.

edited Dec 16, 2011 at 13:51

Matthew Murdoch

31.6k32 gold badges99 silver badges127 bronze badges

answered Dec 16, 2011 at 13:28

Wyzard

34.8k3 gold badges74 silver badges94 bronze badges

Collectives™ on Stack Overflow

Writing linked list functions

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related