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