An explanation (instead of code). the canonical example of a linked list: head -> node1 -> node2 -> node3 -> NULL Starting at the first node of the list, look at the current node and the next node. If the two nodes are not in the correct order, swap them. Continue this until you reach the […]
Written on Thursday, July 17th, 2008 by marymoreno :: 0 comments to this post
An explanation (instead of code).
the canonical example of a linked list:
head -> node1 -> node2 -> node3 -> NULL
Starting at the first node of the list, look at the current node and the next node. If the two nodes are not in the correct order, swap them. Continue this until you reach the end. The end node will have NULL as the next pointer.
If you swapped any items at all, go back to the beginning of the list and do it all again.
Swapping can involve two different methods. If the stored item is small, such as a single integer, it’s easier to just swap the integer value;s.
temp = node1.value;
node1.value = node2.value;
node2.value = temp;
If the item is larger, it’s faster to change the pointers instead of the values.
In the original example, if we want to swap node1 and node2, we need to change the head pointer, node1.next and node2.next.
before swap
head == &node1;
node1.next = &node2;
node2.next = &node3;
I’ll let you figure out the actual swap code
after swap
head == &node2;
node1.next = &node3;
node2.next = &node1;
Now the list looks like this:
head -> node2 -> node1 -> node3 -> NULL
Post Comments Here » 0 comments to this post
Check the Categories below for more on Could someone please explain how to bubble sort a linked list on c++???
More from Uncategorized(t) Categories
« conundrum!? :: would ballet cds work? an answer required please!!!? »
