Square using Linked lists

After reading about linked lists and a bit about stacks it’s time to do more important things. Geometry, for us computer oompa-loompas we use it without realizing, when you select an area in your desktop or word file (which what I do with no reason :) ) Its a kind of geometry that is a square or a rectangler shape. This was just one example of geometry in things we all know, but there is other places where geometry play an important role (it’s not our interest for now). What has this to do with linked lists? – Well, what if I told you to make a square using a linked list! How you imaging it?

As usual, I will start with illustrations, but before that, lets discuss how a square is formed. In geometry, a square is just a set of 4 main points (a square contains infinite number of points but we are interested in the main ones) those points have to be aligned two by two which means not every four points gives us a square, you can put the 4 points in a single line and it is a line, not a square, so we need something to give us that square shape, of course if we were in math we could say that the angle must be a right angle and the distance between two points must be the same. Actually, we can inspire from math a bit, by using the structure of linked lists we can give each “Point” a coordinates (x, y) and do some sort of looping to make the ‘distance’ between each point and the “next” one the same (we will need the next pointer, remember?).

However, how we can make let us say two points equally aligned to form the first side of the square? Moreover, how we move to the next side, which is just above (i.e.: the opposite parallel line)?

- In this page I will simplify this geometry form using some illustrations of course, and for each part, I will add the code too (in C). HAVE FUN.

To make things more comprehensible, let us suppose that we are in a plan of x and y (just like math), after that let us draw a square with the 4 main points we talked about in the introduction:

# as you can see, each point has x and y coordinates and a number we will need after.

One of the questions was how can we make the distance between two points the same, even if we added more points to form a shape like in the image bellow, you can notice that the distance between each two points is the same, So we want something like that (we need a formula to give us that equal distance between two points, so that for each one step in the x-axis (and the y-axis) we get a fixed distance. That is the main point of making that square, now enough talking let us go back to illustrations:

In order to start making that shape, we need first to create the “structure” of our point, each point has the following properties :

- X and Y coordinates I will consider them as a double type.

- A number associated with each point.

- Finally, a pointer that points to the structure of Point. (Important!)

Now we need a function that add or “insert” values to those properties, of course we need before that to figure out the formulas that will gives us the X and Y coordinates and also the number of each square because we want to start with 1 and then increment it for each point .

As I said in the beginning, we will use a bit of math (basic stuff) in order to find the formulas that will gives us the same distance between each point.

The first step is making some variables :

- let “i” and “j” be the counters of (respectively) the X-axis (Y-axis) loops. And let us suppose that we will start counting from 0 for both I and j.

- Let L be the unit distance (the reference distance) *(later on, in the code part I will consider the general way which is : L the unit distance in the X axis and small l the unit distance in the Y axis).

After adding all information (x, y and the number of point) we make that point points to the previous one (we are using “insertion_tete” function) and then we use a pointer, which plays the role of the head as we saw in the linked list part.

Now in order to see what we’ve done i will make a print function that will display the number and the coordinates of each points.

PS : the formula to calculate the number that corresponds to each point is simple: we consider we will start with 1 and then we will keep adding one till we reach the last point we have then we move to the next level just above, and we do so by adding each time we loop through the X axis the term : (j*n) with “n” the number of points we have.

Till now everything is simple, the hard part is the following:

- Consider the list of points we’ve created, now we will make another “structure” which is the square structure that contains the following properties :

+ 4 points (because we said that each square is defined by 4 main points I will call them “sommet”).

+ A number associated to each square created.

+ A pointer that points to the next square (pointer of type square structure).

· As you can see in the image each square is defined with those 4 ‘sommet’, the challenge is to give each point of them the same coordinates as the list we’ve already created in part 1. >> see illustrations bellow

You can also notice in the case when we have three points in the first list of points we create, we get just two squares (which is logical)

>Can you imagine how many squares we can form with 4 points? – The answer is 3. So you can see the pattern here, in order to make the loops that fill the “ sommet” with its corresponding points in the first list, we will stop at the n-1 point (taking n the number of points in the X-axis and m the number of points in the Y-axis).

The big challenge we have right now is: how can we give for each “sommet” its corresponding coordinates in the previous list we’ve created ?

+ The answer is that we need another function that do this for us :)

+ It will take the list we’ve created and a number that indicates the right position of the point so that it will match with its corresponding sommet in our square. This function is pretty similar to the one we saw in the linked list part, the challenge is what is the proper value that we will look for. This time we will not use math to find the formula, just by observing the illustration bellow you can deduce the formula (actually 4 formulas). After matching each coordinate with its corresponding in the square by using the “search” function we will ‘link’ between this square and the next one by the pointer we have in the structure of the square.

Finally, to make things clearer, we make a function that displays the squares we have created with each number associated with it and its sommet points.