| JavaScript - Object Methods | | Print | |
The usefulness of linked lists in computer science has been mentioned in previous chapters without actually producing a working definition of linked lists. What follows is a working example of a JavaScript linked list class that encapsulates the native Array class. This example demonstrates two very important concepts: how to create custom objects and how encapsulation works.
<html>
<head>
<title>
JavaScript Professional Projects - Linked Lists
</title>
<script language="JavaScript">
<!--
function pop()
{
return( this.data.pop() );
}
function push( value )
{
this.data.push( value );
}
function insertAt( index, value )
{
var part1 = this.data.slice( 0, index );
var part2 = this.data.slice( index );
part1.push( value );
this.data = part1.concat( part2 );
}
function removeAt( index )
{
var part1 = this.data.slice( 0, index );
var part2 = this.data.slice( index );
part1.pop();
this.data = part1.concat( part2 );
}
function size()
{
return( this.data.length );
}
function display()
{
document.write( "<table border=1 cellpadding=5 cellspacing=2
width=50%>" +
" <tr>" +
" <td>" +
" <b><code>Linked List Size = " +
this.size() + "</code></b>" +
" </td>" +
" </tr><tr>" +
" <td>" );
if( this.size() == 0 ) document.write( "No data" );
document.write( this.data.join( "</td></tr><tr><td>" ) );
document.write( "</td></tr></table>" );
}
function List()
{
this.data = new Array( 0 );
this.pop = pop;
this.push = push;
this.size = size;
this.display = display;
this.insertAt = insertAt;
this.removeAt = removeAt;
}
// -->
</script>
</head>
<body>
<center>
<font size=6>JavaScript Professional Projects</font><br>
<font size=4>Chapter 5: Linked Lists </font>
</center>
<br><br>
<script language="JavaScript">
<!--
var linkedList = new List();
linkedList.display();
document.write( "<br><br>" );
for( i = 0 ; i < 5 ; i++ )
{
linkedList.push( Math.random() );
}
linkedList.display();
document.write( "<br><br>" );
for( i = 0 ; i < 5 ; i++ )
{
linkedList.insertAt( 3, Math.random() );
}
linkedList.display();
// -->
</script>
</body>
</html>
In this example, the user-defined class List encapsulates the native class Array. The new class contains a property of type Array. The user-defined methods make use of the Array property by calling its built-in functions. This all goes on behind the scenes without the user of the new class knowing, or needing to know, exactly how it was implemented.
The pop() and push() methods of the List class each make a call to the built-in method of the Array object data to insert or remove an item from the list:
function pop()
{
return( this.data.pop() );
}
function push( value )
{
this.data.push( value );
}
The methods insertAt() and removeAt() have been discussed extensively in previous chapters. They insert or remove a value anywhere in the list. Even these methods, which have no parallel method in the Array object, make extensive use of the Array object's built-in methods. The size() and display() methods create a shortcut for using the list data that would otherwise have made this example much longer. The size() method simply returns the size of the data Array property of the list. The display() method cleanly displays the entire contents of the list in an HTML table.
There are two other very simple dynamic data types that can be created in a similar way. A Stack is essentially a linked list in which you can only add and remove values from the top. An implementation of a Stack class would be
function pop()
{
return( this.data.pop() );
}
function push( value )
{
this.data.push( value );
}
function size()
{
return( this.data.length );
}
function display()
{
document.write( "<table border=1 cellpadding=5 cellspacing=2
width=50%>" +
" <tr>" +
" <td>" +
" <b><code>Stack - Size = " +
this.size() + "</code></b>" +
" </td>" +
" </tr><tr>" +
" <td>" );
if( this.size() == 0 ) document.write( "No data" );
document.write( this.data.join( "</td></tr><tr><td>" ) );
document.write( "</td></tr></table>" );
}
function Stack()
{
this.data = new Array( 0 );
this.pop = pop;
this.push = push;
this.size = size;
this.display = display;
}
The other useful dynamic data type is a queue. Queues allow you to add values to one end of the linked list and remove them from the other. An implementation of the Queue class would be
function dequeue()
{
return( this.data.pop() );
}
function enqueue( value )
{
this.data.unshift( value );
}
function size()
{
return( this.data.length );
}
function display()
{
document.write( "<table border=1 cellpadding=5 cellspacing=2
width=50%>" +
" <tr>" +
" <td>" +
" <b><code>Queue Size = " +
this.size() + "</code></b>" +
" </td>" +
" </tr><tr>" +
" <td>" );
if( this.size() == 0 ) document.write( "No data" );
document.write( this.data.join( "</td></tr><tr><td>" ) );
document.write( "</td></tr></table>" );
}
function Queue()
{
this.data = new Array( 0 );
this.dequeue = dequeue;
this.enqueue = enqueue;
this.size = size;
this.display = display;
}
All three dynamic data types—linked lists, stacks, and queues—are very handy tools to have. The dynamic quality of these classes creates less of a memory drain when compared to static arrays.
Object Constructors
When creating custom classes, the constructor method must always be present. The constructor method constructs, or initializes, an instance of a class. In the linked list example above, the constructor
function List()
{
this.data = new Array( 0 );
this.pop = pop;
this.push = push;
this.size = size;
this.display = display;
this.insertAt = insertAt;
this.removeAt = removeAt;
}
has the same name as the class it is used to construct—in this case List. Constructors are generally used to initialize local properties such as
var data = new Array();
This property will be available to all other methods of the initialized object just like any other object property. The only difference between constructors and other methods and functions is that a constructor should never return a value.
| Users' Comments (0) |
|
No comment posted
