Java Programming Examples on Data-Structures

This section covers Java Programming Examples on Datastructure. Every example program includes the description of the program, Java code as well as output of the program.

Hashing is a way to assign a unique code for any variable/object after applying any function/algorithm on its properties. Hash table is a data structure which stores data in an array format & each data value has its own unique index value. Hash tree (or hash trie) is a persistent data structure that can be used to implement sets and maps, intended to replace hash tables in purely functional programming. MinHash is a technique for quickly estimating how similar two sets are. Rolling hash technique search is also known as Rabin-Karp algorithm. The following programs demonstrate the implementation of hash tables chaining with binary trees, list heads, linear probing, singly and doubly linked lists. It also explains the implementation of hash trie and rolling hash.

The following section demonstrates the implementation of Heaps, Binary Heap, Fibonacci Heap, Pairing Heap, Min Heap, Pairing & Ternary Heaps. A heap is a specialized tree-based data structure that satisfies the heap properties. A binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance. Ternary Heap is implemented using concept of D-ary Heap. A randomized meldable heap is a priority queue based data structure in which the underlying structure is also a heap-ordered binary tree. Skew heap is a heap data structure implemented as a binary tree. Heaps are crucial in several efficient graph algorithms such as Dijkstra’s algorithm and in the sorting algorithm heapsort.

The following section contains programs which deal with Array, Vector, Stack, Queue and Linked Lists. Array is an object which contains elements of similar data type. It is a data structure where we store similar elements. Sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. Vectors are commonly used instead of arrays, because they expand automatically when new data is added. It can hold only Objects and not primitive types. Stack is an abstract data type or collection where Push – the addition of data elements to the collection and Pop – removal of data elements from the collection. Queue is a collection of objects on which operations can only be performed at two ends of the queue. They are head and tail. Linked list is a data structure consisting of a group of nodes which together represent a sequences.

The following section contains programs on Segment Tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. Priority queue is an abstract data type which is like a regular queue or stack data structure, but additionally each element has a priority associated with it. BitSet is a class defined in the java.util package. It creates an array of bits represented by boolean values. Bi Directional Mapis a map that preserves the uniqueness of its values as well as that of its keys. This section also explains various other implementation on Bloom filters, CountMinSketch and Tree Set.