Thread: Looking for terminology.

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    114

    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.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2019
    Posts
    114
    Quote Originally Posted by Salem View Post
    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.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Terminology
    By r_james14 in forum C Programming
    Replies: 4
    Last Post: 11-24-2011, 09:37 AM
  2. terminology
    By h_howee in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 05-04-2007, 09:36 PM
  3. Thinking about terminology
    By SlyMaelstrom in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 02-25-2006, 07:42 AM
  4. Pointer Terminology Question
    By SourceCode in forum C Programming
    Replies: 2
    Last Post: 03-07-2003, 09:11 AM
  5. Error in terminology in Code Journal
    By SilentStrike in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 01-23-2002, 11:04 AM

Tags for this Thread