What are the missing data structures in java collections?

Java collections provides APIs for many data structures such as ArrayList, Linkedlist, HashMap. They are very handy for us to use. But there are missing data structures in Java collections that are widely used, but not provided. The developers have to write their own implementations for these data structures. What are the missing data structures in java collections? They are Trees (Binary tree, nary tree, B tree, Trie etc) and graph.

In this post, I provided the implementations of Binary tree, Graph and Trie. They share the same characteristics – composed of nodes. We have to define the node before define the data structure. The implementation include common methods such as add, delete, search and traverse.

1. Binary tree

A tree is a collection of nodes connected by edges. Each node points to a number of nodes. A binary tree has at most two children, we name them left child and right child. The nodes can have zero node, which occurs when the nodes are leaves.

In this implementation, we define a TreeNode first. It has left and right TreeNode. We can simply build tree by calling TreeNode constructor. There are three ways to traverse tree: in-order, pre-order and post-order. In-order traversal: Traverse the left subtree, visit the root, traverse the right subtree.Pre-order traversal: Visit the root, traverse the left subtree, traverse the right subtree.Post-order traversal: Traverse the left subtree, traverse the right subtree, visit the root.

2. Graph

A graph contains a set of nodes and edges. Nodes are used to store and retrieve data. The nodes are also called vertices. Edges are used to connect nodes. In our implementation, we first define class GraphNode, in which it defines the node information and its neighbors.

In Graph class, we define the basic operations, such as addNode, addEdge, search and traverse. For graph traversal, there are two ways – DFS and BFS. Depth First Search (DFS): It starts from the source node, and explores the adjacent nodes as far as possible before backtracking. DFS is usually implemented with recursion or stack. Breath First Search (BFS): It starts from the source node, and explores all its adjacent nodes before going to the next level adjacent nodes. BFS is usually implemented with Queue.

3. Trie

A trie  is a tree-like data structure in which every node stores a character. After building the trie, strings or substrings can be retrieved by traversing down a path of the trie.

Trie can be implemented with linked list, array or HashMap. In this implementation, we use LinkedList. First, we define TrieNode. It contains the information of the node and its children. If a node is the last character of the string, isEnd is true. Otherwise it is false. In Trie class, we have implementation of methods add, delete, search and print. Print is to print all strings in trie, using recursion.

Download Missing Data Structures in Java Collections
Data structures and Java collections
Java coding interview questions series (YouTube)

Comments are closed