Linked Lists

This is a discussion on Linked Lists within the C Programming forums, part of the General Programming Boards category; I am a little confused about the push() function, which puts an element at the beginning of a linked list. ...

  1. #1
    Registered User Tommo's Avatar
    Join Date
    Jun 2007
    Location
    Scotland
    Posts
    101

    Linked Lists

    I am a little confused about the push() function, which puts an element at the beginning of a linked list.

    Code:
    void WrongPush(struct node* head, int data) {
       struct node* newNode = malloc(sizeof(struct node));
       newNode->data = data;
       newNode->next = head;
       head = newNode;       // NO this line does not work!
    }
    void WrongPushTest() {
       List head = BuildTwoThree();
       WrongPush(head, 1);   // try to push a 1 on front -- doesn't work
    }
    The proposed solution for the above is to have struct node** head instead of struct node* head in the WrongPush parameters.

    Now, I am a little confused here, could someone outline a process to help me understand it better? Also, in WrongPushTest(), could i pass WrongPush(&head, 1) instead of WrongPush(head, 1)? Would this allow me to keep the struct node* head in the parameter list? Are (*-**) and (&-*) synonymous?

    Thanks

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,714
    Well the problem is that head nodes outside the push function won't be able to reflect the change if you do it that way. The idea would stay the same, except that from a working implementation, you want the head pointer to point to the new head.

    You could return the new head pointer

    lst = push( lst, data)

    or use a pointer to pointer.

    push( &lst, data );

  3. #3
    Registered User Tommo's Avatar
    Join Date
    Jun 2007
    Location
    Scotland
    Posts
    101
    Sorry I didn't know 'List head' meant the same as 'struct node* head'. That clears things up a little. I am still a little confused about passing the & and using the 'struct node ** head' for that. I will read up a bit more and come back if i need further help. Thanks

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    Quote Originally Posted by Tommo View Post
    Sorry I didn't know 'List head' meant the same as 'struct node* head'. That clears things up a little. I am still a little confused about passing the & and using the 'struct node ** head' for that. I will read up a bit more and come back if i need further help. Thanks
    You could have the function return a pointer to the new head of the list:

    Code:
    struct node *push(struct node *head, int data)
    {
        struct node *newnode = malloc(sizeof(*newnode));
    
        newnode->data = data;
        newnode->next = head;
        return newnode;
    }
    Then, when you use it:

    Code:
    head = push(head, 12345);
    Of course, there is the issue of malloc() returning NULL, which my example doesn't consider.

  5. #5
    Registered User Tommo's Avatar
    Join Date
    Jun 2007
    Location
    Scotland
    Posts
    101
    OK, thanks. Turns out the new code is:
    Code:
    void Push(struct node** headRef, int data) {
       struct node* newNode = malloc(sizeof(struct node));
       newNode->data = data;
       newNode->next = *headRef;   // The '*' to dereferences back to the real head
       *headRef = newNode;         // ditto
    }
    void PushTest() {
       struct node* head = BuildTwoThree();// suppose this returns the list {2, 3}
       Push(&head, 1);       // note the &
       Push(&head, 13);
       // head is now the list {13, 1, 2, 3}
    }
    I think the thing that tripped me up was the **. I guess you need to know that the same rules apply as with the single *. Thanks for the help

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 04:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 10:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21