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.

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.

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));

---

?

Quote:

---

Originally Posted by hwing91

Do you mean

Code:

---

    Position* pos = (Position*)malloc(3*sizeof(Position));

---

?

---

Exactly. That would fix the issue.

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?

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.

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;

---

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.

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.

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.

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.

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);

---

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.

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.

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.

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);
}

---

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);
}

---

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.

Not random access, accessing certain nodes, for example, the second node I stored.

Quote:

---

Originally Posted by hwing91

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);

---

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!!

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).

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?

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().

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.

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.

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.

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);





}

---

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).

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.

If you're only calling add_position() twice in main() like it looks like you're doing, then there should only be 2 positions in the list and draw_balls() should only be drawing those 2. But if you add one position, call draw_balls(), add another position, then call draw_balls() again, that's 3 balls total. The original ball being draw from the first draw_balls() call and then the original ball and the new ball from the second draw_balls() call.

Hmm okay thanks, ill have to think about how im going to get this working.

Quote:

---

Originally Posted by hwing91

Hmm okay thanks, ill have to think about how im going to get this working.

---

If you have a ball already on screen, telling it now to draw 2 balls totals at three. You probably need to delete the original before drawing the new ones.