Reversing a Linked List

Reversing a singly linked list is one of those things that’s super easy to implement but can be tricky at first to actually implement – especially if you’re new to linked lists in general. At the same time, it’s definitely an algorithm that you should understand. Besides there of course being use cases for it in dev related purposes, it’s also the focus of common teasers that you’ll find in interview questions. Simply put, regardless of whether or not you have an immediate need to utilize this algorithm, it’s one that any coder should have handy in their back pocket.

The goal of this post is to make it as clear as possible for you to grasp and visualize the method of linked list reversing. As you read along you might find it helpful to also watch the following video (as the example in the video is the same as talked about in this post):

Let’s start with a very simple singly linked list:

Yup, nothing fancy about this list. Four integers are linked together (1 -> 2 -> 3 -> 4) –  1 at the head of the list, 4 at the end. What we want is for the order to become reversed: 4 -> 3 -> 2 -> 1 – putting 4 at the head of the list.

Let’s get into how we’re going to set up our reversal code. We’ll assume that we’re writing a function which accepts a ‘pointer’ to the head of the linked list. At the beginning of our function we’ll initialize 3 pointers: previous, current, and next. These pointers will be used so we can keep track of node states during the reversal.

ListNode previous = null;
ListNode current = head;
ListNode next = head;

Our previous pointer is currently set to null. This makes sense because we haven’t even performed 1 iteration of our reversing loop, so why would previous be set to anything? Then we set current to head – even at the start we’re positioned at the head aka first node, so current should be set to something.  Finally we got our next pointer, currently set to head as well, and, as long as head wasn’t null to begin with, will ensure that the below while loop runs at least 1 iteration:

while(head != null) {
}

Easy enough so far, right? Now we have to start to work out the code we’ll have inside our loop.

Let’s pretend we’re just starting and running for one iteration – the second line of code within our loop is going to overwrite the next pointer on our current node, but we’ll need to reference that pointer later on so we can keep traversing the linked list – so we’ll store and preserve that in next for future use. The following line will set next to point to node1:

next = current.next;

Now we get to the part where we’re actually linking our current node up to our previous node. At this stage, current is referencing the head node (node1) and we’re going to link node1’s next up to prev (right now being null).

current.next = prev;

Now we’ll update prev so that it references current (so prev will point to node1):

prev = current;

And then finally we set current to next (in this case current will point to node2)

current = next;

By the end of the iteration, node1 will point to null, and we’ve set our pointers up so that we’re ready to work on linking node2’s next to node1.

I mentioned earlier that in this scenario were writing a function which will return the value of the new ‘head’ node. As for our return value – what are we going to return to represent our new head? Just by visually inspecting the animation we can see that it wouldn’t make sense to return either current or next since by the end of the process both of these will hold a null value. We’ll have to return prev since that will always contain the last item in the list right before null.

Putting it all together, we have the following reversing method in java (which, being as simple as it is, is easily portable to other languages):

How to Code the Mandelbrot Set

This is a picture of the famous Mandelbrot set – generated from code we'll step through later on. There’s a very good chance you’ve encountered this picture before in some shape or form – there are probably thousands of implementations scattered around the web. If you’ve come here because you’d like to learn how to make your own Mandelbrot generator, or would just like to know more about it in general, then you’ve come to the right place. By the end of this article you will have coded your own program which displays this on screen, and will also have the know-how to create an implementation entirely from scratch, perhaps in another language of your choosing, as well.

We aren’t going to cover all the vast details and mechanics underlying the Mandelbrot. The main goal of this article will be to get you to the point that you can understand what’s going on fairly intuitively within the system so you have enough background to code your own implementation of it. I’ll then step through implementing a basic Mandelbrot generator in JavaScript and HTML5.

We’ll address the concept of iterating functions and “orbits” first. Chances are, you might not have heard these terms before but are already aware of what they are on a conceptual level. In very simple terms, we find the orbit of a particular mathematical function by plugging a particular value in a mathematical function and iterating that value infinitely. Basically, we plug a seed in, get the result, plug that result back into the function and then use that result as the next value to be plugged in, and so on and so on.

For instance, let’s find the orbit of 2 in the squaring function, x^2. We iterate like this:

(2) ²=4
(4) ²=16
(16) ²=256
(256) ²=65536

And so on to infinity…

Alternatively, we could start with a seed of 0:

(0) ²=0
(0) ²=0
(0) ²=0

And so on… it’s easy to figure out that by starting with 0 we’re always going to get back to 0.

Lastly, if we start with a fractional seed like ½, the orbit will look something like this:

(½) ²=¼
(¼) ²=1/16
(1/16) ²=1/256

We get increasingly closer to 0 each iteration, but never quite land there. 

The dynamics of this function are pretty boring – there are only a few things that can happen with a given seed we provide:

• If we start with 0 and square 0, we’re going to end up with 0 again, which upon squaring will again result in 0, and again and again.
• If we start with a negative or positive fraction and square that, we will then get a positive fraction, which will then get repeatedly squared and continue to result in smaller fractions, continuously getting closer to zero but never quite getting there.
• If we start with any negative value slightly less than 1 (such as -1.005) or a positive value slightly higher than 1 (e.x: 1.005), and keep iterating we’ll eventually approach infinity.
•  If we iterate with a seed of 1, we’ll just keep getting an output of 1.

It is important to point out that the orbits of 0 and 1 are fixed points – the sequence is constant. 

Things get a little more interesting with functions like x² - 1. This function exhibits the behavior like above but introduces a new type of orbit to it. If we plug in -1 as a seed, we get the following sequence of outputs: 0,-1,0,-1,0,-1, etc. This is known as a periodic point  (a ‘2-cycle’ orbit).

You could use this information to generate a visualization based on the behavior of the various outputs that you get for each seed. For instance, with the squaring function – each seed whose orbit flies off into positive infinity (for instance, 2), plot a white pixel, while any of the seeds that stay within the a certain radius of the origin (seeds <1 or >-1) plot a black pixel, etc. This however would yield a pretty boring picture. 

We aren’t going to do this, so why did I mention all of that? Because it turns out that the Mandelbrot image is essentially an illustration of the behavior of orbits generated from different seeds plugged into a mathematical function – except this time, we’re dealing with a complex function on the complex plane. And unlike the basic functions we talked about earlier, this visualization will yield a more unique illustration.

But before we jump in and code a Mandelbrot generator, there’s a couple more mathematical concepts you need to get up to speed with like: what the complex plane actually is, and what is i? i represents imaginary numbers. 1i or i, 2i, 3i, 4i, 5i, etc are all imaginary numbers. i² is equivalent to -1. Why? Just roll with it for now. Like I said, we could go on and on with the details here – but simply put, imaginary numbers help us explain and come to solutions we wouldn’t be able to with real numbers alone. For instance, knowing that i² == -1, we can now say that the square root of -1 is i.

Imaginary numbers can be combined with real numbers to form complex numbers (2+4i, 3+7i, 6-2i, etc) are all complex numbers.

  

Take a look at the graph below to see an example of a complex number plotted on a complex plane:

We’ll be working with the complex plane within our Mandelbrot generator. 

There are a multitude of properties inherit in these numbers. Of immediate interest to us right now is the concept of a complex number’s ‘absolute value’. Remember that the absolute value in regards to real numbers is ‘distance from zero’. In this case, we can use the Pythagorean Theorem to calculate a complex number’s absolute value based on its real and imaginary components. We can calculate the absolute value of the complex number shown above like so:   which comes out to approximately 4.243. Keep that method in mind – we’ll be using it again later in our code.

For the entirety of our time working with the Mandelbrot set, we’ll be working with the following equation: Z² + C.

For Z, we’ll simply be starting with the value 0. The C part will vary – we’ll choose various complex numbers along the plot to plug in C and iterate from there.

Diving into the code

Let’s write the code. We’re going to use Javascript and utilize the HTML5 canvas element for the graphics rendering (If the github gist isn't showing below, visit the full code on github).

The core of the logic begins with the solve function, which accepts two sets of complex numbers – the first complex number represented by real0 and i0 will be the value for the z part of the equation. The second complex number (real1 and i1) will be the value for the C part of the equation. Solve() returns a complex number in the form of a two element array for simplicity. Let’s go over how those two parts are calculated. 

First we have the real part which first involves multiplying real0 by real0 (aka real0 squared) plus the product -1, and i0 squared. Why? Well let’s say we plugged 2+5i as a seed into our z²+c equation:

(2+5i) ² + (2+5i).

Which expands to: (2+5i) * (2+5i) + (2+5i)

Ignore the third complex number in gray for now. Let's foil this. The first step in calculating the new real part is the first set of 2s (highlighted in blue) multiplied together, added to the result of the first set of imaginary parts (the 5s highlighted in green) multiplied together. And remember i² is equivalent to -1, which is why we’ll multiply whatever that value is by -1.

So we have realpart = (2*2)+(-1*5*5) =  4 + -25 = -21. At this point the real part of our new complex number is equal to -24.

The next line starts to calculate the imaginary portion of the complex number. As we continue foiling the example above, we multiply 2 by 5, and then double that value (because we’ll be doing that twice).  So we have -21 for the real portion of our complex number and 20 for the imaginary part: -21 + 20i. 

Then there’s the last two lines right before the return statement: we have to add in the complex number that we have for C (the one above we have highlighted in gray). This part is easy: (-21 + 2) + (20i+5i) = -19 + 25i or 25i – 19.

Then we come to the plotMandelbrot() function, where everything comes together. The particular range on the complex plane we’ll be targeting for the Mandelbrot is between -1.5 and 0.5 on the real axis, and between -1 and 1 on the imaginary axis. Why this range? Anything beyond this range is outside the Mandelbrot set – meaning that all the orbits spiral off into infinity. You’ll get a better sense of what I mean once you actually see this thing drawn on screen.

Next is the nested loop that traverses the complex plane and determine the orbits for each seed.

For each seed, we check whether it stays within the bounds of the Mandelbrot or if it leaves the set. We do this by running the seed through our solve() function repeatedly, and if after a certain arbitrary number of iterations the magnitude of the complex number we left on exceeds 2.0, then we consider that point to be outside the set and paint a black pixel at that point. However, if the absolute value is <= 2.0 then we consider the point to be within the bounds of the Mandelbrot and paint a black pixel. Lots of arbitrary stuff here – you could swap the colors if you want, or even have different colors represent points within and outside the set. You could even introduce multiple colors – like having different colors represent how long specifically it takes for each seed’s orbit to escape the set. Additionally, there are numerous ways to speed this code up and make it more efficient.

The full code for this Mandelbrot implementation here can be found on github: 

https://github.com/edev90/Mandelbrot-JS

Further Reading

In case you were wondering, imaginary and complex numbers aren’t just for drawing neat looking pictures like the one above – they do have significance importance in various scientific and mathematical domains. Signal and sound processing, certain branches of physics, for instance, are examples of fields which rely heavily on imaginary and complex numbers.

Since this is a development and coding blog primarily, I took a very high level approach to talking about the Mandelbrot in order to get you to the level of being comfortable coding your Mandelbrot painters. I merely scratched the surface of what’s going behind the chaos inside the Mandelbrot.

There are many questions you might be left with. For instance, you might be wondering – what are those bulb like looking things in the image?  The answer to that question along with more insight into the mathematics of dynamical systems in general can be found by exploring this Boston University web page.

You might also want to check out this book: https://www.amazon.com/First-Course-Chaotic-Dynamical-Systems/dp/0201554062/. This introduction to chaotic dynamical systems includes plenty of questions and examples relevant to the material in this tutorial, as well a myriad of other dynamical systems.

I hope this post demystified Mandelbrot and provided some insight into putting together your own implementation.

Once again, the full code featured here can be found on github: https://github.com/edev90/Mandelbrot-JS

Golfing Tic-Tac-Toe in Javascript

Recently while searching for something completely unrelated to codegolfing, I came across a thread on stackoverflow which piqued my interest: https://stackoverflow.com/questions/2245801/code-golf-tic-tac-toe.

For those unfamiliar with the term, code golfing is essentially the art of implementing a certain program or algorithm in the least amount of code possible – a fun way to exercise your competitive and creative coding prowess. On a more practical front, it can also be a good way to practice writing efficient code which translates over to more serious coding endeavors.

The challenge was simple: Write a function which accepts an integer array of 9 integers (0 representing blank cell on the board, and 1 and 2 representing the X and O players, respectively) and output one of the following integer values:

·         0 if the board is empty or there is no winner

·         1 if player ‘X’ has won

·         2 if player ‘O’ has won

Scrolling down I found a 114 character Javascript implementation. I already knew what code golfing was, but I hadn’t really done it in a competitive context before.  I had to of course try my hand at beating out the JS implementation.

After thinking about it for a few minutes I whipped up the following solution:

        

The code is fairly straightforward – we’re decrementing the variable i and for each iteration we’re setting r to the value of bitwise AND’ing the 3 respective positions of a “win” board state. So for instance, at the start i will be 8, and r will be set to r=b[2]&b[4]&b[6]  - which is the diagonal winning combo spanning from the top right corner of our board to the bottom left corner. Remember – in JS multiplying a numerical char string by 1 will cast as an integer value.

The code takes advantage of the following truths: 

Any combos of  the Xs/Os AND 0 will be 0
1 AND 2 will be 0
1 AND 1 will be 1
2 AND 2 will be 2

Here's the gist of it: the only time when r will set to a non-zero value is when each of the three board elements we AND together are all non-zero and the same value, aka either all 1s (aka all ‘X’s) or all 2s (aka all ‘O’s). When r is set to a non-zero value then the evaluation of the !r within the while loop will be false and thus break the loop. Otherwise, r will be set to zero, !r will evaluate to true, and the loop will go on.

So in the end my version was 7 bytes shorter than the JS implementation I had found on stackoverflow. I have a feeling that utilizing some other JS constructs could knock the footprint on that by at least another ~20-30 lines of code. Perhaps someone will incorporate this into a full-fledged golfed tic-tac-toe game.

If you have your own version you’d like to share please feel free to include it in a comment below!