JavaScript Day 18: Linked List

Today, I just wanted to try implementing a common construct in JavaScript: the linked list.

In case you are not familiar with it, a linked list is an alternate way of storing and iterating through a collection of objects. Usually in JavaScript, you would use an array for this. However, array access is often quite slow in many languages. It always has been slow in ActionScript, and although I don’t know about it in JS, I assume it is likely the same. A linked list has an initial object that has a link to the next object, which has a link to the next, etc. Hence, “linked list”. Iterating through a linked list generally looks something like this:

[php lang=”JavaScript”]var obj = firstObj;
while(obj != null) {
// do something with obj
obj = obj.next;
}[/php]

Because each link is just a reference to another object, this is very efficient. Much more so than array access. However, it is best suited for iterating over the list from start to finish. While it is possible to get a reference to a specific element in the list, it still requires iterating through the list until you reach the object you want. Thus, arrays are much better for accessing random elements. There’s also a construct which combines the two, getting the best of both.

You can see the whole new script here: http://www.bit-101.com/jscanvas/mar18.js

Let’s go over the key points. First the vars:

[php lang=”JavaScript”]var firstPoint, lastPoint, maxPoints = 100, numPoints = 0, canvas, context, width, height, gravity = 0.1, emitter;[/php]

No more points array and i iterator. But we have a firstPoint and lastPoint var.

Next, let’s jump down to addPoint, so we can see how the list is created.

[php lang=”JavaScript”] function addPoint() {
var point;
if(numPoints < maxPoints) { point = {}; initPoint(point); if(numPoints == 0) { firstPoint = point; } else { lastPoint.next = point; } lastPoint = point; numPoints += 1; } }[/php] As before, we check whether or not we should create a point, and if so, create and initialize it. But instead of pushing it into an array, we make it part of the list. First, if numPoints is 0, then this is the first point we are creating. Thus, we assign it to the firstPoint var. If it's not the first point, then we get the last point and set lastPoint.next to this new point. Finally, we set lastPoint itself to this point and increment numPoints. So if this is the first point we are creating, it is now assigned as both firstPoint and lastPoint. The second point will then be assigned to both firstPoint.next and lastPoint. So each new point is tacked on to the end of the list and then becomes the end of the list. The other changes are in the update and draw functions. [php lang="JavaScript"] function update() { var point = firstPoint; while(point != null) { point.vy += gravity; point.x += point.vx; point.y += point.vy; if(point.x > width ||
point.x < 0 || point.y > height ||
point.y < 0) { initPoint(point); } point = point.next; } } function draw() { var point = firstPoint; context.fillStyle = "rgba(0,0,0,0.05)"; context.fillRect(0, 0, width, height); while(point != null) { context.fillStyle = point.color; context.beginPath(); context.arc(point.x, point.y, point.radius, 0, Math.PI * 2, false); context.fill(); point = point.next; } }[/php] As outlined earlier, both of these functions iterate through the list with the following pattern: [php lang="JavaScript"]var point = firstPoint; while(point != null) { // do something with or to the point point = point.next; }[/php] As you can see, when it reaches the last point, it will assign point.next to point. Since lastPoint does not have a next property, on the next iteration, point will be null and the while loop will end. I haven't done any real world testing in terms of the performance of this. It was really more my intention to implement a known pattern. And it works, so I guess it was successful.