0

I'm practising using Linked Lists, and trying some exercises here: https://study.cs50.net/linked_lists

Here's an exact copy-paste of the code found at the bottom:

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

typedef struct node
{
    // the value to store in this node
    int n;

    // the link to the next node in the list
    struct node* next;
}
node;

node* head = NULL;

int length(void)
{
    // TODO
}

int main(int argc, char* argv[])
{
    // create linked list
    for (int i = 0; i < SIZE; i++)
    {
        node* new = malloc(sizeof(node)); 

        if (new == NULL)
        {
            exit(1);
        }
        new->n = i;
        new->next = head; 
        head = new; 
    }

    printf("Making sure that list length is indeed %i...\n", SIZE);

    // test length function
    assert(length() == SIZE);
    printf("good!\n");

    return 0;
}

Could someone please explain to me the logic of "new->next = head" and "head = new", because wouldn't I then be installing in new the Null pointer head, then setting them equal to each other? I feel like it should be just head->next = new, because I'd be linking, for instance, the first node with the second node that way?

1 Answer 1

0

OK, let's look at this code:

    new->next = head; 
    head = new; 

These two lines are actually inserting a new node at the beginning of the linked list. It's far more efficient than adding it to the end.

Let's say that head is pointing at the first node in the list. We'll call it node P. Now, the code creates a new node, call it node T. (maybe other nodes were added elsewhere in between.) Node T needs to be added to the beginning of the list that starts at the node pointed to by head, i.e., node P.

So, node T was created and new points at node T. At this point, new->next should point to null.

Now we want to insert the node into the list. First, we want to preserve the existing list. We do that by setting the next pointer to the head of the list with this:

new->next = head;

Now, both new->next and head point at the beginning of the linked list, node P.

Next, we need to update head to point to the new node that we are inserting. It will become the new first node. This is how:

head = new;

Now, both head and new point at node T. Also, that means that head->next and new->next are both pointing at the next node, or the second node, node P.

Finally, since head == node T and head->next == node P, the existing list was preserved and is now updated.

At this point, new can be reassigned to another new pointer. head will not be changed when the address stored in new is changed.

Any questions?

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

2
  • I understand your explanation, thanks. But how would I add elements to the linked list in any other position, how would those 2 lines change? Apr 10, 2020 at 16:10
  • That would be more complicated. If you were adding to the end, you would have to walk the linked list to the end and then add after the last node. Since the last node->next would be null, you'd just set node->null = new. If you want to add the node somewhere in the middle, say in an ordered list, then you'd literally have to break the linked list and update all the needed pointers accordingly. But that's too complicated and code-dependent to answer here. ;-) Perhaps a review of the lecture on linked lists is in order?
    – Cliff B
    Apr 10, 2020 at 19:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .