I have a friend who teaches Computer Science. One of the things we've discussed is
the need for students/entry level hires to really understand basic data structures.
This is true even though most popular languages do the basic ones quite well (linked
list, hashtable, queue, stack). A consequence of these things being in most languages
is that many of today's students aren't being required to actually build these data
structures as part of their education. Many problems in the work place involve situations
where one needs to know the characteristics of the data structure in order to implement
the most efficient algorithms. One acquires this knowledge through actually building
the data structures at least once.
I believe that many of the folks who grew up programming for the web are getting to
a point where their script skills will need to fill in these gaps in their education.
Browser apps are approaching desktop applications in terms of presentation, interactivity,
and capability. The next step in the evolution of browser applications will require
developers to have knowledge of the basic data structures and their variance implementation
options. The reason: unlike the desktop languages we all use, the browser's programming
language, JavaScript, doesn't have any of these. (If I'm mistaken, let
me know!)
Right now, I'm reviewing the data structures and algorithms that I learned during
the first two years of college. I'm also trying to bring myself up on my level of
understanding JavaScript. I think that some of these diversions might prove interesting
to the world at large. Today, I've implemented a linked list. A linked list has the
following characteristics:
-
Add at the front or end of the list takes O(1) time.
-
Extraction of the nth element takes O(n) time.
-
Insert at a given position, k, takes O(k) time.
-
Delete at a given position, k, takes O(k) time.
Linked lists are effective when typical usage of the list is in scanning all elements.
A linked list is 'nice' to memory management. That is, the room needed for the list
+ one more linked list node is:
Z = (size of node) = ((size of data) + (reference to next node))
(total memory in use when adding a node) = Z x (number of nodes + 1)
This is an improvement over the typical JavaScript Array type whose worst case characteristics
for adding one more element to the list is
Z = (size of node) = (size of data)
(total memory needed when adding a node) = Z x ((2 + growth size) x number of nodes)
In many algorithms for array growth, the algorithm calls for a doubling of the array's
allocated memory. The reason that so much memory is required is that arrays require
contiguous memory in order to maintain O(1) lookup time at any given element.
A Doubly Linked List Implementation
A doubly linked list is a list that one can use to go both forward and backward from
one node to the next. To accomplish this, I've created three classes:
function LinkedListNode()
{
}
LinkedList.LinkedListNode = {
Data: null,
Next: null,
Previous: null
};
LinkedListNode keeps track of the data, the Next, and the Previous nodes. The algorithms
involved all assume that the linked list Next and Previous members will only be other
LinkedListNodes or null.
function LinkedListIterator(){}
LinkedListIterator.prototype = {
_current: null,
Current: function()
{
var retval = null;
if (this._current
!= null)
{
retval = this._current.Data;
}
return retval;
},
Next: function()
{
if (this._current
!= null)
{
this._current
= this._current.Next;
}
return
this._current
!= null;
},
Previous: function()
{
if (this._current
!= null)
{
this._current
= this._current.Previous;
}
return
this._current
!= null;
},
HasData: function()
{
return
this._current
!= null;
}
};
LinkedListIterator allows one to go forward and backward within a LinkedList. The
iterator can become invalid when it runs off the front or back of the LinkedList.
function LinkedList(){}
LinkedList.prototype = {
_head: null,
_back: null,
_length: 0,
Add: function(data)
{
var newNode = new LinkedListNode();
newNode.Data = data;
if (this._head
== null)
{
this._head = newNode;
this._back = newNode;
}
else
{
newNode.Previous = this._back;
this._back.Next
= newNode;
this._back = newNode;
}
++this._length;
return newNode;
},
RemoveAt: function(index)
{
var currentIndex
= 0;
var nextNode = this._head;
while (nextNode
!= null && currentIndex < index)
{
++currentIndex;
nextNode = nextNode.Next;
}
if (currentIndex
== index)
{
nextNode.Previous.Next = nextNode.Next;
if (nextNode.Next
!= null)
{
nextNode.Next.Previous = nextNode.Previous;
}
}
return nextNode;
},
Length: function(){
return
this._length;
},
InsertAt: function(index,
data) {
var currentIndex
= 0;
var nextNode = this._head;
var newNode = new LinkedListNode();
newNode.Data = data;
if (index == 0)
{
// Insert at head
if (this._head
== null)
{
this.Add(data);
}
else
{
newNode.Next = this._head;
this._head.Previous
= newNode;
this._head = newNode;
++this._length;
}
}
else
if (index
>= this._length)
{
// Add to the end.
this.Add(data);
}
else
{
// Insert in the middle
while (nextNode
!= null && currentIndex < index)
{
++currentIndex;
nextNode = nextNode.Next;
}
if (currentIndex
== index)
{
nextNode.Previous.Next = newNode;
newNode.Previous = nextNode.Previous;
newNode.Next = nextNode;
nextNode.Previous = newNode;
++this._length;
}
}
return nextNode;
},
GetIterator: function(){
var retval = new LinkedListIterator();
retval._current = this._head;
return retval;
}
};
Finally, this is the linked list data structure. It allows you to insert at a given
location, remove a given item, add an item to the end of the list, and can create
a bi-directional iterator to allow you to walk the list from front to back and to
the front again. Since I'm a Windows guy, I tested out the structure using cscript.exe.
function DisplayList(list)
{
var
iterator = list.GetIterator();
if
(iterator.HasData())
{
do
{
WScript.Echo(iterator.Current());
}while(iterator.Next());
}
}
function TestLinkedList()
{
var list = new LinkedList();
list.Add(15);
list.Add("Hello, World!");
WScript.Echo(list.Length());
DisplayList(list);
WScript.Echo("---");
list.InsertAt(1, new Date());
DisplayList(list);
WScript.Echo("---");
list.RemoveAt(2);
DisplayList(list);
WScript.Echo("---");
}
TestLinkedList();
If you need a refresher on linked lists and their variants, Wikipedia
has a good write-up that I won't repeat here.
Visit my site, http://www.scottseely.com/.
