abstract-data-types
The future of this module is that it will be able to return instances of the following abstract data types:
- Queue This is currently implemented
- Linked List This is currently implemented
- Stack This is currently implemented
- Binary Tree
- Binary Search Tree
- Graph
- Hash Table
- Heap
Installation
$ npm install abstract-data-types
Getting Started
The individual abstract data types are instantiated from constructors that exist as properties of the abstract-data-types module. The module can be accessed as follows.
var adt = require('abstract-data-types');
You can instantiate individual abstract data types like this.
var q = adt.createQueue(); // To create an empty Queue
var ll = adt.createLinkedList(); // To create an empty Linked List
var s = adt.createStack(); // To create an empty Stack
var bt = adt.createBinaryTree(); // To create an empty Binary Tree
var bst = adt.createBinarySearchTree(); // To create an empty Binary Search Tree
var g = adt.createGraph(); // To create an empty Graph
var ht = adt.createHashTable(); // To create an empty Hash Table
var h = adt.createHeap(); // To create an empty Heap
The rest of this document explains each of the operations that can be performed these abstract data type instances.
Queue
This Queue is implements all the standard Queue operations. These are:
- enqueue adds a new item to the back of the queue
- dequeue returns the item at the front of the queue and removes it from the queue
- front returns the item at the front of the queue
- size returns the number of items in the queue
- isEmpty determines whether the queue is empty and returns true if it is and false otherwise
Enqueue
The enqueue operation adds a new item to the back of the queue. To do this call the enqueue method on a Queue instance passing it the data item you wish to add to the Queue.
q.enqueue({data: 'item'});
Dequeue
The dequeue method returns the item at the front of the queue and removes that item from the queue. To do this call dequeue on a queue object.
var frontItem = q.dequeue();
If dequeue is called on an empty queue, the following error is thrown.
new Error('adt-queue.dequeue(): Tried to dequeue an empty queue!');
Front
The front method returns the item at the front of the queue, but unlike dequeue it does not remove it from the queue.
var frontItem = q.front();
If front is called on an empty queue, the following error is thrown.
new Error('adt-queue.front(): Tried to get the front of an empty queue!');
IsEmpty
The isEmpty method is a boolean function that, when called on a queue, returns true if the queue is empty and false otherwise.
q.isEmpty();
Linked List
The Linked List implements all of the standard Linked List functions. These are given below:
- add adds a new item to the list at a specific position
- remove removes an item from the list at a specific position
- get returns the item at at a specific position in the list
- size returns the number of items in the List
- isEmpty determines whether the List is empty and returns true if it is and false otherwise
The postion index starts from 0.
Add
The add method takes the item to be added to the list and the position that the item should be added in. If the position is less than or equal to 0, the item is added to the front of the list. If the position is greater than or equal to the size of the list, the item is added to the end of the list.
ll.add(position, item);
Remove
The remove method removes the item at a specific position in the list. If the position requested is less than 0 or geater then or equal to the length of the list, an error is thrown.
ll.remove(position);
Get
The get method returns the item at a specific position in the list. If the position requested is less than 0 or geater then or equal to the length of the list, an error is thrown.
ll.get(position);
Size
The size method returns the number of items in the list.
ll.size();
IsEmpty
The isEmpty method is a boolean function that, when called on a list, returns true if the list is empty and false otherwise.
ll.isEmpty();
Stack
The Stack implements all of the standard Stack functions. These are given below:
- push adds a new item to the top of the stack
- pop returns the item at the top of the stack and removes it from the stack
- top returns the item at the top of the stack and leaves it on the stack
- size returns the number of items in the stack
- isEmpty determines whether the stack is empty and returns true if it is and false otherwise
Push
The push method adds a new item to the top of the stack. It also returns the stack so that push opertations can be chained.
s.push(item);
Pop
The pop method returns the item at the top of the stack and removed it from the stack.
s.pop();
Top
The pop method returns the item at the top of the stack and leaves it on the stack.
s.top();
Size
The size method returns the number of items in the stack.
s.size();
IsEmpty
The isEmpty method is a boolean function that, when called on a stack, returns true if the stack is empty and false otherwise.
s.isEmpty();