Thread: Linked Lists?!

  1. #16
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    1) Wouldn't we have to return it? Is this correct?
    - Nope. The function takes a pointer to the pointer to the start of the list so the pointer to the list can be directly modified. The function can be redefined to just take the pointer to the start of the list and then return that (possibly modified) pointer, but it's not designed that way right now.

    2) Would this be correct in deleting the first node? With this method im not sure about how to access the specific node I want, but I figure this should access the first one?
    - Close. Firstly, you don't need to allocate memory to delete a node. Secondly, the -> operator has a higher precedence than the * (dereference) operator so you need additional parentheses. Deleting the head node is really this simple:
    Code:
    void delete_position(Position** list)
    {
      Position *n = *list;
      *list = (*list)->next;
      free(n);
    }
    If you understand what you're doing, you're not learning anything.

  2. #17
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Okay thanks. Is it possible to access certain nodes with this method without looping through all of them as you did? Or would I have to write a more complex linked list function?

    Code:
    void add_position(Position** list, int col, int row)
    {
      Position* new_position = malloc(sizeof(Position));
    
      new_position->col = col;
      new_position->row = row;
    
     
      new_position->next = *list;
      *list = new_position;
    }
    
    int main(void)
    {
      Position* positions = NULL;
    
      add_position(&positions, 50, 5);
      add_position(&positions, 20, 135);
      add_position(&positions, 120, 80);
    }

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by hwing91
    Is it possible to access certain nodes with this method without looping through all of them as you did?
    If you want random access, then perhaps you should just use an array.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #19
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Not random access, accessing certain nodes, for example, the second node I stored.

  5. #20
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Quote Originally Posted by hwing91 View Post
    Not random access, accessing certain nodes, for example, the second node I stored.
    You can access the second node you stored by just using the head pointer's next variable:
    Code:
    positions->next->col = 15;
    printf("%d\n", positions->next->row);
    If you understand what you're doing, you're not learning anything.

  6. #21
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Ah I see so
    Code:
    positions->next->next->col //would access my last(third) right?
    I guess I could write a function to make it easier if I had alot more nodes. Thanks again!!

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by hwing91
    I guess I could write a function to make it easier if I had alot more nodes.
    Yes, but accessing the ith element is random access (unless you are accessing it given the (i-1)th or (i+1)th element).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #23
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    We program C in netbeans and we use VBA to perform tasks. I'm making a game, with my premade drawRect and drawCircle functions that work correctly.

    I plan on having balls (at the head of the node) be removed once you hit something, and once a counter on the balls hitting the paddle goes up to, say 5, I plan on adding an additional ball.

    Is it possible to have a function within a node to draw something? How would I go about doing that?

  9. #24
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Quote Originally Posted by hwing91
    Is it possible to have a function within a node to draw something? How would I go about doing that?
    You could have a function pointer in the node that you can set to whatever function handles drawing that particular object.

    Just in your struct definition add the following:
    Code:
    void (*draw)();
    And then you can assign it to nodes as they're created or whatever: node->draw = drawCircle, node->draw = drawRectangle

    And then when you're ready to call the functions you just call node->draw().
    If you understand what you're doing, you're not learning anything.

  10. #25
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    So i've been working on it a bit and I've decided to have a linked list with the data of the position of the balls, and a draw_ball function that cycles through the linked list and draws all the nodes in the linked list.

    Here is my code for now.

    Everything works except for some logical errors I guess. I want it to draw multiple balls, at two different positions you'll see, but it only draws the last declared position. Did I do my draw_ball function wrong? Thanks.

    Code:
        void add_position(Position** list, int col, int row){
      Position* new_position = malloc(sizeof(Position));
    
      new_position->col = col;
      new_position->row = row;
    
      new_position->next = *list;
      *list = new_position;
    }
    
    
        void draw_balls(Position** list){
            
      Position* new_position = malloc(sizeof(Position));
      new_position = *list;
      Position* p;
     for(p = new_position; p !=NULL; p = p->next){
            fillCircle4(new_position->row, new_position->col, 7, COLOR(0, 0, 0)); // the 7 denotes the size, and the 
                                        //COLOR, is a color, black, I just made all the balls, or wanted to
      }
    
    }
    
    
    int main(void) {
        Position* positions = NULL;
    
    
        add_position(&positions, 120, 80); 
        add_position(&positions, 25, 25); // Only draws this ball, I guess something is wrong 
                                                             //with my for loop up there in my draw_ball function? Thanks
    
    
        draw_balls(&positions);
    
    
    
    
    
    }
    What could be wrong? It initially sets the linked list as NULL right? Then it adds the new info with the add_position function, and makes the NULL the value of the ->next of the last node correct? I feel like it could be a pointer problem, but I looked over them and it looks right to me...? Thanks.
    Last edited by hwing91; 11-08-2010 at 04:55 AM.

  11. #26
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Unless you're creating a new node, you don't need to malloc() more memory. You can get rid of the call to malloc() in draw_balls().
    This code:
    Code:
      Position* new_position = malloc(sizeof(Position));
      new_position = *list;
    allocates memory and immediately changes the pointer to that memory to point to a different place, losing your only reference to the memory you just allocated. This is referred to as a memory leak since there's no way to ever free the memory you allocated.

    Code:
     for(p = new_position; p !=NULL; p = p->next){
            fillCircle4(new_position->row, new_position->col, 7, COLOR(0, 0, 0)); // the 7 denotes the size, and the 
                                        //COLOR, is a color, black, I just made all the balls, or wanted to
      }
    Here you have p walking through the list, but you're referencing new_position in your fillCircle4() call. In fact, the whole draw_balls() function can be written much simpler like this:
    Code:
    void draw_balls(Position **list)
    {
      Position *p;
      for(p = *list;p != NULL;p = p->next)
        fillCircle4(p->row, p->col, 7, COLOR(0, 0, 0));
    }
    Your main() and add_position() functions look good.
    If you understand what you're doing, you're not learning anything.

  12. #27
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    AHHHHHHHHHHHHHHH, I see. Thank you SO much again. I think im done with my code, all I have to do is tweak my collision detection and implement adding/removing balls and im done.
    Last edited by hwing91; 11-08-2010 at 11:26 AM.

  13. #28
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    So now that i've fixed the collision detection to register for multiple balls, right off the bat if I draw two balls everything works fine.
    If I draw one, then have a condition that add_position()'s another ball, there become three balls on the screen, it seems the original ball, and two additionals?

    Shouldn't the add_position() function add another position then the draw_balls() function only draw the two balls? It doesn't seem to be updating correctly.

    If I do the delete_position() line of code, it seems to wipe my balls completely?

    Hmm, are my add_position() and delete_position() functions working correctly?



    Code:
        void add_position(Position** list, int col, int row){
      Position* new_position = malloc(sizeof(Position));
    
      new_position->col = col;
      new_position->row = row;
    
      new_position->next = *list;
      *list = new_position;
    }
    
        void delete_position(Position** list){
      Position *n = *list;
      *list = (*list)->next;
      free(n);
    }
    
    
        void draw_balls(Position** list){
            
      Position* new_position = malloc(sizeof(Position));
      new_position = *list;
      Position* p;
     for(p = new_position; p !=NULL; p = p->next){
            fillCircle4(new_position->row, new_position->col, 7, COLOR(0, 0, 0));
                                       
      }
    
    }
    
    
    int main(void) {
        Position* positions = NULL;
    
    
        add_position(&positions, 120, 80); 
    
                                                            
    
    
        draw_balls(&positions);
    
        //some condition causes this, then does what I wrote in my intro paragraph.
        add_position(&positions, 25, 25); 
        // some condition causes this, then wipes all my balls.
        delete_position(&positions);
    
    
    
    
    
    }

  14. #29
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Quote Originally Posted by hwing91
    So now that i've fixed the collision detection to register for multiple balls, right off the bat if I draw two balls everything works fine.
    If I draw one, then have a condition that add_position()'s another ball, there become three balls on the screen, it seems the original ball, and two additionals?
    It should draw the one ball, and then draw the original ball and the new one.

    Your draw_balls() functions is still incorrect. Try replacing it with the code I gave you previously:
    Code:
    void draw_balls(Position **list)
    {
      Position *p;
      for(p = *list;p != NULL;p = p->next)
        fillCircle4(p->row, p->col, 7, COLOR(0, 0, 0));
    }
    I don't see anything wrong with delete_position(). It should delete the first node in the list (i.e. the last, most recent, position that was added).
    If you understand what you're doing, you're not learning anything.

  15. #30
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Oh yeah sorry, I used that code.

    The delete_position() works fine, I had an error in something else that I fixed.

    So draw_ball() isn't suppose to draw 3 balls? It seems like its drawing the original, then another "original" and the new added position one.

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, 05: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, 11: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