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

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:

1. Arrays
3. Stacks
4. Queues
5. 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";
}
?>

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:

• Link - Each link to a linked list can store a data usually called an element or similar.

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

####Java

import java.util.*;

int size;

private class Node<E> {
private E data;
private Node<E> next;

private Node(E data) {
this.data = data;
this.next = null;
}
}

this.size = 0;
}

this.size = 1;
}

public void append(E data) {

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

def __init__(self):

def isEmpty(self):

newNode = Node(item)

def size(self):
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count

def search(self, item):
found = False
if current.getData() == item:
found = True
else:
current = current.getNext()
return found

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

if previous == None:
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

def initialize(data)
end

while current.next != nil
current = current.next
end
current.next = Node.new(data, nil)
end

def delete(data)
if current.data = data
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 = []
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;
}

this._length = 0;
}

var node = new Node(value),

if (!currentNode) {
this._length++;
return node;
}

while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
this._length++;

return node;
};

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;
};

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) {
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;

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

public:
}

Node *n = new Node();
n->x = val;
}

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

delete n;
return ret;
}

private:
};

}

####PHP

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

return \$this->data;
}
}

private \$firstNode;
private \$lastNode;
private \$count;

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

public function insertFirst(\$data) {

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

\$listData = array();
\$current = \$this->firstNode;
while(\$current != NULL)
{
\$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{
\$current = \$this->firstNode;
\$previous = \$this->firstNode;

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

\$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)
end

def dequeue
if empty?
nil
else
@tail = @tail.succ

@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  \
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!