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.