Thread: Linked Lists?!

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    17

    Linked Lists?!

    Hello! I am taking a beginning C class at my school and the requirements for this homework is to make a game using linked lists.
    The requirements with linked lists are
    - To draw elements of linked lists
    - Moving elements around in linked lists
    - and adding/removing elements to/from a linked list

    So before I started my implementation of a linked list, I just wrote the code for my game, I decided to do a pong game, in structure/dynamic memory format because I have no clue what a linked list is lol.

    Code:
        typedef struct _position{
            int row;
            int col;
        }Position;
        Position* pos = (Position*)malloc(sizeof(Position));
    
        pos[0].col = 50;
        pos[0].row = 5;
        pos[1].col = 20;
        pos[1].row = 135;
        pos[2].col = 120;
        pos[2].row = 80;
    That is the code of my position structure that updates for where the paddles and the balls are (two paddles and one ball). I was wondering how I could easily just convert this into a linked list?

    I have my game working but now and I just want to convert my structure data into linked list format... i've been trying to figure out what a linked list is and from what I understand it is just a way of storing information...

    Is there any simple way of just making a basic linked list structure that I can add and pull elements to and from like my structures?
    Our class doesn't have a textbook so i've been trying to google everything but to no avail.

    Thanks.
    Last edited by hwing91; 11-02-2010 at 06:52 PM.

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    A linked list is just a series of instances of structs that point to another instance of the same struct type.

    If your struct looked like this:
    Code:
    typedef struct _position
    {
      int row;
      int col;
      struct _position *next;
    } Position;
    Then you could set pos->next to another dynamically allocated instance of the struct. There are well-documented uses of linked lists including creation, iteration, addition of nodes, removal of nodes, etc. and you shouldn't have a hard time searching for that kind of information.

    Also, I'm assuming that the code you pasted isn't your actual working code, since you only allocate enough space for one instance of the struct, but you're accessing it as though you had memory allocated for 3.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Hmm maybe my understanding of dynamic memory isn't as good as I thought, in class thats how we were always taught to create a structure and store elements into it.

    That is the code im using to declare the structure and set it's initial values for three rows/positions, it works and my pong game is working at the moment.

    Do you mean

    Code:
        Position* pos = (Position*)malloc(3*sizeof(Position));
    ?

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Quote Originally Posted by hwing91 View Post
    Do you mean

    Code:
        Position* pos = (Position*)malloc(3*sizeof(Position));
    ?
    Exactly. That would fix the issue.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Yeah whoops, thanks alot for your help so far lol, my professor really doesn't do anything to aid us in our class.

    So I just read a quick article about them.

    So, bare with me since I really do suck at coding and I'm just a beginner.

    Linked lists are a storage of structures kinda? Like having the first "element" in one be a structure with it's own dynamically allocated data, and the next another one with different values in the structure?

  6. #6
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Exactly. They're favored over arrays when you'll be doing a lot of inserting and removing of nodes. If you want to insert a node in an array, you have to move each element after the insertion point one index out in order to create space for the new element.

    But for a linked list all you have to do is point the new node's next member to the previous node's next member and then set the previous node's next member to the new node.
    Code:
    new_node->next = prev_node->next;
    prev_node->next = new_node;
    As you can see, if you have a large collection of elements/nodes, the linked list approach is much more efficient than moving everything around in an array.
    If you understand what you're doing, you're not learning anything.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Hm okay...I'm still confused on the syntax on how to define a linked list and access nodes from them.

    So if I wanted to begin to change my storage into a linked list method, would something like this be okay to start it off...?

    Code:
        typedef struct _position{
            int row;
            int col;
            struct _position *next;
        }Position;
        Position* pos1 = (Position*)malloc(sizeof(Position)); // Would I have to keep defining new dynamic memory for each of the structures?
        Position* pos2 = (Position*)malloc(sizeof(Position));
        Position* pos3 = (Position*)malloc(sizeof(Position));
    
    
        pos1.col = 50;
        pos1.row = 5;
        pos1->next = pos2;
        pos2.col = 20;
        pos2.row = 135;
        pos2->next = pos3;
        pos3.col = 120;
        pos3.row = 80;
        pos3->next = NULL;
    Last edited by hwing91; 11-02-2010 at 07:37 PM.

  8. #8
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    That's pretty close. You would use the -> operator to access the structure members instead of the . operator though since pos1, pos2, and pos3 are pointers. Other than that, it looks right.

    Regarding your question about memory allocation, you could allocate a big chunk of memory like you were doing with your array method like so:
    Code:
    Position* positions = malloc(3 * sizeof(Position));
    
    Position* pos1 = positions;
    Position* pos2 = positions + 1;
    Position* pos3 = positions + 2;
    pos1->next = pos2;
    pos2->next = pos3;
    pos3->next = NULL;
    That is really not the typical way of doing it though. Usually you just allocate the new nodes as you need them without keeping a reference to each node. You only really need to keep track of the head node and then walk through it from there.
    If you understand what you're doing, you're not learning anything.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Would this be correct in declaring a singly-linked list then, if i only wanted these three?

    Code:
        typedef struct _position{
            int row;
            int col;
            struct _position *next;
        }Position;
        Position* positions = malloc(3*sizeof(Position));
    
        Position* pos1 = positions;
        Position* pos2 = positions + 1;
        Position* pos3 = positions + 2;
    
        pos1.col = 50;
        pos1.row = 5;
        pos1->next = pos2;
    
        pos2.col = 20;
        pos2.row = 135;
        pos2->next = pos3;
    
        pos3.col = 120;
        pos3.row = 80;
        pos3->next = NULL;

    If so how would I access the storage elements correctly? I tried just doing pos2.col for example, and it errors.
    Thanks alot again, this is helping me understand this basic concept that im SURE i'll be using alot later.

  10. #10
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    You would do pos2->col instead since pos2 is a pointer. Your code is correct except for your use of the . operator for assigning member values. Just change them all to the -> operator and you're set.
    If you understand what you're doing, you're not learning anything.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Okay thanks!

    So this is my definition so far.
    Code:
        typedef struct _position{
            int row;
            int col;
            struct _position *next;
        }Position;
        Position* positions = malloc(3*sizeof(Position));
    
        Position* pos1 = positions;
        Position* pos2 = positions + 1;
        Position* pos3 = positions + 2;
    
        pos1->col = 50;
        pos1->row = 5;
        pos1->next = pos2;
    
        pos2->col = 20;
        pos2->row = 135;
        pos2->next = pos3;
    
        pos3->col = 120;
        pos3->row = 80;
        pos3->next = NULL;
    
    
        int balls = 0;
        int randElement = 1;
        int ballSize=7;
        int down = TRUE;
        int rt = TRUE;
    You were talking about
    Code:
        Position* positions = malloc(3*sizeof(Position));
    As not being typical, which I assume it would be more complicated if I wanted to add and remove nodes.

    How could I start adding a node and removing a node more efficiently than having to adjust the dynamic memory size manually each time? At least I thought thats what you were hinting at earlier.
    Last edited by hwing91; 11-02-2010 at 09:26 PM.

  12. #12
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    You might have a function that does it:
    Code:
    void add_position(Position** list, int col, int row)
    {
      Position* new_position = malloc(sizeof(Position));
    
      new_position->col = col;
      new_position->row = row;
    
      // It's easiest to add the new node to the start of the list
      // Otherwise you have to walk through the list to find the end and then append the new node there
      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);
    }
    And then you can use any old Position* pointer to start at positions and as long as the pointer isn't NULL, you can print the struct's members and move to the next node:
    Code:
    Position* p;
    for(p = positions;p != NULL;p = p->next)
      printf("%d %d\n", p->col, p->row);
    If you understand what you're doing, you're not learning anything.

  13. #13
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Let me add one note here as well:

    Linked lists are not generally geared towards what you're looking for in this instance (pong game) where you have a set number of things to keep track of and you're not adding/removing nodes.

    You might start seeing a benefit if more balls could appear or disappear (go out of play but play continues with other ball?) mid-game. I just don't want you to be wondering "I really don't see why linked lists are useful!" because yeah, with a static number of things to keep track of with no node addition/removal, you won't see the usefulness.
    If you understand what you're doing, you're not learning anything.

  14. #14
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    No yeah, I plan on adding multiple balls and removing them depending on circumstances, I can see the usefulness already, its just the syntax that's confusing more so.

    My project proposal is to have a pong game where the longer you play without dying, the more balls are added, and if you hit a certain object in the middle which is moving around, you remove balls to make it easier (maximum removed to 1). There's no ultimate point to the game besides staying alive as long as possible lol.

    Thanks again. I'll try to implement it more tomorrow, for now I needa sleep, if I have more questions, which im sure i will, I'll definitely post back. You've been EXTREMELY helpful, thank you.
    Last edited by hwing91; 11-02-2010 at 10:20 PM.

  15. #15
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Hmm I have a few questions again. I'll comment them in the code you helped me with.

    Would this function be correct in deleting the first node in that linked list?

    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;
    
      return *list; //Wouldn't we have to return it? Is this correct?
    }
    
    void delete_position(Position** list)
    {
    
      Position* new_position = malloc(sizeof(Position));
    
    
    /*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?*/
       
      new_position=*list->next; 
      
      return new_position;
    }
    
    int main(void)
    {
      Position* positions = NULL;
    
      add_position(&positions, 50, 5);
      add_position(&positions, 20, 135);
      add_position(&positions, 120, 80);
      delete_position(&positions);
    }
    Thanks again.
    Last edited by hwing91; 11-03-2010 at 12:26 PM.

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