What is the code of the insertTail function?
Also, did you fix printlist to take a pointer to list_t argument?
What is the code of the insertTail function?
Also, did you fix printlist to take a pointer to list_t argument?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Here is the InsertTail
And I did fix it to take a pointer to list_tCode:int insertTail(list_t *list, node_t *node) { node->prev = list->tail; node->next = NULL; list->tail = node; list->size += 1; return 1; }
Code:void printlist(list_t* list) { node_t *current = list->head; while (current != NULL) { printf("%d ", current->value); current = current->next; } printf("\n"); }
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
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.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: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.
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.
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.Originally Posted by Lax
That's right. It explains why you get nothing when you print: you start with the head pointer, but it is a null pointer.Originally Posted by Lax
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.Originally Posted by Lax
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.Originally Posted by Lax
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.Originally Posted by Lax
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Oh this makes sense I will have another go at this.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.
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.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'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!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.
Also is this reasoning correct: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.
Hopefully I cleared this up but then again, I'll gladly clarify!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.
Last edited by Lax; 02-18-2021 at 12:53 AM.
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
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"):
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.Code:. head tail . | | . | | . v v . +---+ +---+ NULL <---| 6 |--->| 7 | . | |<---| |---> NULL . +---+ +---+
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
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!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 } }
Last edited by Lax; 02-18-2021 at 03:22 AM.
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.
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.,Originally Posted by Lax
If you compile and run the above code, you will find that the output is: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; }
instead of the expected output of:Code:6
So what went wrong? Let's start with this:Code:6 7
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.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.
Now let's look at this:
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:list->tail = node; //Here we dereference the tail pointer so it now points to the new node.
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!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.
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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:
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?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?
Oh I thought that sets the last node in the list to NULL like this: Screenshot - d426aa52fbeb42dc6588c366ff3b93a7 - Gyazo3 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!
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.
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.Originally Posted by Lax
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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;