Looking for terminology.

Hi,

I was learning about linked lists and while writing a sort function for a linked list, I came across the following for the swapping of the data:

Code:

---

                int temp = t1->x;
                t1->x = (t1->next)->x;
                (t1->next)->x = temp;

---

I think being able to access a variable from the next pointer of a node is awesome. But what is this called when you do this? Does this have a name?

Ty.

> But what is this called when you do this?
Dumb.

Well, no, that's not what it's called, it's just called dereferencing.

It's dumb because the thing you should be swapping over are the pointers (which are small and finite size, typically taking just a few instructions).

Swapping the data could be 100's of times slower because you end up with lots of memcpy's all over the place if your data is of any complexity (ie, more than a single int).

Quote:

---

Originally Posted by Salem

It's dumb because the thing you should be swapping over are the pointers (which are small and finite size, typically taking just a few instructions).

---

I'm struggling with the pointer swapping. My first try at sorting a linked list, I emptied the data into an array, sorted the array, and repopulated the linked list. That seemed cumbersome. I'll try to swap the pointers today.

Also, if anybody cares, the "Singly linked lists in C" tutorial, in the first code sample, someone is teaching people to type cast the pointer from malloc. I only point this out because it seems, "You don't type cast the results from malloc" is one of the first comments offered when someone posts similar code here on the forums. :)

Get out the paper and pencil, and doodle.

You logically have three temporary pointers which follow each other down the linked list (called Prev, Curr and Next).

Code:

---

.
  P            C            N     
  +=+          +=+          +=+          +=+ 
  |a|--------->|s|--------->|d|--------->|f| 
  +=+          +=+          +=+          +=+

---

If you want to swap over Curr and Next, then you need three assignments.

Code:

---

.
      +--------(1)------+ 
  P  |        C        |  N 
  +=+  |      +=+      |  +=+          +=+ 
  |a|--+    +->|s|--+    +->|d|--+    +>|f|
  +=+      |  +=+  |      +=+  |    | +=+ 
            |      |            |    |   
            +-------|-----(3)----+    | 
                    |                  |           
                    +--------(2)-------+


Prev->next = Next;        // 1
Curr->next = Next->next;  // 2
Next->next = Curr;        // 3

---

The last step would be to reset Curr and Next to be their respective new nodes before progressing.