1

I am a new learner and trying to build linked list. I am able to do so but I am trying to keep the pointer of root or first node so after building linked list I can read the list or execute the pattern matching but I am not able to do it successfully. Can you please help here?

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

struct node {    
    int x;
    struct node *next;
};

int main(){

    int d;
    struct node *linked;
    struct node *head;

    linked = malloc (sizeof(struct node));

    head = linked;   <<<< As this is pointer, in while loop whenever malloc executes it changes the value of head as well.
    printf ("Location of head %p \n", head->next);

    d = 1;
    while (d>0){

        printf ("Enter the value of X: ");
        scanf ("%d", &linked->x);

        linked->next = malloc (sizeof(struct node));
        printf ("Location of linked %p \n", linked->next);

        printf ("Location of head %p \n", head->next);

        printf ("To enter further value enter non zero: ");
        scanf ("%d", &d);

        if (d==0)
            linked->next = NULL;
    }

    //linked->next = NULL;

    printf("Value of Next is %p\n", linked->next);        
    printf ("Location of head %p \n", head->next);        
}

Output:

MacBook-Air:cprog jimdev$ ./a.out

Location of head 0x7fff90ab952c <<<< this value should not be change but here in sub sequent output it is.

Enter the value of X: 0

Location of linked 0x7ff0624039c0

Location of head 0x7ff0624039c0 <<<< different value then previous

To enter further value enter non zero: 3

Enter the value of X: 3

Location of linked 0x7ff0624039d0

Location of head 0x7ff0624039d0 <<<< different value then previous

To enter further value enter non zero: 0

Value of Next is 0x0

Location of head 0x0

I just tried this new one it does the printf of linked list elements as well, let me know if you guys think of any improvement. I know recursion is quick and neat way to achieve it but I wanted to try out something with while loop.

include

include

struct node {

    int x;
    struct node *next;
    };

int main () {

    int d, hold, i;
    struct node *list;
    struct node *head;
    struct node *current;



    list = (node *)malloc(sizeof(struct node));
    head = list;
    printf ("Location of list is %p \n", head);
    d = 1;

while (d>0){

    printf ("Enter the value of X: ");
    scanf ("%d", &list->x);
    printf ("Location of list is %p\n", list);
    current = (node *)malloc (sizeof (struct node));
    list->next = current;
    list = current;

    printf ("Location of head is %p\n", head);


    printf ("Enter zero to terminate the loop: ");
    scanf ("%d", &d);

    }
    list->next = NULL;
    printf ("Value of last next is %d\n", list->next);

    current = head;

    i = 1;
    while (current->next != 0){
          printf ("Location of list is %p \n", current);
          printf ("Value of linked list %d elements %d \n", i, current->x);
          current = current->next;
          i++;
          }

    scanf ("%d", &hold);

}

4 Answers 4

2

2 things:

  1. you are outputting head->next instead of just head

  2. you are not updating linked to linked->next

The head node of a linked list is the first element of a list. head->next, when the linked list is well-formed, is the second element. Either way it shouldn't be changing as the list is made after it is created.

If you are not updating linked to be linked->next you are just throwing away the memory you just allocated in linked->next and not creating a list.

This works:

int d;
struct node *linked;
struct node *head;

linked = malloc(sizeof(struct node));

head = linked;
printf ("Location of head %p \n", head);//changed head->next to head

d = 1;
while (d>0){

    printf ("Enter the value of X: ");
    scanf ("%d", &linked->x);

    linked->next = malloc (sizeof(struct node));
    printf ("Location of linked %p \n", linked->next);

    printf ("Location of head %p \n", head);// changed head->next to head

    printf ("To enter further value enter non zero: ");
    scanf ("%d", &d);

    linked = linked->next; //this was added
    if (d==0)
        linked->next = NULL;
}

Your code, since it wasn't updating linked, kept head and linked equal. Your list looked like this:

Node {x:next}

           -> {x2:NULL}
           -> {x3:NULL}
{x1:node2} -> {x4:NULL}
    ^^            ^^
(head and linked)   you're outputing this node both times  

Since you don't have any pointers to node2 or node3 you lose these nodes (a memory leak).

You had it almost right. This is what a list generated with this code looks like:

{x1:node2} -> {x2:node3} -> {x3:node4} -> {x4:node5}
   ^^           ^^                           ^^
  head        head->next                   linked

update:

I changed the diagram for your code to better reflect what is happening.

The ptr->varname operator looks in location pointed to by ptr for the value of varname. So if the pointers are the same value then you are looking in the same space for the variables. In your case, head=linked means that if you set linked->next = ptr then head->next = ptr, and since linked is never updated to be linked->next (and therefore head->next) then you are just assigning and reassigning linked->next

2
  • In my code, I used the head = linked at very beginning and running loop to execute malloc for new linked so all new allocation happened in while loop where as I did head = linked before that so it should not be changing the head. Is it happening because of pointers reference? I am also trying to visualize the move in linked list with linked node, how am I referencing new node with old node next? Here I will have to write the value of new linked node to the linked->next of the previous linked node, right?
    – devnp
    Feb 8, 2013 at 17:12
  • @devnp, I was a little off on how I represented your code. I added an explination of the -> operator, which I think might help.
    – Stephen
    Feb 8, 2013 at 18:50
1

The value of head should only be set and NEVER changed when working with linked lists. If you change the value of head then all of the links "fall off" and the garbage collector eats them up. A linked list should follow this format.

Node number one is the head and is set to the current node

Node number two is set to the next pointer INSIDE of the head Node and Node two is also set to the current node

Node three is set to the next pointer INSIDE of node two and node three is set to the current node pointer.

Wash/rinse/repeat

Never change the head node

1

You're not really "building" a linked-list here for reasons I will explain the next paragraph ... As far as your question about the head pointer, you keep printing the value of head->next which is not the same as the head pointer. If you printed out the value of head, you would see that it never changed over time since you never explicitly modify it.

The biggest mistake I can see you are making is the fact that you are never assigning the linked pointer to point to linked->next after you've allocated memory and assinged the pointer value to linked->next. So what's happening is you keep assigning new memory blocks to linked->next, which is the same value as head->next, and in-turn creating memory leaks as you lose the references to the previously assigned memory blocks that were being pointed to by linked->next. So you'll want something like:

linked->next = malloc(sizeof(struct node));
linked = linked->next;

With this approach, you're maintaining the loop-invariant where linked always points to the last node in the list, and as a result, you're attaching new nodes to the end of the list, and not losing the references to the nodes. Additionally, you'll be able to traverse the list from the head pointer since it's never changed (it's pointing to the first node in the list).

1

This is a sample i had written for a newbie who wanted to write a doubly linked list program . You may use it for your reference . As already correctly pointed out by AMR your Head should remain contstant ( assuming you are inserting elements at the end of the list and NOT at the front ) .

Here head is implemented as global . It may not always be a good idea to have global variables . In such a case have the head be passed as to your insert_element_into_list function() something like

insert_elements(head,item)

struct node {
    int d;
    node *llink;
    node *rlink;
};
typedef struct node* Node;
Node head = NULL;

void linked_list_init(int);
void linked_list_print();

void linked_list_init(int data) {

    Node newnode = (Node) malloc(sizeof (Node));
    newnode->d = data;

    Node curr;

    if (head == NULL) {

        newnode->llink = NULL;
        newnode->rlink = NULL;
        head = newnode;

    } else {
        curr = head;
        while (curr->rlink) {
            curr = curr->rlink;
        }
        curr->rlink = newnode;
        newnode->rlink = NULL;
        newnode->llink = curr;       
    }
}

void linked_list_print() {
    Node curr;
    curr = head;
    while (curr) {
        printf("Element Data : %d", curr->d);
        curr = curr->rlink;
    }
}
1
  • Thanks everyone, let me try today to understand it.
    – devnp
    Feb 8, 2013 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.