Category: data-structures

Selecting proper data structures for the realtime problems


As a software engineer you have to have a proper understanding about data structures and the corresponding implementations. In real world application development you need to think about the efficiency of the operations and it should fit for the entire domain that the solution is addressing. So in this blog post Im going to explain some of the data structures implemented in java.

Look at the following class hierarchy.

collections

1. LinkedList –  Use the linked list If you need to maintain the list which is no need random access to the values and needed frequent insertions and deletions.
Insertion and deletion is O(1) and access the (k)th element is O(n).
But remember LinkedList is not thread safe.

2. ArrayList –  Use the array list if you need the random access to the values frequently and same as you don’t need frequent insertion and remove operations.
Access the (k)th element is O(1) and insertion and deletion is O(n).
Same as LinkedList remember ArrayList is not thread safe.

3. Vector –  When you need to maintain thread safety over the ArrayList use the Vector. If you don’t need any synchronization on each and every operations you have to go for ArrayList otherwise it will give bad performance impact on each operation.

4. PriorityQueue –  We know that queue is a first come first serve basis but some times we need to get the things according to the priority. So if you have that kind of problem use the priority queue. But remember PriorityQueue is not thread safe.

5. HashSet –  It is not maintaining the duplicates. When you need to maintain the unique list of objects you can use the HashSet. HashSet allows the NULL Objects but it is not maintain the insertion sequence. If you need to maintain the insertion sequence you have to use the LinkedHashSet.

6. TreeSet –  Same as HashSet this data structure maintain the duplicate free collection and additionally its provide the sorted order of the elements.TreeSet is not allow the NULL objects. Guarantees log(n) time cost for the basic operations add, remove and contains.

7. HashTable –  This data structure is useful when you need to do the insertion, deletion and the quick access to the given element in constant time. All operations are in O(1).Hash tables are not maintain the insertion sequence. I would like to explain the HashTable little bit in depth because this is commonly using in the industry. As an example a router table. When a packet has to be routed to a specific IP address, the router has to determine the best route by querying the router table in an efficient manner.

To use the Hash tables you have to implement the equals(), hashCode() functions the Object type that you are going to store in the HashTable.
hashCode() – as a best practice you have to consider all attributes in the object to generate the hash code. See the following example.

public class Employee {
    int        employeeId;
    String     name;
    Department dept;
 
    // other methods would be in here 
 
    @Override
    public int hashCode() {
        int hash = 1;
        hash = hash * 17 + employeeId;
        hash = hash * 31 + name.hashCode();
        hash = hash * 13 + (dept == null ? 0 : dept.hashCode());
        return hash;
    }
}

Once you call the insert method in the hash table it will calculate the hash value and then store the the data according to the hash value.

 int hashValue = hashCode % hash_table_size;

There are several ways to handle the collisions in hash table.
1. Separate Chaining – Maintain the list in each slot. If there are two objects with same hash value it is going to store in that list. This implementation has extra overhead to maintain the list. Total Performance is depend on the number of elements in the list.

2. Open Addressing – In this approach it is find the next available slot according to the probing function.
Linear prob – h(x), h(x)+1, h(x)+2, h(x)+3,..
Quadratic prob – h(x), h(x)+1^2, h(x)+2^2, h(x)+3^2,..
Double hashing – h(x), h(x)+1*h'(x), h(x)+2*h'(x), h(x)+3*h'(x),..

Delete elements in hash table – If hash table is use open addressing then it is logically delete the value from the table by setting a flag.

Performance of the hash table is denoted by alpha load factor.

 alpha = number_of_elements/table_size;

If hash table is filled we need to do the rehashing. Rehashing is done according to the load factor. If load factor reaches to some level we need to do the rehashing. This is the only disadvantage of the HashTable.

8. HashMap –  Hash map is used when you need to store the elements as key, value pairs.In hash map you cannot duplicate the key but you can duplicate the value with different key. This is not maintain the insertion sequence. If you need to maintain the insertion sequence you have to use the LinkedHashMap. Remember HasMap is not thread safe if you need thread safety over HashMap you have to use the ConcurrentHashMap

8. TreeMap –  If you need to maintain the key, value pairs in sorted order this is the data structure suits for that operation. Its guarantees that the given key value pairs arrange in sorted order according to the compareTo() method in Object type which is stored in TreeMap.

1

Simple LinkedList Implementation with Java Generics


Java generics are introduced with in 2004 J2SE 1.5. This concept is really important and it will help a lot in programing. I’m not going to explain the whole generics concept here but I will use the generics to implement the LinkedList. With the generics you don’t want to do the type casting anymore that will really avoid the runtime exceptions. See the following code snippet and enjoy your programming.


import java.util.Currency;
/**
* LinkList implementation with generics
*
* @author malalanayake
*
* @param <T>
*/
public class LinkedListWithGenerics<T> {
private LinkedNode<T> first;
private LinkedNode<T> last;
private int count;
/**
* Internal linked node implementation
*
* @author malalanayake
*
* @param <T>
*/
private class LinkedNode<T> {
private T data;
private LinkedNode<T> next;
public LinkedNode() {
this.data = null;
this.next = null;
}
public LinkedNode(T obj) {
this.data = obj;
this.next = null;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public LinkedNode<T> getNext() {
return next;
}
public void setNext(LinkedNode<T> next) {
this.next = next;
}
}
public LinkedListWithGenerics() {
LinkedNode<T> newLiked = new LinkedNode<T>();
this.first = newLiked;
this.last = this.first;
}
/**
* Add values to the list
*
* @param data
*/
public void add(T data) {
LinkedNode<T> newData = new LinkedNode<T>(data);
if (this.first.getData() == null) {
this.first = newData;
this.last = this.first;
} else {
this.last.setNext(newData);
this.last = newData;
}
count++;
}
/**
* Remove values from the list
*
* @param data
*/
public void remove(T data) {
LinkedNode<T> current = first;
if (this.first.getData().equals(data)) {
if (this.first.getNext() == null) {
LinkedNode<T> newNode = new LinkedNode<T>();
this.first.setData(null);
this.first = newNode;
this.last = this.first;
} else {
this.first.setData(null);
this.first = this.first.getNext();
}
} else {
boolean wasDeleted = false;
while (!wasDeleted) {
LinkedNode<T> currentNext = current.getNext();
if (currentNext.getData().equals(data)) {
currentNext.setData(null);
current.setNext(currentNext.getNext());
currentNext = null;
wasDeleted = true;
count–;
} else {
current = current.getNext();
}
}
}
}
public void print() {
boolean allPrinted = false;
LinkedNode<T> crr = first;
System.out.print("[");
while (!allPrinted) {
if (crr.getData() != null) {
if (crr.getNext() != null) {
System.out.print(crr.getData().toString() + ",");
LinkedNode<T> crrNext = crr.getNext();
crr = crrNext;
} else {
System.out.print(crr.getData().toString() + "]");
allPrinted = true;
}
} else {
allPrinted = true;
}
}
System.out.println();
}
public int getCount() {
return count;
}
public static void main(String[] args) {
LinkedListWithGenerics<String> linkedLst = new LinkedListWithGenerics<String>();
linkedLst.add("Test");
linkedLst.add("Free");
linkedLst.add("Yes");
linkedLst.add("Me");
linkedLst.print();
System.out.println(linkedLst.getCount());
linkedLst.remove("Me");
linkedLst.print();
System.out.println(linkedLst.getCount());
}
}

view raw

LinkedListWithGenerics.java

hosted with ❤ by GitHub

0

Simple ArrayList Implementation


The post will be useful to keep your mind refresh about the array list implementation. If you are a beginner you have to understand the concepts of simple array list and how it will work.


import java.util.Arrays;
/**
* Simple ArrayList Implementation for Java Beginners
*
* @author malalanayake
*
*/
public class ArrayList {
private Object[] data;
private int count = 0;
private int FIXED_SIZE = 10;
public ArrayList() {
data = new Object[this.FIXED_SIZE];
}
/**
* Get the specific object
*
* @param index
* @return
*/
public Object get(int index) {
if (index < count) {
return data[index];
} else {
throw new ArrayIndexOutOfBoundsException();
}
}
/**
* Add new object to the array list
*
* @param obj
*/
public void add(Object obj) {
if (data.length – count <= data.length / 2) {
this.reSizeArray();
}
data[count++] = obj;
}
/**
* Remove the object from list
*
* @param index
* @return
*/
public Object remove(int index) {
if (index < count) {
Object obj = data[index];
int temp = index;
data[index] = null;
while (temp < count) {
data[temp] = data[temp + 1];
data[temp + 1] = null;
temp++;
}
count–;
return obj;
} else {
throw new ArrayIndexOutOfBoundsException();
}
}
/**
* Resizing the array
*/
public void reSizeArray() {
data = Arrays.copyOf(data, data.length * 2);
}
public int size() {
return count;
}
public static void main(String[] args) {
ArrayList mal = new ArrayList();
mal.add(new Integer(2));
mal.add(new Integer(5));
mal.add(new Integer(1));
mal.add(new Integer(23));
mal.add(new Integer(14));
for (int i = 0; i < mal.size(); i++) {
System.out.print(mal.get(i) + " ");
}
mal.add(new Integer(29));
System.out.println("Element at position 5:" + mal.get(5));
System.out.println("Total List size: " + mal.size());
System.out.println("Removing element at position 2: " + mal.remove(2));
for (int i = 0; i < mal.size(); i++) {
System.out.print(mal.get(i) + " ");
}
}
}

view raw

ArrayList.java

hosted with ❤ by GitHub

1

Simple Linked List Implementation in Java


Data structures are very important in software development and Linked List is one of commonly using data structures in the development. Most of the time people who are new to software engineering they need to implement well known data structure in their point of view to understand the concepts. So I think this code snippet will help for beginners to learn how to implement the LinkedList in Java.

This is a really simple one but you can do some modification on this and make it as advanced structure.


/**
* Class which is provide the linked list facility
*
* @author malalanayake
*
*/
public class LinkedList {
private LinkNode first;
private LinkNode last;
/**
* Class which is contain the data
*
* @author malalanayake
*
*/
private class LinkNode {
private Object data;
private LinkNode next;
public LinkNode() {
this.data = null;
this.next = null;
}
public LinkNode(Object obj) {
this.data = obj;
this.next = null;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public LinkNode getNext() {
return next;
}
public void setNext(LinkNode next) {
this.next = next;
}
}
public LinkedList() {
// creating the first node
this.first = new LinkNode();
this.last = this.first;
}
public LinkNode getFirst() {
return first;
}
public void setFirst(LinkNode first) {
this.first = first;
}
public LinkNode getLast() {
return last;
}
public void setLast(LinkNode last) {
this.last = last;
}
public void add(Object obj) {
LinkNode linkNode = new LinkNode(obj);
// check whether it is the first node
if (this.first.getData() == null) {
this.first = linkNode;
this.last = linkNode;
} else {
this.last.setNext(linkNode);
this.last = linkNode;
}
}
public void remove(Object obj) {
LinkNode currentNode = first;
// If the first object is removing
if (obj.equals(first.getData())) {
// if the one node is there
if (first.getNext() == null) {
this.first.setData(null);
this.first = new LinkNode();
this.last = this.first;
} else {
currentNode.setData(null);
currentNode = currentNode.getNext();
this.first = currentNode;
}
} else {
// In the middle object is removing
boolean wasDeleted = false;
while (!wasDeleted) {
// go for the next node
LinkNode nextNode = currentNode.getNext();
if (nextNode != null) {
if (nextNode.getData().equals(obj)) {
currentNode.setNext(nextNode.getNext());
nextNode = null;
wasDeleted = true;
} else {
currentNode = nextNode;
}
}
}
}
}
/**
* Printing whole list
*/
public void print() {
LinkNode current = first;
boolean isDone = false;
while (!isDone) {
System.out.print(current.data + " ");
if (current.next == null) {
isDone = true;
}
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
// just add
linkedList.add("1");
linkedList.add("2");
linkedList.add("3");
linkedList.print();
// just remove
linkedList.remove("2");
linkedList.print();
// remove the first element
linkedList.add("2");
linkedList.remove("1");
linkedList.print();
// remove the last element
linkedList.add("1");
linkedList.remove("1");
linkedList.print();
}
}

view raw

Linked_List_Implementaion.java

hosted with ❤ by GitHub

3

Blog at WordPress.com.

Up ↑