Tag Archives: Java

Implementing Circular Queue in Java with Arrays

A circular queue is an abstract data type that contains a collection of data which allows addition of data at the end of the queue and removal of data at the beginning of the queue. Circular queues have a fixed size.

Circular queue follows FIFO principle. Queue items are added at the rear end and the items are deleted at front end of the circular queue.

Continue reading Implementing Circular Queue in Java with Arrays

Implementing Doubly Linked List in Java

doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

DLL
A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.

The two node links allow traversal of the list in either direction. Here is java implementation of DLL.

Continue reading Implementing Doubly Linked List in Java

Implementing Binary Search Tree in Java

Binary search trees (BST), sometimes called ordered or sorted binary trees, are a class of data structures used to implement lookup tables and dynamic sets. They store data items, known as keys, and allow fast insertion and deletion of such keys, as well as checking whether a key is present in a tree.

The common properties of binary search trees are as follows:

  • One node is designated the root of the tree.
  • Each internal node contains a key and has two subtrees.
  • The leaves (final nodes) of the tree contain no key. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.
  • Each subtree is itself a binary search tree.
  • The left subtree of a node contains only nodes with keys strictly less than the node’s key.
  • The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
Continue reading Implementing Binary Search Tree in Java

Program to Implement KMP Algorithm in Java

The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a “word” W within a main “text string” S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

Continue reading Program to Implement KMP Algorithm in Java