In a place where your fantasy can roam free, there won't be any boundaries to what your imagination can create.
Misha’s Tech Playground
graphics, fun and code play
I'm crazy - but who cares? My ideas are constantly dwelling and this is the place for them to pour out and form into something good. Only active participation will ultimately make this place come to life.
Your Own JavaScript Data Structures
Some Data Goodies
To keep one or the other occupied I thought why not give away some insights on how to implement advanced data structures in JavaScript. Read on to learn how to use Stacks, Vectors and various types of linked lists in your JavaScript Application - complete with Source code.
The Problem
Beside primitive types, Javascript has only built in Objects and Arrays (which themselves are Objects internally as well). While this is a convenience drawback, this also results in a great flexibility. This article will show you how to implement your own data structures utilizing JavaScript object's prototype property to create your own data types. I've added all objects to my global Object CGE, you might need to adjust that to fit your code.
Although not necessary for these Objects to work, I'll also provide a version of each Object that was made utilizing the AJS.Class constructor, thus only working when the AJS Library is present.
A possible Solution
The source provided here is uncommented, though the function signatures should speak for themselves. Most implementations are taken straight out of the wikipedia entry on linked lists. A reference is provided with each implementation.
A Stack
The true nature of a stack is simply to push things on it and the pop them off again in reverse order. Though an array in nature, the wrapper hides everything that could compromise the data integrity. Therefore the stack works according to the Last In First Out (LIFO) principle. Java 5.0 API Doc: Class Stack
-
var stck = new CGE.Stack();
-
stck.push("one");
-
stck.push("two");
-
var topElm = stck.pop(); // two
A Vector
Unlike Java's Vector, my implementation inherits from Stack (Java implements it the other way 'round). Thus only vectors get random access.
The vector is implemented using JavaScript's built in array, but wraps an object around providing limited accessor functions to ensure data integrity. Basically this implementation of vector is a stack with random access. The big disadvantage is that adding or deleting elements not at the end will be a lot slower than with a list for example.
-
var vec = new CGE.Vector(2);
-
vec.append("one");
-
vec.append("two");
-
var elm0 = vec.valueAt(0); // one
A Queue
A Queue works like the line at a ticket counter. The first to come is the first going to be served, or in professional terms First In First Out (FIFO)
This implementation uses the technique proposed by Safalra (Stephen Morley)
-
var queue = new CGE.Queue();
-
queue.enqueue("one");
-
queue.enqueue("two");
-
var nextInLine = queue.dequeue(); // two
A Linked List
This is, simply put, a chain of elements, where each element contains a pointer to it's successor and to it's own data.
A linked list cannot be accessed at random, but can be modified much faster than an array, because adding a node requires to change 2 pointers, whereas using an array would require to change as many indices as would be followed by the inserted node. Wikipedia: Singly Linked Lists
-
var list = new CGE.LinkedList();
-
list.insertFirst(new CGE.ListNode("one"));
-
list.insertAfter(list.getFirst(), new CGE.ListNode("two"));
-
var first = list.getFirst();
-
var second = first.next;
A Doubly Linked List
This is generally the same as a linked list that contains additional methods and is also traversable backwards because it's node also contain a pointer to it's predecessor in the chain. Wikipedia: Doubly Linked Lists
-
var dList = new CGE.DoubleLinkedList();
-
dList.append(new CGE.ListNode("one"));
-
dList.append(new CGE.ListNode("two"));
-
var second = dList.getFirst().next;
-
var first = second.prev;
A Circular Doubly Linked List
This works the same as a doubly linked list, but additionally links the first and last node to form a circular reference. Wikipedia: Circularly Linked Lists
-
var circList = new CGE.CircularDoubleLinkedList();
-
circList.append(new CGE.ListNode("one"));
-
circList.append(new CGE.ListNode("two"));
-
var second = circList.getFirst().next;
-
var first = second.prev;
-
// second.next works too, because second is last in list
The Source
Tags: JavaScript, oop
Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat. Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi.
Leave a Reply