Binary Tree Implementation in Java

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

Hashtable Implementation in Java

Hashtable is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket). Instead, most hash table designs assume that hash collisions, different keys that are assigned by the hash function to the same bucket, will occur and must be accommodated in some way (Later we use Linked List data structure, that was discussed in this blog, to remedy this potential problem).

Stack Implementation in Java

A stack is a last-in-first-out (LIFO) data structure: Elements are always removed in the reverse order
in which they were added. The add element and remove element operations are conventionally called push and pop, respectively.

One of the ways to implement a stack is by using a dynamic array, an array that changes size as needed

when elements are added. The main advantage of dynamic arrays over linked lists is that arrays offer random access to the array elements (you can immediately access any element in the array if you know its index). However, operations on a stack always work on one end of the data structure (the top of the stack), so the random accessibility of a dynamic array gains you little. In addition, as a dynamic array grows, it must occasionally be resized, which can be a time-consuming operation as elements are copied from the old array to the new array.

Linked lists usually allocate memory dynamically for each element. Depending on the overhead of the memory allocator, these allocations are often more time consuming than the copies required by a dynamic array, so a stack based on a dynamic array is usually faster than one based on a linked list.

Linked List Implementation in Java

Why Linked Lists?

The linked list is the basis for a number of problems regarding the handling of dynamic data.

Kinds of Linked List

There are three basic kinds of linked list: singly linked lists, doubly linked lists, and circular linked lists. Let's discuss singly linked lists in this post.

Singly Linked Lists

Each data element in the list has a link (a pointer or reference) to the element that follows it in the

list. The first element in a singly linked list is referred to as the head of the list. The last element in such a list is called the tail of the list and has an empty or null link.

Singly linked list

Because the links in a singly linked list consist only of next pointers (or references), the list can be traversed only in the forward direction. Therefore a complete traversal of the list must begin with the first element. In other words, you need a pointer or reference to the first element of a list to locate all the elements in the list.

Bitwise Manipulation in Java

Bitwise Operators

The Java programming language also provides operators that perform bitwise and bit shift operations on integral types.

1. The unary bitwise complement operator "~" inverts a bit pattern; it can be applied to any of the integral types, making every "0" a "1" and every "1" a "0". For example, a byte contains 8 bits; applying this operator to a value whose bit pattern is "00000000" would change its pattern to "11111111".
2. The signed left shift operator "<<" shifts a bit pattern to the left, and the signed right shift operator ">>" shifts a bit pattern to the right. The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand. The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.
3. The bitwise & operator performs a bitwise AND operation.
4. The bitwise ^ operator performs a bitwise exclusive OR operation.
5. The bitwise | operator performs a bitwise inclusive OR operation.

Merge Sort Implementation in Java

Merge Sort

Mergesort is a divide and conquer algorithm and works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

During the Merge Sort process the object in the collection are divided into two collections. To split a collection, Merge Sort will take the middle of the collection and split the collection into its left and its right part.

The resulting collections are again recursively sorted via the Merge Sort algorithm.

Once the sorting process of the two collections is finished, the result of the two collections is combined. To combine both collections Merge Sort start at each collection at the beginning. It pick the object which is smaller and inserts this object into the new collection. For this collection it now selects the next elements and selects the smaller element from both collection.

Once all elements from both collections have been inserted in the new collection, Merge Sort has successfully sorted the collection.

To avoid the creation of too many collections, typically one new collection is created and the left and right side are treated as different collections.

Merge Sort Example - GIF Format

Quick Sort Implementation in Java

Quick Sort

Quick sort is a divide and conquer algorithm. Quick sort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quick sort can then recursively sort the sub-lists.

The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values and separately to the sub-list of elements with greater values.

Quick Sort Example - GIF Format

Bubble Sort Implementation in Java

Bubble Sort

A simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Bubble Sort Example - GIF Format