Know your algorithms and data structures - in any language

From my previous post, I discussed the importance of knowing simple algorithms every software developer/engineer must grasp as part of their engineering repertoire. In this post, I will be covering topics on common data structures that we normally (or always, should I say) use when implementing our algorithms.

The common ones are the following:

Arrays
Linked Lists
Stacks
Queues
Hash Tables

##Data Structures

###a) Arrays

If you’ve ever been doing some programming for a while, you may have run into this term a lot by now if you ever worked with or seen lots of loop iterations in many codebases. If you haven’t, then I’d suggest now it’s time to take a refresher course on the for loop constructs. After all, that’s what (and why) arrays are built for :).

Arrays are the most prominent and well-known piece of data structure programmers of different programming disciplines have come across with. They are very simple data structures, and you can place any kinds of data types in them from strings to booleans. And they usually have a finite size of holding items. And the most common type of data operations we’ve seen on arrays are manipulating and traversing data hold of items by referencing its indices.

All popular programming languages I know or aware of supports them - such as the following.

####Java

import java.util.*;

public class Array {

   public static void main(String[] args) {
      
      // Declare int array
      int[] myList = {1, 2, 3, 4, 5};

      // Print all the array elements by accessing its iterative index
      for (int i = 0; i < myList.length; i++) {
         System.out.println(myList[i] + " ");
      }
    
   }
}

####Python

#!/usr/bin/python

from array import *

myList = array(‘i', [1,2,3,4,5])

for i in myList:
    print myList[i]

####Ruby

#!/usr/bin/ruby

myList = Array[1,2,3,4,5]

myList.each do |item|
    puts item
end

####Java

var myList = [1,2,3,4,5];

for (var i = 0; i< myList.length; i++ ) {
    console.log(myList[i]);
}

####C++

#include <iostream>
using namespace std;

int main() {
           
   // initialize elements of array n to 0
   int myList[5] = {1,2,3,4,5};

   // output each array element's value                      
   for ( int j = 0; j < 5; j++ ) {
      cout << myList[j];
   }
   return 0;
}

####PHP

<?php
$myList = array(1, 2, 3, 4, 5);

foreach ($myList as $item) {
    echo "$item";
}
?>

###b) Linked Lists

Next, we have a second commonly used data structure called the linked lists. Like arrays, you can also perform data storage and data operations in a similar fashion. The key difference is that its elements are not stored contiguous linearly. Elements are individually linked one after another - and typically the links are called ‘pointers‘. For eg

---------       --------        --------       --------
A | node ---->  B | node ---->  C | node ----> D | node
---------       --------        --------       --------

Given the illustration above, the arrows indicated as pointers thus each element’s pointer is always referenced to the next subsequent element. Each pointer typically represents a node in which an element is stored. Thus we normally depict linked list structure to be a visual representation of chaining of nodes - one node after another.

The key difference is, unlike the arrays, its actual data storage is never finite - meaning it’s not fixed. It can dynamically grow (or shrink) as you see fit. You can easily remove and add items to the list by looking at the current node that will hold the pointer reference we’re interested in.

The key concepts when you start working with linked lists are:

Node - Each link of a linked list contains a link to the next link called a node.
Link - Each link to a linked list can store a data usually called an element or similar.
Linked List - A Linked List contains the connection link to the first link called First.

Here is the list of popular programming languages with their respective linked list implementation.

####Java

import java.util.*;

public class LinkedList<E>{
    Node<E> head;
    int size;

   private class Node<E> {
        private E data;
        private Node<E> next;
        
        private Node(E data) {
            this.data = data;
            this.next = null;
        }
    }
    
    public LinkedList() {
        this.head = null;
        this.size = 0;
    }
    
    public LinkedList(E data) {
        this.head = new Node<E>(data);
        this.size = 1;
    }
   
    public void append(E data) {
        Node<E> tmp = head;
        
        while(tmp.next != null) {
            tmp = tmp.next;
        }
        
        tmp.next = new Node<E>(data);
        size++;
    }

}

####Python

#!/usr/bin/python

class Node:
    def __init___(self, data):
        self.data = data
        self.next_node = None
    
    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, new_data):
        self.data = new_data
        
    def setNext(self, new_next):
        self.next = new_next

class LinkedList:
    def __init__(self):
        self.head = None
    
    def isEmpty(self):
        return self.head == None

    def add(self, item):
        newNode = Node(item)
        newNode.setNext(self.head)
        self.head = newNode
    
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count
    
    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
          if current.getData() == item:
              found = True
           else:
              current = current.getNext()
        return found

    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

####Ruby

#!/usr/bin/ruby

class Node
  attr_accessor :data, :next_node

  def initialise(data, next_node)
    @data = data
    @next_node = next_node
  end
end

class LinkedList
  def initialize(data)
    @head = Node.new(data, nil)
  end

  def add(data)
    current = @head
    while current.next != nil
      current = current.next
    end
    current.next = Node.new(data, nil)
  end

  def delete(data)
    current.next = @head
    if current.data = data
      @head = current.next
    else
      while (current.next != nil) && (current.next.data != data)
        current = current.next
      end
      unless current.next == nil
        current.next = current.next.next
      end
    end
  end

  def return_list
    elements = []
    current = @head
    while current.next != nil
      elements << current
      current = current.next
    end
    elements << current
  end
end

####Javascript

function Node(data) {
    this.data = data;
    this.next_node = null;
}

function LinkedList() {
    this._length = 0;
    this.head = null;
}

LinkedList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;

    if (!currentNode) {
        this.head = node;
        this._length++;
        return node;
    }
  
    while (currentNode.next) {
        currentNode = currentNode.next;
    }
    currentNode.next = node;
    this._length++;
     
    return node;
};

LinkedList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: 'Failure: non-existent node in this list.'};
 
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
  
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
    return currentNode;
};

LinkedList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 0,
        message = {failure: 'Failure: non-existent node in this list.'},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
   
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
   
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length--;
         
        return deletedNode;
    }
   
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }
    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length--;
    return deletedNode;
};

####C++

#include <iostream>
using namespace std;

class LinkedList{
    
    struct Node {
        int x;
        Node *next;
    };


  public:
    LinkedList(){
        head = NULL; 
    }


    void addValue(int val){
        Node *n = new Node();   
        n->x = val;            
        n->next = head;                     
        head = n; 
    }

    int popValue(){
        Node *n = head;
        int ret = n->x;

        head = head->next;
        delete n;
        return ret;
    }


    private:
        Node *head;
  };

}

####PHP

<?php
class ListNode {
    public $data;
    public $next;
    function __construct($data) {
        $this->data = $data;
        $this->next = NULL;
    }

    function readNode() {
        return $this->data;
    }
}

class LinkedList {
    private $firstNode;
    private $lastNode;
    private $count;

    function __construct() {
        $this->firstNode = NULL;
        $this->lastNode = NULL;
        $this->count = 0;
    }

    public function insertFirst($data) {
        $link = new ListNode($data);
        $link->next = $this->firstNode;
        $this->firstNode = &$link;

        /* If this is the first node inserted in the list
           then set the lastNode pointer to it.
        */
        if($this->lastNode == NULL)
            $this->lastNode = &$link;
            $this->count++;
    }

    public function readList() {
        $listData = array();
        $current = $this->firstNode;
        while($current != NULL)
        {
            array_push($listData, $current->readNode());
            $current = $current->next;
        }
        foreach($listData as $v){
            echo $v." ";
        }
    }

    public function reverseList() {
        if($this->firstNode != NULL)
        {
            if($this->firstNode->next != NULL)
            {
                $current = $this->firstNode;
                $new = NULL;

                while ($current != NULL)
                {
                    $temp = $current->next;
                    $current->next = $new;
                    $new = $current;
                    $current = $temp;
                }
                $this->firstNode = $new;
            }
        }
    }

    public function deleteNode($key) {
        $current = $this->firstNode;
        $previous = $this->firstNode;

        while($current->data != $key)
        {
            if($current->next == NULL)
                return NULL;
            else
            {
                $previous = $current;
                $current = $current->next;
            }
        }

        if($current == $this->firstNode)
         {
              if($this->count == 1)
               {
                  $this->lastNode = $this->firstNode;
               }
               $this->firstNode = $this->firstNode->next;
        }
        else
        {
            if($this->lastNode == $current)
            {
                 $this->lastNode = $previous;
             }
            $previous->next = $current->next;
        }
        $this->count--;  
    }

    public function emptyList() {
        $this->firstNode == NULL;

    }

    public function insert($NewItem,$key) {
        if($key == 0){
        $this->insertFirst($NewItem);
        }
        else{
            $link = new ListNode($NewItem);
            $current = $this->firstNode;
            $previous = $this->firstNode;

            for($i=0;$i<$key;$i++)
            {       
                    $previous = $current;
                    $current = $current->next;
            }

               $previous->next = $link;
               $link->next = $current;
               $this->count++;
        }
    }   
}
?>

Bear in mind, there are other three known types of linked lists we should be aware of as well - which are not within the scope of this post.

Singly linked list - we perform forward traversal operation in the list along with the nodes as per our example.
Doubly linked list - we perform both forwards and backwards traversal - using two nodes interlinked instead of one.
Circularly linked list - a linked list where all the nodes are connected in a circular direction ie the last node of the list has the pointer reference to the head node of the list.

There are simply variations of the original linked list implementation as above. You can find other examples online how they’re accomplished. My point here is for you to get comfortable knowing its basic structure well beforehand. Once you have this knowledge grounded, the rest of them are fairly straightforward to implement.

###c) Stacks

Another data structure that is commonly used. And they certainly have their wide array of practical uses.

If you can ever imagine, in the real world, things like a deck of cards or a pile of unwashed dishes in the kitchen are the prime examples of a stack type.

When we shuffle our decks, cards are removed and placed on the top surface of the deck. Or when we start piling up dishes in a stack, the dirty dishes at the top are always the first ones to get washed before moving down rest of the stack. This is the classic characteristic of a stack.

In the programming world, our stack-based operations follow this main principle tightly. Stacks perform insert and removal operations, where we insert items at the end of the list and we remove items at the end of the list. Their respective operations are called “PUSH” and “POP”. Another common terminology to describe this is called “LIFO” or last-in-first-out operations.

We can also perform other operations such as checking if the stack was full or empty (isEmpty) and check the status of the current stack(peek) as well.

Here are the programming languages’ respective stack implementations.

####Java

import java.util.*;

public class Stack {
    private int max_size;
    private long[] stack_array;
    private int top;

    public Stack(int stack_size) {
        max_size = stack_size ;
        stack_array = new long[max_size];
        top = -1;
    }

    public void push(long j) {
        stack_array[++top] = j;
    }

    public void pop() {
        return stack_array[top—];
    }

    public void peek() {
        return stack_array[top];
    }

    public void isEmpty() {
        return (top == -1);
    }

    public void isFull() {
        return (top == max_size - 1);
    }

}

####Python

#!/usr/bin/python

class Stack:
    def __init__(self):
        self.items = []
    
    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

####Ruby

#!/usr/bin/ruby

class Stack
    def initialize(size)
        @size = size
        @stack_array = Array.new(size)
        @top = -1
    end

    def pop
        if empty?
            nil
        else
            popped = @stack_array[@top]
            @stack_array[@top] = nil
            @top = @top.pred
            popped
    end

    def push(item)
        if full? or item.nil?
            nil
        else
            @top = @top.succ
            @stack_array[@top] = element
            self
        end
    end

    def size
        @size
    end

    def look
        @stack_array[@top]
    end

    private
    
    def full?
        @top == (@size - 1)
    end

    def empty?
        @top == -1
    end
end

####Javascript

function Stack() {
    this.array = [];
    this.size = 0;
}

Stack.prototype.push = function(item) {
    this.size++;
    var top = this.size - 1;
    this.array[top] = item;
}

Stack.prototype.pop = function(item) {
    var top = this.size,
        deleted_item;

    deleted_item = this.array[top];
    delete this.array[top];
    this.size--;
    return deleted_item;
}

Stack.prototype.size = function(item) {
    return this.size;
}

Stack.prototype.peek = function(item) {
    var top = this.size - 1;
    return this.array[top];
}

Stack.prototype.empty = function(item) {
    var top = this.size - 1;
    return (top === -1);
}

####C++

#include <string>
using namespace std;

class Stack {

private:
      int top;
      int size;
      int *array;

public:
      Stack(int size) {
            if (size <= 0)
                  throw string("Stack's capacity must be positive");
            storage = new int[size];
            this->size = size;
            top = -1;
      }

      void push(int item) {
            if (top == size)
                  throw string("Stack's underlying storage is overflow");
            top++;
            array[top] = item;
      }

      int peek() {
            if (top == -1)
                  throw string("Stack is empty");
            return array[top];
      }

      void pop() {
            if (top == -1)
                  throw string("Stack is empty");
            top--;
      }

      bool isEmpty() {
            return (top == -1);
      }

      ~Stack() {
            delete[] storage;
      }
};

####PHP

<?php

class Stack {
    protected $stack;
    protected $limit;
    
    public function __construct($limit = 10) {
        $this->stack = array();
        $this->limit = $limit;
    }

    public function push($item) {
        if (count($this->stack) < $this->limit) {
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!');
        }
    }

    public function pop() {
        if ($this->isEmpty()) {
          throw new RunTimeException('Stack is empty!');
      } else {
            return array_shift($this->stack);
        }
    }

    public function peek() {
        return current($this->stack);
    }

    public function isEmpty() {
        return empty($this->stack);
    }
}

###d) Queues

Like stacks, queues also operate similar fashion. But the order of traversal and data operations are slightly different.

Like in real life, before you watch a blockbuster movie, or dine in a popular restaurant or buy a ticket to attend a music concert, you have to line up in a queue like the rest of the crowd do. The people at the front are always served first, people at the back (and others who are late to arrive), will be served last.

Thus queues, in the programming world, are exactly like that.

Queues are operated in “FIFO“ fashion ie first-in-first-out fashion. First items at the front of the queue get removed whilst items are the back continue to get longer as more new items are being pushed at the back. We use “dequeue” and “enqueue” for describing the respective operations.

Again, here are the languages’ queue implementations.

####Java

import java.util.Arrays;

public class Queue<T> {

    private int front;
    private int rear;
    int size;
    T[] array;

    public Queue(int inSize) {
        size = inSize;
        array = (T[]) new Object[size];
        front = -1;
        rear = -1;
    }

    public boolean isEmpty() {
        return (front == -1 && rear == -1);
    }

    public void enQueue(T value) {
        if ((rear+1)%size==front) {
            throw new IllegalStateException("Queue is full");

        } else if (isempty()) {
            front++;
            rear++;
            array[rear] = value;

        } else {
            rear=(rear+1)%size;
            array[rear] = value;

        }
    }

    public T deQueue() {
        T value = null;
        if (isempty()) {
            throw new IllegalStateException("Queue is empty, cant dequeue");
        } else if (front == rear) {
            value = array[front];
            front = -1;
            rear = -1;

        } else {
            value = array[front];
            front=(front+1)%size;

        }
        return value;

    }

    @Override
    public String toString() {
       return java.util.Arrays.toString(array);
    }

}

####Python

#!/usr/bin/python

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

####Ruby

#!/usr/bin/ruby

class Queue
  def initialize(size)
    @size = size
    @stack_array = Array.new(@size)
    @head, @tail = -1, 0
  end
  
  def dequeue
    if empty?
      nil
    else
      @tail = @tail.succ

      dequeued = @stack_array[@head]
      @stack_array.unshift(nil)
      @stack_array.pop
      dequeued
    end
  end
  
  def enqueue(element)
    if full? or element.nil?
      nil
    else
      @tail = @tail.pred
      @stack_array[@tail] = element
      self
    end
  end
  
  def size
    @size
  end
  
  private
  
  def empty?
    @head == -1 and @tail == 0
  end

  def full?
    @tail.abs == (@size)
  end
end

####Javascript

function Queue() {
    this.front = 1;
    this.rear = 1;
    this.array = {};
};

Queue.prototype.size = function() {
    return this.rear - this.front;
};

Queue.prototype.enqueue = function(data) {
    this.array[this.rear] = data;
    this.rear++;
};

Queue.prototype.dequeue = function() {
    var curr_front = this.front,
        curr_rear = this.rear,
        deleted_data;
    if (curr_front !== curr_rear) {
        deleted_data = this.array[curr_front];
        delete this._rray[curr_front];
        this.front++;
        return deleted_data;
    }
};

####C++

include<iostream>
#include<cstdlib>
#define MAX_SIZE 10
using namespace std;

class Queue{
    private:
        int queue_array[MAX_SIZE];
        int front;
        int rear;

    public:
        Queue() {
          front = 0;
          rear = -1;
        }

        void enqueue(int data) {
          queue_array[++rear] = data;
        }

        int dequeue() {
          return queue_array[front++];
        }

        int size() {
          return (rear - front + 1);
        }

        void display() {
          if(!this->isEmpty()){
              for(int i=front; i<=rear; i++)
                  cout<<queue_array[i]<<endl;
          } else {
              cout<<"Queue Underflow"<<endl;
          }
        }

        bool isEmpty() {
          if(front>rear) {
              return true;
          } else {
              return false;
          }
        }

        bool isFull() {
          if(this->size()>=MAX_SIZE){
                return true;
          } else {
                return false;
          }
        }
};

####PHP

<?php

class Queue {

  protected $queue = NULL;
  proctected $limit ;

  public function __construct($limit = -1) {
    $this->queue = array();
    $this->limit = $this->getLimit($limit);
  }

  public function enqueue($item) {
    
    $isInfiniteQueue        = ($this->limit == -1);
    $isSizeSmallerThanLimit = (count($this->queue) < ($this->limit));
    if(($isInfiniteQueue) || ((!$isInfiniteQueue) && $isSizeSmallerThanLimit) ) {
          array_push($this->queue,$item);
    }else {
          throw new Exception('Queue is already full');
    }
  }

  public function dequeue() {
      if(!empty($this->queue)){
          $frontItem   = array_shift($this->queue);
          return $frontItem;
      } else {
          throw new Exception('Trying to dequeue on empty queue');
      }
  }

  public function isEmpty() {
      $isEmpty = empty($this->queue);
      return $isEmpty;
  }

  public function size() {
      $size = count($this->queue);
      return $size;
  }

  public function getLimit($limit) {
      if(!((gettype($limit) == 'integer') && $limit > 0)){
          $limit = -1;
      }
      return $limit;
  }
}

###e) Hash Table

Lastly, we have our linear data structure using a special table that uses key-value store by reference, called “Hash Table”.

It’s coined such a term because its primary concept revolves around indices. Indices are used to store data so that our ability to readily access such data store will be efficiently quick and easy to look up. Data (stored as value) are referenced or flagged with a particular index (or key) in a table so we can search them up by depending on this key-value associative relationship.

It’s much like the same way how you want to look up for certain keywords or phrases by reaching for the index section of a library book and then locate the actual page numbers containing the same words or phrases you identified. Hashtable is analogous to this.

When making associations between the key values and the required hashed keys in a hash table, we require our hashing techniques to do this.

Any hashing computing methods can be done in several ways to make this hash key-value mapping possible, so long as such hashing functions are efficient computable and should uniformly distribute keys without any possible duplication or collision of keys when inserting into a hash table.

For the purpose of this post, our simplest example of it would be to use a modulo operator. This modulo operator is used to take a range of data values to compute their respective key indices.

For eg, let’s say you have a table size of 10 and you have the following:

// Assuming in our array of fixed length of 10, we have the following keys

[1, 2 42, 4, 12, 14, 17, 13, 37]

// Using our modulo operator as our hashing function, we get

1 % 10  = 1
2 % 10  = 2
42 % 10 = 2
4 % 10  = 4
12 % 10 = 2
14 % 10 = 4
17 % 10 = 7
13 % 10 = 3
37 % 10 = 7

// Thus our new index array for the hash table is

[1, 2, 2, 4 ,2 ,4, 7, 3, 7]

Notice, in the example, we do have repeated hashed index values, thus we need to have collision handling techniques to prevent any two or more values that reference the same key. Under such circumstances, we go to our neighbouring array slot to see if the slot is empty. We keep searching for the empty slot until it is found and insert the key value appropriately. Like so.

//some pseudo code

void insertData(some key, some value) {

    hash_key = key % value;
    
    loop the hash table
       if hash_table[hash_key] not empty AND hash_table[hash_key] is not the same as ‘key'
            check the next array slot, calculate new hashed key
       otherwise
            store its respective hash entry into hash_table

}

That’s it.

Finally, their actual implementations are as follows:

####Java

import java.util.*;
/**
* Hash Entry Class
*/

public class HashEntry {
      private int key;
      private int value;
      HashEntry(int key, int value) {
            this.key = key;
            this.value = value;
      }    

      public int getKey() {
            return key;
      }

      public int getValue() {
            return value;
      }
}


/**
* HashMap class that will use the Hash Entry data structure
*/

public class HashMap {
      private final static int TABLE_SIZE = 128;
      HashEntry[] table;
      HashMap() {
            table = new HashEntry[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = null;
      }

      public int get(int key) {
            int hash = (key % TABLE_SIZE);
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] == null)
                  return -1;
            else
                  return table[hash].getValue();
      }

      public void put(int key, int value) {
            int hash = (key % TABLE_SIZE);
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            table[hash] = new HashEntry(key, value);
      }
}

####Python

#!/usr/bin/python

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    def put(self,key,data):
      hashvalue = self.hashfunction(key,len(self.slots))

      if self.slots[hashvalue] == None:
        self.slots[hashvalue] = key
        self.data[hashvalue] = data
      else:
        if self.slots[hashvalue] == key:
          self.data[hashvalue] = data  
        else:
          nextslot = self.rehash(hashvalue,len(self.slots))
          while self.slots[nextslot] != None and \
                          self.slots[nextslot] != key:
            nextslot = self.rehash(nextslot,len(self.slots))

          if self.slots[nextslot] == None:
            self.slots[nextslot]=key
            self.data[nextslot]=data
          else:
            self.data[nextslot] = data 

    def hashfunction(self,key,size):
         return key%size

    def rehash(self,oldhash,size):
        return (oldhash+1)%size

    def get(self,key):
      startslot = self.hashfunction(key,len(self.slots))

      data = None
      stop = False
      found = False
      position = startslot
      while self.slots[position] != None and  \
                           not found and not stop:
         if self.slots[position] == key:
           found = True
           data = self.data[position]
         else:
           position=self.rehash(position,len(self.slots))
           if position == startslot:
               stop = True
      return data

    def __getitem__(self,key):
        return self.get(key)

    def __setitem__(self,key,data):
        self.put(key,data)

####Ruby

#!/usr/bin/ruby

class HashTable
    attr_accessor :store

    def initialize(num_buckets=256)
        @store = [];
        (0...num_buckets).each do |i|
            @store.push([]);
        end
        @store
    end

    def hash_key(key)
        return key.hash % @store.length
    end

    def get_bucket(key)
        bucket_id = @store.hash_key(key)
        return @store[bucket_id]
    end

    def get_slot(key, default = nil)
        bucket = @store.get_bucket(key)
        bucket.each_with_index do |kv, i|
            k, v = kv
            if key == k
                return i, k, v
            end
        end

        return -1, key, default
    end

    def get(key, default=nil)
        i, k, v = @store.get_slot(key, default=default)
        return v
    end

    def set(key, value)
        bucket = @store.get_bucket(key)
        i, k, v = @store.get_slot(key)

        if i >= 0
            bucket[i] = [key, value]
        else
            bucket.push([key, value])
        end
    end

    def delete(key)
        bucket = @store.get_bucket(key)
        (0...bucket.length).each do |i|
            k, v = bucket[i]
            if key == k
                bucket.delete_at(i)
                break
            end
        end
    end

    def list
        @store.each do |bucket|
            if bucket
                bucket.each { |k, v| puts k, v }
            end
        end
    end
end

####Javascript

/**
* Hash Entry
*/

function HashEntry(key, value) {
  this.key = key;
  this.value = value;
  this.nextEntry = undefined;
};

HashEntry.prototype.getKey = function() {
  return this.key;
};

HashEntry.prototype.gettValue = function() {
  return this.value;  
};

HashEntry.prototype.setNext = function(entry) {
  this.nextEntry = entry;
};

HashEntry.prototype.getNext = function() {
  return this.nextEntry;
};

/*
* HashTable
*/

function HashTable(){
  this.tableSize = 100;
  this.table = []; // for holding HashEntry
};

HashTable.prototype.hashFunction = function(input) {
  return input % this.tableSize;
},

HashTable.prototype.put = function(key, value) {
  var hash = this.hashFunction(key);
  var table = this.table;
  if(table[hash] === undefined) {
      table[hash] = new HashEntry(key, value);
  } else {
      var curr = table[hash];
      while(curr.getNext()!==undefined) {
        curr = curr.getNext();
      }
      curr.setNext(new HashEntry(key, value));
  }
},

HashTable.prototype.get = function(key) {
  var hash = this.hashFunction(key);
  var table = this.table;
  var currEntry = table[hash];
  if(currEntry === undefined) return null;
  if(currEntry.getKey() === key) {
    return currEntry.getValue();
  } else {
    while(currEntry.getNext()!==undefined) {
      currEntry = currEntry.getNext();
      if(currEntry.getKey() === key) {
        return currEntry.getValue();
      }
    }
  }
}

####C++

/**
* Hash Entry Class
*/

class HashEntry {
  private:
    int key;
    int value;
  public:
    HashEntry(int key, int value) {
          this->key = key;
          this->value = value;
    }

    int getKey() {
          return key;
    }

    int getValue() {
          return value;
    }
};

/**
* HashMap Class using Hash Entry data structure
*/

const int TABLE_SIZE = 128;
class HashMap {
  private:
    HashEntry **table;
  public:
    HashMap() {
          table = new HashEntry*[TABLE_SIZE];
          for (int i = 0; i < TABLE_SIZE; i++)
                table[i] = NULL;
    }

    int get(int key) {
          int hash = (key % TABLE_SIZE);
          while (table[hash] != NULL && table[hash]->getKey() != key)
                hash = (hash + 1) % TABLE_SIZE;
          if (table[hash] == NULL)
                return -1;
          else
                return table[hash]->getValue();
    }

    void put(int key, int value) {
          int hash = (key % TABLE_SIZE);
          while (table[hash] != NULL && table[hash]->getKey() != key)
                hash = (hash + 1) % TABLE_SIZE;
          if (table[hash] != NULL)
                delete table[hash];
          table[hash] = new HashEntry(key, value);
    }     

    ~HashMap() {
          for (int i = 0; i < TABLE_SIZE; i++)
                if (table[i] != NULL)
                      delete table[i];
          delete[] table;
    }
};

####PHP

<?php

class HashTableNode {
    public $key;
    public $val;

    public function __construct($key, $val) {
        $this->key = $key;
        $this->val = $val;
    }
}

class HashTable {
    private $_array = array();
    private $_size = 10000;

    public function __construct($size=0) {
        $size = (int)$size;
        if ($size > 0) {
            $this->_size = $size;
        }
    }

    public function set($key, $val) {
        $i = $orig_i = $this->_get_index($key);
        $node = new HashTableNode($key, $val);
        while (true) {
            if (!isset($this->_array[$i]) || $key == $this->_array[$i]->key) {
                $this->_array[$i] = $node;
                break;
            }
            // increment $i
            $i = (++$i % $this->_size);
            // loop complete
            if ($i == $orig_i) {
                // out of space
                $this->_double_table_size();
                return $this->set($key, $val);
            }
        }
        return $this;
    }

    public function get($key) {
        $i = $orig_i = $this->_get_index($key);
        while (true) {
            if (!isset($this->_array[$i])) {
                return null;
            }
            $node = $this->_array[$i];
            if ($key == $node->key) {
                return $node->val;
            }
            // increment $i
            $i = (++$i % $this->_size);
            // loop complete
            if ($i == $orig_i) {
                return null;
            }
        }
    }

    private function _get_index($key) {
        return crc32($key) % $this->_size;
    }

    private function _double_table_size() {
        $old_size = $this->_size;
        $this->_size *= 2;
        $data = array(); // new array
        $collisions = array(); 
        for ($i=0; $i < $old_size; $i++) {
            if (!empty($this->_array[$i])) {
                $node = $this->_array[$i];
                $j = $this->_get_index($node->key);
                // check collisions and record them
                if (isset($data[$j]) && $data[$j]->key != $node->key) {
                    $collisions[] = $node;
                } else {
                    $data[$j] = $node;
                }
            }
        }
        $this->_array = $data;
        // manage collisions
        foreach ($collisions as $node) {
            $this->set($node->key, $node->val);
        }
    }
}

That’s all for common linear-type data structures.

The next type of data structures I want to cover in my upcoming post are tree structures, where data are stored along with the nodes, and all nodes are interconnected by edges. Much like how you have an apple tree that has all apples hanging by the tip of their branches - or nodes in our case.

And also, its common algorithms such as binary search trees and heap; and how useful are they when performing faster-searching operations in larger scale regardless the dynamic size of data space can take.

Till then, Happy Coding!

Power of Eloquence

Know your algorithms and data structures - in any language - part 2

Comments