Thread: Memory adress as output

  1. #16
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What is the code of the insertTail function?

    Also, did you fix printlist to take a pointer to list_t argument?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  2. #17
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Here is the InsertTail

    Code:
    int insertTail(list_t *list, node_t *node)
    {	
    	node->prev = list->tail;
    	node->next = NULL;
    	list->tail = node;
    	
    	list->size += 1;
    	return 1;
    }
    And I did fix it to take a pointer to list_t

    Code:
    void printlist(list_t* list)
    {
    	node_t *current = list->head;
    	while (current != NULL)
    	{
    		printf("%d ", current->value);
    		current = current->next;
    	}
    	printf("\n");
    }

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Excellent. Now here's what you need to do: take a sheet of paper and a pencil. Pretend that you're executing your insertTail function, but on paper. So you draw a box, and put in 6 for the value. Then you draw an arrow outwards to represent prev and another arrow outwards in the opposite direction to represent next. Then draw two more boxes and label one head and the other tail. You will draw arrows outwards from these to show which nodes are the head and tail of the linked list. At the start, the arrows will point to NULL.

    The idea is that you "execute" your code by drawing (and erasing) arrows and boxes and writing NULL to see what you're missing. This way you understand visually what's going on, and so you can see what you did wrong or omitted. I can easily tell you, but this way you learn it for yourself, and it'll help you when you tackle more complex data structures.

    Make sure you do this step by step. Do not skip anything, and do not draw anything that your code doesn't do. Do one call of insertTail at a time.
    Last edited by laserlight; 02-17-2021 at 08:56 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #19
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Thank you for such a wonderful reply! Im so thankful you are trying to get me to understand the core concept instead of just giving me the answer, I really do so thanks a ton!

    I followed your instructions and did the first functioncall of 6. I hope it's okay im asking so soon but I really want to know im understanding and doing this correctly. (I did this on hand first but just to show what im doing I decided to do it on paint aswell so you can get a better picture of what im doing. The gyazo links are just screenshots of the progression i made in paint.

    Okay so when do our intial call :insertTail(list2,node1) we get this: Screenshot - 99a67af44b64a13bfdf39b574c37d73c - Gyazo

    Then we reach the first line of the insertTail function (node->prev =list->tail) this leads to this: Screenshot - 9de9cf30937574e2c38d024d6185c5b9 - Gyazo This means that node->prev = null

    Second line : (node->next = null) we get this: Screenshot - 08fa87ed706f19bfb8700428283a4df4 - Gyazo Now node->next is equal to null aswell.

    Third line : (list.tail = node) leads to this : Screenshot - 7a785dd256ec2c6179a29913ebe8ab64 - Gyazo Now this sets the node to be the tail of the linked list.

    then on the next line the function just updates the size of the list while just the tail of the linked list is pointing to a node. (the node itself is not pointing back to anything)

    I'll do one more of 7.

    InserTail(list2, node2) we get this: Screenshot - a6f86faf73315e0e0addd8f22d1c5e42 - Gyazo

    first line of the function (node->prev =list->tail) we get this : https://gyazo.com/15f051b0d5427e48d950c8ddac197ef2

    second line (node->next = null) I just realized that this dosent actually do anything since when I created my node in the createNode function I already set it to NULL.

    Third line (list.tail = node) we get this : https://gyazo.com/6546675fcfc3527d1291982565d33b0a the tail of the list now points at the new node.

    and we update the size of the list again.

    Okay I have to admit that I feel rather stupid now. Okay some takeaways i got. My head of the list is actually not pointing to the first node. The value never changes from null. The next pointer is not used at all. Is there anything I missed?
    Last edited by Lax; 02-17-2021 at 09:54 AM.

  5. #20
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Nodes don't have tails. What this does is set the prev pointer of the node to be the tail of the linked list. This means that we're about to make this node the new tail of the linked list.
    Yes, it sets the node's next pointer to be a null pointer. Think about it: if a node has no next node, then it must be the tail of the linked list. It cannot be the head of the linked list, unless the linked list has only one node.
    I Totally missed these replies. This does give me some more context. If I would redraw the steps again it would look this in my mind:

    We start like this again: Screenshot - 99a67af44b64a13bfdf39b574c37d73c - Gyazo (I forgot to make the next and prev null pointers)

    First line executes(node->prev = list->tail): Screenshot - 54f8e728f0d41e1b1cca39200773ab45 - Gyazo now the prev pointer is set to be the tail of the list.

    second line executes(node->next = null) : Nothing happens here? because the next pointer was already set to null in the createNode function. I might be wrong here so correct me if im wrong.

    third line executes (list->tail = node) :Screenshot - e7e733dfc512a880ab53ebdd8ead412e - Gyazo This line make the node be the tail of the linked list.

    then we increment the size by one and return 1;

    We execute the other insertTail statement(insertTail(list2, node2)) : Screenshot - 3715848b9ebe36b74bbe14c764e582a8 - Gyazo I set both the next and prev to NULL since that happens when the node gets passed into createNode. Again correct me if im wrong on this one.

    first line again: (node->prev = list->tail) : Screenshot - 26d2a4ca54fe5e258979005b010f4c55 - Gyazo The prev pointer is set to the tail of the list aswell.

    second line again(node->next = NULL) : same reasoning as I had on the previous second line.

    third line again (list->tail = node) : https://gyazo.com/d5312175c81cee58e76af989af7db096 The newest node is now the tail of the list.

    Alright some thoughts and observation. As I mentioned in my most recent post (which I think was wrong) The head pointer is still a NULL pointer when I think it should point to the first element in list. The first node's prev pointer is still pointing at the tail when it should be dereferenced to the new node. The new node's next value is pointing at NULL when it should be pointing at the older node (6). Oh and the older node's next pointer should probably also point to the head and not to NULL. This is a screenshot on how I think it should look: https://gyazo.com/9f53535cb7b98cb7191d9f77526a1f12
    Last edited by Lax; 02-17-2021 at 11:29 AM.

  6. #21
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Lax
    First line executes(node->prev = list->tail): Screenshot - 54f8e728f0d41e1b1cca39200773ab45 - Gyazo now the prev pointer is set to be the tail of the list.
    Ah, I should have been clearer: the head and tail boxes are meant for you to keep track of what is the head and what is the tail. You should not draw any arrows to them because they represent pointers to nodes, not the nodes themselves. Rather, if something is set to the tail, then the arrow should be drawn to what the tail arrow points to, i.e., to the node that is the tail node or NULL.

    Quote Originally Posted by Lax
    The head pointer is still a NULL pointer when I think it should point to the first element in list.
    That's right. It explains why you get nothing when you print: you start with the head pointer, but it is a null pointer.

    Quote Originally Posted by Lax
    The first node's prev pointer is still pointing at the tail when it should be dereferenced to the new node.
    No, the first node's prev pointer should be a null pointer. This is why I don't want you to draw arrows to the head or tail boxes: when you say something "points at the tail", you should be able to identify exactly which node it is, or if the pointer is a null pointer because you have drawn it pointing to NULL.

    Quote Originally Posted by Lax
    The new node's next value is pointing at NULL when it should be pointing at the older node (6).
    Sorry, I'm confused: are you trying to append or prepend? insertTail sounds like append, which means that the new node's next pointer should be a null pointer: if you're inserting the new node to be the tail, then there is no next node.

    Quote Originally Posted by Lax
    Oh and the older node's next pointer should probably also point to the head and not to NULL.
    Same issue: is this append or prepend? If you're having difficulty determining which is which, then perhaps you should try your hand at a singly linked list with a tail first.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #22
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Ah, I should have been clearer: the head and tail boxes are meant for you to keep track of what is the head and what is the tail. You should not draw any arrows to them because they represent pointers to nodes, not the nodes themselves. Rather, if something is set to the tail, then the arrow should be drawn to what the tail arrow points to, i.e., to the node that is the tail node or NULL.
    Oh this makes sense I will have another go at this.

    No, the first node's prev pointer should be a null pointer. This is why I don't want you to draw arrows to the head or tail boxes: when you say something "points at the tail", you should be able to identify exactly which node it is, or if the pointer is a null pointer because you have drawn it pointing to NULL.
    Ah I see so node->prev = list->tail; makes the prev pointer of the that node point to whatever the list points at.

    No, the first node's prev pointer should be a null pointer. This is why I don't want you to draw arrows to the head or tail boxes: when you say something "points at the tail", you should be able to identify exactly which node it is, or if the pointer is a null pointer because you have drawn it pointing to NULL.
    I don't really get this. The first node is the node which should be the head of the list so wouldn't it make sense for it to have it prev pointer pointing to the next node in line and have it next pointer pointing to null.

    Sorry, I'm confused: are you trying to append or prepend? insertTail sounds like append, which means that the new node's next pointer should be a null pointer: if you're inserting the new node to be the tail, then there is no next node.
    I'm trying to apend?(Hopefully this is the right term) I'm trying to add each new node after the first node that was inserted to the list. If you are still a bit confused, I'll gladly clarify!

    Same issue: is this append or prepend? If you're having difficulty determining which is which, then perhaps you should try your hand at a singly linked list with a tail first.
    Also is this reasoning correct:

    second line executes(node->next = null) : Nothing happens here? because the next pointer was already set to null in the createNode function. I might be wrong here so correct me if im wrong.
    Hopefully I cleared this up but then again, I'll gladly clarify!
    Last edited by Lax; 02-18-2021 at 12:53 AM.

  8. #23
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Here is another attempt. (I'll go with my intuition here but with your feedback in mind)

    first line https://gyazo.com/e7acefb1141b33d7d31bd662ed9c0ed1 now the prev pointer is pointing to a NULL pointer. (I'm unsure if it is the same NULL pointer but I let it be in this case so I get the process right.)

    second line: going by my logic, nothing happens here. Again if this is wrong call me out!

    third line: Screenshot - 103b1d434b78138ce5aec79c724efbae - Gyazo

    We go again. Screenshot - fba4a6981410755836eaffac91724a87 - Gyazo

    first line: Screenshot - 87f0057e2c60d757b107ef00a972c119 - Gyazo Oh I think I just realized something. In my code im saying the prev pointer should point to the older node. And here my logic is faulty because that would make the newer node ahead in list which would mean im trying to add the new nodes at the start of the list instead of in the back. I can see how this made ou confused! I'll keep going to see if we can catch some more mistakes.

    Second line: Same thing here as in on the other second line.

    Third line: Screenshot - 3d5d32908aef202655ddd32eccf7cb7a - Gyazo The tail pointer points at the new node.

    Alrighty then, some takeaways and thoughts. I feel like the tail pointer is working as intended but the head node as I mentioned before is not changing. This : node->prev = list->tail; should probably be node->next = list->tail because im adding at the end of the list. The prev pointer is just a null pointer. This is my updated look on how I think it should be: https://gyazo.com/4d07761b89f45b9aba304b036ec79abe

  9. #24
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    If you excuse the ASCII art, this is how your final diagram should look if you append 6 and then append 7 ("append" means "insert at the end", i.e., for a linked list it means "insert after the tail"):
    Code:
    .         head     tail
    .          |        |
    .          |        |
    .          v        v
    .        +---+    +---+
    NULL <---| 6 |--->| 7 |
    .        |   |<---|   |---> NULL
    .        +---+    +---+
    The arrows going towards the left represent the "previous" pointer of the node from which it originates; the arrows going towards the right represent the "next" pointer of the node from which it originates.

    So you can see that the node with the value of 6 is the head of the linked list. Its previous pointer is a null pointer; its next pointer points to the node with the value of 7. The node with the value of 7 is the tail of the linked list. Its previous pointer points to the node with the value of 6; its next pointer is a null pointer.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #25
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    I COME BEARING GOOD NEWS!!!

    So after taking what you said to heart I tried to implement my foundings I wrote in my two most recent posts.... AND IT WAS A SUCCES!!

    This is what my current code looks like! I'll also write some comments what each thing does so you can check if my comprehension is correct aswell.
    Code:
    int insertTail(list_t *list, node_t *node)
    {    
        if (list->head == NULL) // I found that the first case is different since we only have to set the head node once. It is static so it dosent change. 
        {
            list->head = node; //we set the head pointer to point to first node.
            node->next = NULL; //sets both nodes to NULL like i did in my drawings.( still unsure if this is even necessary )
    
            node->prev = NULL; 
            list->tail = node; // sets the tail to point at this node aswell. Since we only have one node it is the head and the tail at the same time.
            list->size += 1; //increment the size by one
            return 1; //Return 1 if this is succesful
        }
        else
        {
            node->next = list->tail; //If we get here we already have atleast one node in the list. So we point the next node to the same place that the tail is pointing to. Since the tail points at the last node in the list we make it so the new node's next pointer points at it aswell.
            list->tail = node;    //Here we dereference the tail pointer so it now points to the new node.
            node->prev = NULL; //Since the node is the last node in the list its prev pointer dosent point to anything so we set it to NULL. (Still dont know since this is necessary since when we created the node we set it to NULL
            list->size += 1;    //increment the size by one
            return 1;               // If this was succesful we return one again
        }
    }
    I might be a bit to excited to notice if I have done something wrong, so please let me know if I've done something weird!
    Last edited by Lax; 02-18-2021 at 03:22 AM.

  11. #26
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Oh I think by sheer coincidence I wrote my most recent message just as you posted this reply. I think I managed to understand and implement it.

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Lax
    I might be a bit to excited to notice if I have done something wrong, so please let me know if I've done something weird!
    You have the right idea to treat the empty linked list separately from a linked list that already has nodes. However, you have indeed made a mistake for the case where the linked list already has one or more nodes. You should test, e.g.,
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct node
    {
        struct node *prev;
        int value;
        struct node *next;
    }node_t;
    
    
    typedef struct list
    {
        node_t *head;
        int size;
        node_t *tail;
    }list_t;
    
    
    list_t *createList(void)
    {
        list_t *list = malloc(sizeof(*list));
        if (list)
        {
            list->head = NULL;
            list->size = 0;
            list->tail = NULL;
        }
        return list;
    }
    
    node_t *createNode(int n)
    {
        node_t *newnode = malloc(sizeof(node_t));
        if (!newnode)
        {
            return NULL;
        }
        newnode->value = n;
        newnode->next = NULL;
        newnode->prev = NULL;
        return newnode;    
    }
    
    void printlist(list_t *list)
    {
        node_t *current = list->head;
        while (current != NULL)
        {
            printf("%d ", current->value);
            current = current->next;
        }
        printf("\n");
    }
    
    int insertTail(list_t *list, node_t *node)
    {    
        if (list->head == NULL)
        {
            list->head = node;
            node->next = NULL;
            node->prev = NULL;
            list->tail = node;
            list->size += 1;
            return 1;
        }
        else
        {
            node->next = list->tail;
            list->tail = node;
            node->prev = NULL;
            list->size += 1;
            return 1;
        }
    }
    
    int main()
    {
        list_t *list = createList();
        if (!list)
        {
            fprintf(stderr, "Failed to allocate memory for linked list!\n");
            return EXIT_FAILURE;
        }
    
        node_t *node1 = createNode(6);
        if (!node1)
        {
            free(list);
            fprintf(stderr, "Failed to allocate memory for linked list node!\n");
            return EXIT_FAILURE;
        }
        insertTail(list, node1);
    
        node_t *node2 = createNode(7);
        if (!node1)
        {
            free(node1);
            free(list);
            fprintf(stderr, "Failed to allocate memory for linked list node!\n");
            return EXIT_FAILURE;
        }
        insertTail(list, node2);
    
        printlist(list);
    
        free(node2);
        free(node1);
        free(list);
        return 0;
    }
    If you compile and run the above code, you will find that the output is:
    Code:
    6
    instead of the expected output of:
    Code:
    6 7
    So what went wrong? Let's start with this:
    Code:
    node->next = list->tail; //If we get here we already have atleast one node in the list. So we point the next node to the same place that the tail is pointing to.
    Your reasoning does not make sense. This node is supposed to be the last node of the list. How can it have a next node? What you're saying here in the code is actually this: set the next node of this node to be the current tail node of the linked list, i.e., this node comes before the tail of the linked list.

    Now let's look at this:
    Code:
    list->tail = node;    //Here we dereference the tail pointer so it now points to the new node.
    This is correct, but you're not dereferencing the tail pointer; you're dereferencing the list pointer to get the tail pointer of the linked list.

    Code:
    node->prev = NULL; //Since the node is the last node in the list its prev pointer dosent point to anything so we set it to NULL.
    No no no. Here is a list of numbers: 1 2 3. 3 is the last number in the list, so you're saying that the previous number in the list is not 2, because being the last number in the list, nothing comes before it? Obviously not. 2 comes before it, and nothing comes after it!

    Think about the node with the value of 6. Its next pointer is still a null pointer because you didn't change list->tail->next before you assigned node to list->tail.
    Last edited by laserlight; 02-18-2021 at 03:42 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Yea that is true. I actually tested myself and when I saw that I only got a 6 from my printlist I thought it was because the head pointer didnt change so I just changed the list->head to list->tail in the printlist function. But I see where you are comming from, although I dont really understand it.

    Here is what im thinking visually if that makes more sense: This is where we are after the first node is inserted because that seems to be correct.
    Screenshot - b0794507b519b3f096eab3eb0e1cdd0d - Gyazo

    Oh now that im painting it out I just realized I actually dont set the previous pointer of the older node to be the location of the new node. Screenshot - 910a36045dc6a0f731d7c6bd578a01e4 - Gyazo
    But I dont really understand what this means:
    Your reasoning does not make sense. This node is supposed to be the last node of the list. How can it have a next node?
    Yes it is supposed to be the last node of the list. But shouldn't it have a next node? That's how it's linked with the node before it. How I understand it it shouldnt have a previous node because it is the last node in the list? Do I have this backwards? Shouldnt node2.next point to node1? while node1.prev point to node2. So basically what im saying is doesnt this line of code(node->next = list->tail) create the link which the red arrow is pointing at: Screenshot - 0c0c07f1ce9d13d0fd6f3544536c8d16 - Gyazo or am I wrong here?

    3 is the last number in the list, so you're saying that the previous number in the list is not 2, because being the last number in the list, nothing comes before it? Obviously not. 2 comes before it, and nothing comes after it!
    Oh I thought that sets the last node in the list to NULL like this: Screenshot - d426aa52fbeb42dc6588c366ff3b93a7 - Gyazo

    But I have noticed that im not setting the prev pointer to point at anything new.
    Last edited by Lax; 02-18-2021 at 04:36 AM.

  14. #29
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Lax
    Yes it is supposed to be the last node of the list. But shouldn't it have a next node? That's how it's linked with the node before it. How I understand it it shouldnt have a previous node because it is the last node in the list? Do I have this backwards? Shouldnt node2.next point to node1?
    You have it backwards. "Next" means "being the first one after the present one or after the one just mentioned". The next pointer links to the node after the current node, not the node before it, i.e., it links to the next node. "Previous" means "happening or existing before something or someone else". The previous pointer links to the node before the current node, not the node after it, i.e., it links to the previous node. The first node in the (non-circular) linked list, i.e., the head node, does not have any node before it, by definition. The last node in the linked list, i.e., the tail node, does not have any node after it, by definition.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #30
    Registered User
    Join Date
    Feb 2021
    Posts
    22
    Okay I see but just to be sure: This node->prev = list->tail does establish this connection : Screenshot - de7495e8b6eb0a7764d9f138c3413d09 - Gyazo (the one the red arrow is pointing at) if it is executed before this list->tail = node;

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynamic memory. Output problems.
    By qwes3r in forum C++ Programming
    Replies: 3
    Last Post: 06-04-2015, 09:10 AM
  2. NUMA Virtual Adress Space / Physical Adress Space
    By NUMA Orly in forum Windows Programming
    Replies: 0
    Last Post: 03-14-2011, 03:19 AM
  3. Replies: 4
    Last Post: 11-01-2009, 06:19 AM
  4. Tell adress of object from adress of member
    By TriKri in forum C++ Programming
    Replies: 5
    Last Post: 10-07-2007, 05:04 AM
  5. Searching memory for an adress?
    By Blackroot in forum C++ Programming
    Replies: 12
    Last Post: 03-27-2007, 11:59 PM

Tags for this Thread