Thread: Pushing a new head to list - C

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    135

    Pushing a new head to list - C

    Hey.

    This is the code of a list implementation and some function to remove duplicates in it.

    I have small question about the two final lines in push function:
    First, we define the next element of the new node as the former head - using de-reference.
    And after that, we define the head to be equal to the address of the new node.

    For me, it looks like a buggy circle somehow...

    I see it so:
    The next element of the new node is pointing to the former (about to be) head.
    Now, this former head is being equal to new node.
    So it seems like the new node's next at first points to the former head, and then this next is pointing to the new node (as we define *head to be equal to new node).


    Eventually, I see it as if new node's next points to new node, instead of to the former head.

    What am I missing here?


    Thank you all!

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    
    typedef struct Node {
        int data;
        struct Node* next;
    } Node;
    
    void printList(Node *head) {
        Node* p = head;
        while (p !=NULL) {
            printf("%d ", p->data);
            p = p->next;
        }
         printf("\n");
    }
    
    void push(Node** head, int new_data)
    {
        Node* new_node = (Node*) malloc(sizeof(Node));
        new_node->data  = new_data;
        new_node->next = *head;
        *head = new_node;
    }
    
    
    void deleteList(Node** head) {
        Node* p = *head;
        while (p !=NULL) {
            Node *next = p->next;
            free(p);
            p = next;
        }
        *head = NULL;
    }
    
    
    void removeDuplicates(Node *head) {
        Node *ptr1, *ptr2;
        ptr1 = head;
     
        while (ptr1 != NULL ) {
            ptr2 = ptr1;
     
            while (ptr2->next != NULL) { // iterate the list from ptr2
            
                if (ptr1->data == ptr2->next->data) { // need to delete
                    Node* tmp = ptr2->next;
                    ptr2->next = ptr2->next->next;
                    free(tmp);
                } else {
                    ptr2 = ptr2->next;
                }
            }
            ptr1 = ptr1->next; // move to next node
        }
    }
    
    
    void myListTest() {
        Node* phead = NULL;
        for(int i=0; i<10; i++) { 
            push(&phead, i); 
            push(&phead, 10-i); 
        }
        printList(phead);
        removeDuplicates(phead);
        printList(phead);
        deleteList(&phead);
    }
    int main() {
        myListTest(); 
        return 0; 
    }

  2. #2
    Registered User
    Join Date
    Feb 2019
    Posts
    581
    Aren't you overthinking about pointers usage?
    Code:
    // FIX: Returns true if OK, false if allocation fail.
    int push ( Node **head, int new_data )
    {
      Node *new_node = malloc ( sizeof ( Node ) );
    
      // FIX: malloc() could fail!
      if ( ! new_node ) 
        return 0; // FAIL!
    
      new_node->data  = new_data;
    
      // *head, of course, holds the address of the head node!
      // Since the 'new_node' holds the address of the new node (duh!),
      // we have to assign the address of old 'head' to it's next member...
      new_node->next = *head;
    
      // ...and make this new_node the new head!
      *head = new_node;
    
      return 1; // SUCCESS!
    }
    Using you should do:
    Code:
    if ( ! push ( &head, i ) )
    {
      fputs( "ERROR pushing data.\n", stderr );
    
      // Let crt0 get rid of allocated memory before exit...
      exit( EXIT_FAILURE );
    }

  3. #3
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    @flp1969 - Sorry but I can't see how this answers my question at all...

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    581
    Quote Originally Posted by HelpMeC View Post
    @flp1969 - Sorry but I can't see how this answers my question at all...
    Ok... your ONLY question: "What am I missing here?"
    A: I think you aren't missing anything...

  5. #5
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    @flp1969 -
    "For me, it looks like a buggy circle somehow...
    Eventually, I see it as if new node's next points to new node, instead of to the former head.
    "

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    775
    head is a pointer variable that initially holds the address of the current first node, which will be NULL (basically zero) if the list is empty.

    The newly created node's next pointer is set to that same address so that it points to the current head of the list. Then the head pointer is reset to point to the new node.

    Pointers are basically just integers that hold memory locations (actually, they can be more complicated, but that doesn't concern us here).

    Try looking at this "simulation" of memory:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
     
    typedef struct Node {
        int data;
        int next;
    } Node;
     
    int main() {
     
        // we aren't using offset 0 (considered an "illegal" address so that
        // we can use it to indicate that a pointer is pointing nowhere)
        Node memory[100]; 
     
        // For memory "allocations" (we won't do deallocations)
        int next_address = 1;
     
        int head = 0;  // set to "NULL" to indicate empty list
     
        // add a new node (note that we always set the next
        // pointer to the old value of head)
        memory[next_address] = (Node){50, head};
        head = next_address++;
     
        // add a new node
        memory[next_address] = (Node){51, head};
        head = next_address++;
     
        // add a new node
        memory[next_address] = (Node){52, head};
        head = next_address++;
     
        // print list (note that it prints in the reverse order
        // that the nodes were added)
        for (int i = head; i != 0; i = memory[i].next)
            printf("%d ", memory[i].data);
        putchar('\n');
     
        return 0;
    }
    Last edited by john.c; 12-05-2019 at 12:52 PM.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  7. #7
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    @john.c - amazing.
    I think I got it.
    The key word here is: "reset".

    And your simulation actually demonstrates that head is "reflected" differently as we go through the code.
    It like makes a mark in each Node.

    Thank you!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 04-25-2013, 01:50 AM
  2. Access violation while pushing newnode on list
    By bodhankaryogesh in forum C++ Programming
    Replies: 3
    Last Post: 03-24-2008, 04:42 AM
  3. Another List Q - Seg fault on head-tail list
    By JimpsEd in forum C Programming
    Replies: 11
    Last Post: 05-10-2006, 12:53 AM
  4. head pointer(linked list)
    By Ausandy in forum C Programming
    Replies: 5
    Last Post: 08-24-2002, 01:25 AM
  5. list head
    By sweets in forum C Programming
    Replies: 4
    Last Post: 04-08-2002, 02:03 PM

Tags for this Thread