Introduction

As software engineers, we understand why data structures are important. Data structures provide a way to store complex and big datasets thus enabling one to design efficient algorithms.

Some problems in software engineering may have constraints, which require that you think and evaluate available data structure to pick one that will meet the constraints.

If you have a software engineering problem, just know that there is always a data structure that will make it very easy to solve.

Although, it is crucial to understand how to design any abstract data structure, it may take time. Therefore, when writing algorithms, it is important to be aware of the already implemented data structures so that you are productive.

There are three important things you need to always remember when you think about data structures;-  

  • Name of a data structure.
  • The operations you can perform on that data structure.
  • A unique characteristic, which is why such a data structure exists.  

Objectives of this walk-through    

  • To identify all the implemented data structures in Java programming language.
  • To solve at least one Software Engineering problem (write an algorithm) using the identified data structure. Although we will not discuss about time complexity and space complexity, the solutions we will discuss here will be most efficient.
  • To provide a link to the specific data structure's Java documentation.
  • To propose freely available platforms that you can use to better your skill in solving software engineering problems.
Keep in mind that similar data structures implemented in different languages may behave differently. For instance a Java array and JavaScript array

Prerequisite

  • A basic understanding of Java programming language (Object Oriented programming and an understanding of functions or methods).
  • Ensure you have a Java IDE in your computer.  
  • Ensure you have installed Java JDK (minimum: for Java SE) or simply ensure you can run java programs in your machine.  
  • A basic understanding of algorithm running time and space complexity.
  • A basic knowledge of abstract data structures.

We will look at an Array, 2D-Array, Linked List and List, Stack, Queue, Priority Queue, HashTable together with HashMap, HashSet, LinkedHashMap, , LinkedHashSet, Trees, Graphs, heap, etc...

Let's start with a teaser :)

In each of the following descriptions, identify the most appropriate data structure to use to achieve the functionality. Try it out first. The answers are at the end of this tutorial. What was your score? Let me know at the comments section.

  1. You need to store social network “feeds”. You do not know the size, and things may need to be dynamically added.
  2. You need to store undo/redo operations in a word processor.
  3. You need to store the friendship information on a social networking site. i.e., who is friends with who.
  4. You need to store and then retrieve information in constant time (i.e. O(1)).
  5. Keep the order of incoming calls in a call center, where calls have varying priorities.
Let me remind you that mastering data structures does not mean you will become good in problem solving. You must actually know what you want to do for you to identify the appropriate data structure. You must learn some techniques over time of practice.  

For all of the problems, we will write java functions to solve them

1. Java array - fixed size list or 1D- array

An array is a very common data structure with numerous applications. You store multiple values (of any data type) in an array.

The array size must be known in advance before items are added.

The items in the array are identified using an index, which starts at 0 to n-1, where n is the length of the array.

We declare a java array, which holds integer values, as follows:

int [] myArray = new int [5]; //Size of array if 5

You can learn more about java arrays here. Additionally, learn more about Java Arrays class, which has many methods that you can use to manipulate array data structure.

Sample problem 1:

Two Sum problem - Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number  (there is no guarantee that the 2 numbers exist) e.g.

Input: numbers = [2,7,11,15], target = 9

Output: [2,7] because 2 and 7 adds up to 9 (we are supposed to return an array of size 2 containing the numbers). Find a complete description of this problem here.

We can use a two pointer approach as below:

/**
 * 
 * @param nums the array 
 * @param target target sum 
 * @return array containing the numbers
 */
public int[] twoSum(int[] nums, int target) {
	int n = nums.length;
	//rightPointer starts from right moving left
	int rightPointer = n-1;
	//leftPointer starts from the left moving right 
	int leftPointer = 0;
	
	while (leftPointer < rightPointer) {
		int sum = nums[leftPointer] + nums[rightPointer];
		if (sum == target){
			//return these number in an array
			return new int[] {nums[leftPointer],nums[rightPointer]};
		}else if (sum < target) {
			//we need to move leftPointer rightwise
			leftPointer ++;
		}else {
			//move rightPointer leftwise 
			rightPointer--;
		}
	}
	//return null if the numbers were not found
	return null;
}

We solved the problem in linear time, O(n) and constant space, O(1). If the array was unsorted, the solution we provided will not work!

When you use Java language, a Java String (a group of characters) is something that you will frequently use. However, it is advisable to convert a string to character array for convenience. It can be as shown below;-

String str = "something";
//We convert a string to an array of characters. 
char [] strArray = str.toCharArray();
Java does not support associative array, however such a characteristic can easily be achieved using a Map.  

2. Two Dimensional Array

Unlike in a 1-D array, a 2-D array is a multidimensional array also known as a matrix, and you require 2 indices to read a value.

It is like a table having rows and columns.  

We declare a Java 2-D array as follows:

int[][] myNumbers = new int[3][3]; //a 2-D array with 3 rows and 3 columns

There is a good explanation of a 2D-array in the video below.

Sample problem 2:

A Sudoku board can be represented as a 9x9 matrix. It is valid if the following three conditions are met:

i) Each row contains unique values from 1-9.

ii) Each column contains unique values from 1-9.

iii) Each of the 9 sub-squares, of size 3x3, ​contains a unique value from 1-9.

If you are given a solved Sudoku, can you check if it is correctly solved?

int [][] board = {		{ 3, 1, 6, 5, 7, 8, 4, 9, 2 }, 
            			{ 5, 2, 9, 1, 3, 4, 7, 6, 8 }, 
            			{ 4, 8, 7, 6, 2, 9, 5, 3, 1 },        				
            			{ 2, 6, 3, 4, 1, 5, 9, 8, 7 }, 
            			{ 9, 7, 4, 8, 6, 3, 1, 2, 5 }, 
            			{ 8, 5, 1, 7, 9, 2, 6, 4, 3 },        				
            			{ 1, 3, 8, 9, 4, 7, 2, 5, 6 }, 
            			{ 6, 9, 2, 3, 5, 1, 8, 7, 4 }, 
            			{ 7, 4, 5, 2, 8, 6, 3, 1, 9 }
        				}; 

Although we have not discussed a HashSet data structure, we will be forced to use it here. A set is a data structure, which does not allow duplicates (see Sudoku condition number ii).

Solution:

We will write a function, which checks the rows and columns. Each of these functions must receive the Sudoku board, where the check starts and where it end.

public boolean validSudoku (int [][] board) {
	//check complete rows - starting index 0 - 9
	boolean rows = validRows(board, 0, 9);
	//check complete columns - starting index 0 - 9
	boolean cols = validCols(board, 0, 9);
	
	//check mini-squares i.e. the 3x3, which adds up to 9 sub-squares
	
	boolean miniSquares = true;
	for (int i = 0; i < 9; i=i+3) {
		for (int j = 0; j < 9; j=j+3) {
			miniSquares = miniSquares && validRows(board, i, i+3) && validCols(board, j, j+3);
		}
	}
	
	return rows && cols && miniSquares; 
}

public boolean validRows(int [][] board, int start, int end) {
	//Set<Integer> set = new HashSet<Integer>();
	for (int i = start; i < end; i++) {
		Set<Integer> set = new HashSet<Integer>();
		for (int j = start; j < end; j++) {
 			if (!validRange(board[i][j])) {
				return false;
			}
			if(!set.add(board[i][j])) {
				return false;
			}
		}
	}
	return true;
}

public boolean validCols(int [][] board, int start, int end) {
	
	for (int i = start; i < end; i++) {
		Set<Integer> set = new HashSet<Integer>();
		for (int j = start; j < end; j++) {
			if (!validRange(board[j][i])) {
				return false;
			}
			if(!set.add(board[j][i])) {
				return false;
			}
		}
	}
	return true;
}

public boolean validRange(int num) {
	if (num>0 && num<=9) {
		return true;
	}
	return false;
}
validSudoku is the function to be called. Pass it the solved Sudoku board and it will delegate to validRows and validCols methods 

3. Java LinkedList

Unlike the array, where values are stored together  in sequential memory location, a Linked List stores values (called nodes) and each value is linked to the next value.

There are two pieces of information stored about a node, the value and the address to the next value.

With a linked list, you do not need to specify the size thus it is appropriate when you want to store streaming data whose size is unknown.  

Types of a linked lists. There is a third type called circular linked list.

Java implements a doubly-linked list, LinkedList class

LinkedList can be created as shown below:

//A linked list,which stores integers 
//using LinkedList
LinkedList<Integer> lList = new LinkedList<Integer>();
//Implementing List interface
List<Integer> lList = new LinkedList<Integer>();

Sample problem 3:

You are storing room temperature readings and you thought you could use an array to do so (the array will get full if you have more readings than its size). Write a function, storeReadings, which receives an array of temperature readings (array is size n) and then adds all the readings to a linked list so that you can continue adding more readings to the linked list. You must maintain the order in which the readings were taken.  

A linked list is appropriate because a it will keep the order.

/**
 * 
 * @param readings temperature readings in an array
 * @param n size of array
 * @param newReadings LinkedList to hold temperature readings 
 * @return LinkedList<Double>
 */
public LinkedList<Double> storeReadings(double [] readings, int n, LinkedList<Double> newReadings) {
	//iterate through the array and add array elements into newReadings linked list
	for (int i = 0; i < n; i++) {
		newReadings.add(readings[i]);
	}
	return newReadings;
}

 Which two properties of a linked list did we use to decide that it is appropriate?

  • It maintains element insertion order.
  • You do not need to specify the size beforehand.

4. Java ArrayList, mostly implements the List Interface

We can use it to solve the problem we solved using a linked list.

A part from sharing characteristics with a Java LinkedList, its values are indexed, just like an array.

See a discussion here and here to understand when to use LinkedList and when to use ArrayList.  

Lets write storeReadings but this time using an ArrayList.

/**
 * 
 * @param readings readings temperature readings in an array
 * @param n size of array
 * @param newReadings List/ArrayList to hold temperature readings 
 * @return List<Double>
 */
public List<Double> storeReadings(double [] readings, int n, List<Double> newReadings) {
	//iterate through the array and add array elements into newReadings  list
	for (int i = 0; i < n; i++) {
		newReadings.add(readings[i]);
	}
	
	return newReadings;
}

Sample problem 4: involving an array and a List

You are given an array of integer numbers sorted in an ascending order. Some of the numbers appear twice. Write a function called, duplicates which returns the numbers, which are repeated. For instance;-

input: [1,2,4,4,5,8,8,9,11,21,21]

output: 4,8,21, because these numbers appear twice.

Intuition:

  • Let the input array be a,
  • Because the array is sorted, we know that if element appearing at index i is equal to that at index i+1, then we need to include a[i] in the output.
  • Secondly, because we do not know the number of elements to return (those appearing twice), we cannot use an array. We need one that expands as we add more elements. That is a List or a LinkedList. A linked list could take more space because of the address part and its sequential access is slow. So we settle on a List.
public List<Integer> duplicates (int a []) {
	List<Integer> list = new ArrayList<Integer>();
	//We loop up to size <a.length-1 since if are at 
	//i = a.length-1 and we are checking i+1, we will get an error
	//i.e. ArrayIndexOutOfBounds exception 
	for (int i = 0; i < a.length-1 ; i++) {
		if (a[i] == a[i+1]) {
			list.add(a[i]);
		}
	}		
	return list;
}

5. Java Stack

The Stack Java class represents a last-in-first-out (LIFO) stack of objects.

Simply, if you want a data structure where you insert elements and when you want to remove them, you start with last inserted element.

A stack can solve interesting problems such as reversing a word or solving valid parenthesis problems.

Sample problem 3:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

The intuition is that:

  • Every opened bracket must be closed by the same type of bracket.
  • It means that an opening bracket cannot start
  • For each type of bracket, the number of opening brackets is equal to the number of closing brackets.
  • For each type of bracket, the last opened bracket must be closed first - you can see LIFO here.  

The solution will be something like this:

public boolean isValid(String parenthesis) {		
	Stack<Character> stack = new Stack<Character>();
	for (int i =0; i<parenthesis.length();i++) {
		if(parenthesis.charAt(i) =='(' || parenthesis.charAt(i) == '[' || parenthesis.charAt(i) =='{') {
			stack.push(parenthesis.charAt(i));
		}else {
			//Check what is at the top and the incoming; if they match, pop it
			//The stack should be empty if all corresponding closing brackets are encountered
			char top = stack.peek();
			if(top == '(' && parenthesis.charAt(i) == ')' ||
					top == '[' && parenthesis.charAt(i) == ']' ||
					top == '{' && parenthesis.charAt(i) == '}') {
				//remove the corresponding closing bracket from the stack
				stack.pop();
				
			}else {
				
				stack.push(parenthesis.charAt(i)); 
			}
		}
	}
	
	//if the parenthesis were valid, then the stack should be empty
	if(stack.isEmpty()) {
		return true;
	}else {
		return false;
	}
}
I also need to remind you that in function call or in recursion, it is the stack that is used to track the order in which functions were called. The last function to be called is the first function to complete execution.

6. Java Queue

A queue data structure represents a first-in-first-out (FIFO) structure.  

A Java Queue is an Interface, which is commonly implemented by a LinkedList.

Sample problem 6: Breadth First Search (BFS) in a binary tree

A binary tree is a data structure.

So you are given a binary tree (We will see how a binary tree is represented using a java class) and you are required to perform a BFS traversal in linear time, O(n) and linear space O(n).

BFS is also called Level Order Tree Traversal.

Binary tree Level Order Tree Traversal

The binary tree, TreeNode is defined as shown below

public class TreeNode {
	int value;
	TreeNode right;
	TreeNode left;
	public TreeNode(int val) {
		this.value = val;
		this.right = null;
		this.left = null;
	}
}
Binary tree definition

From the binary tree above, we start with node 10, then children of 10, which are 5 and 30. We proceed to visit children of 5, because 5 was the first child of 10 that was visited. You realize that a queue will be good in tracking the node that was visited ahead of others so that we can visit its children.

Our BFS solution will look like this:

public void BFS(TreeNode root) {
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	if (root == null) {
    	//Nothing to print. Terminate function execution.
		return;
	}
    
    //enqueue the root
	queue.add(root);
	
	while (!queue.isEmpty()) { //We will stop when the queue is empty
		//Access the element at the head and dequeue it (poll)
        TreeNode head = queue.poll();
		//output it 
		System.out.print(head.value + " ");		
		
		if (head.left != null) {
        	//enqueue left child if it exists
			queue.add(head.left);
		}
		
		if (head.right != null) {
        	////enqueue right child if it exists
			queue.add(head.right);
		}
	}
}
Binary tree Breadth First Search (BFS)

7. Java PriorityQueue

A Java PriorityQueue is based on a heap. Specifically, this class implements a min heap.

If you need quick and complete information about min heap and a max heap, checkout the following video.

Sample problem 7: Leetcode problem number 1046 - Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.) e.g.

Example 1:

Input: [2,7,4,1,8,1]

Output: 1

Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

The solution you think about immediately you finish reading the problem is that, every time you take a turn, you sort the array - of course this is correct.

But you can easily use a heap. Because, in each turn, we are interested in the two biggest stones, then we can use a min heap but the numbers must be converted to negative, so that bigger numbers are at the top of the heap.

The process repeats until there is one item remaining in the PriorityQueue (min heap)

The solution will look like as shown below:

public int lastStoneWeight(int[] stones) {
	PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
	
	for(int stone: stones) {
		//negate so that the largest number has the highest priority 
		pq.add(-stone);
	}
	
	while(pq.size()>1) {
		int largeStone = -pq.remove();
		int secondLatgestStone = -pq.remove();
		if(largeStone != secondLatgestStone) {
			//add back the difference
			pq.add(-(largeStone - secondLatgestStone));
		}
	}
	if(pq.size() == 0){
		return 0;
	}
	return -pq.remove();
}

Another problem you can solve using a Priority Queue can be found here. This problem tests your ability to design a new data structure from existing ones and define operations on that data structure.

You can implement a max heap using a PriorityQueue by providing a custom comparator to the PriorityQueue constructor.

8.  Heaps

In Java, a heap data structure is implemented as a PriorityQueue and we have already explained it.

9. Java HashTable and HashMap/Map

When you hear of a hash table or hash map, you immediately remember an implementation of an associative array like data structure, which maps keys to values

They facilitate fast lookup - they actually afford constant time O(1). You just need to know the key.

One thing you need to notice is that, when you put items into these data structures, there is no guarantee that it will preserve the order of insertion.

Find out the difference between a Java Hash Map and a Java Hash Table here.

Sample problem 8: Lucky Integer

Given an array of integer numbers, a lucky number is the number whose frequency in the array is equal to the number itself. e.g.

input: [7,3,3,2,6,6,3,9,1,0,1]

output: 3; 3 appears three times.  

Return zero if a lucky number cannot be found.  

Intuition:

The challenge we face here is that we need to find a way to store a number and how many times it appears i.e. key and value. Java does not support associative array but we know a hashtable of hashmap can do this.

We could use an array, i.e. we put the frequency of a number in the index of that number e.g. at index 3, we put the frequency of 3. This would be inefficient because we will have to determine the largest number in the array, create an array of that size. However, some numbers may not appear in the input array.

Additionally, we choose a hash map because of fast look-up.

Our solution would be something like this:-

public int luckyInteger (int [] arr) {
	//Space: O(N); Time: O(N)
	if (arr.length == 0) {
		return -1;
	}
	//create a map <number, frequency>		
	//number is the value in the array and 
	//frequency is the number of times the number appears in the array
	//Map is an interface implemented by HashMap
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	
	for (int num: arr) {
		if (map.containsKey(num)) {
        	//eveytime we encounter a number already in the map, increase its frequency by 1
			map.put(num, map.get(num) + 1);
		}else {
        //Otherwise, put the number into the map and add 1 as its frequency 
			map.put(num, 1);
		}
	}		
	int happyNumber = -1;	
    //Iterate through the map to check which key is equl to its value.
    //This is what we are looking at
    //If we cannot find it, -1 will be returned. 
	for (Map.Entry<Integer,Integer> m : map.entrySet()) {
		if(m.getKey() == m.getValue()) {
			happyNumber = Math.max(happyNumber, m.getValue());
		}
	}
	return happyNumber;
}
Solving lucky Integer problem using a hashMap: Linear time, O(n) and Linear space, O(n)

Another problem you can solve using a hashtable/hashmap is described here.

10. Java HashSet

A Java HashSet implements the Set Interface.

HashSet contains unique elements only - no duplicates, but does not keep the order of element insertion.

Recall how we used a set to check if Sudoku board is filled incorrectly

To create this data structure in java, we can use the HashSet or implement the Set interface.

Set<Integer> set = new HashSet<Integer>();
//Or
HashSet<Integer> set = new HashSet<Integer>();
Declare a set/HashSet variable 

Sample problem 9: check if an array has duplicates

Given an unsorted array, return true if there are duplicates (has numbers appearing more than once), return false otherwise. Can you solve this in linear time, O(n)?

Intuition:

We check the numbers of the array, and for each number, we need to determine if we have seen it before or not. If we see any number more than once, then the array has duplicates. You could use two loops as shown below, but its running time complexity is not linear time.

public boolean hasDuplicates(int a []) {
	int n = a.length;
	if (n <=1) {
		return false;
	}
	
	for (int i = 0; i < a.length; i++) {
		for (int j = i+1; j < a.length; j++) {
			if (a[i] == a[j]) {
				return true;
			}
		}
	}
	return false;
}

This solution's running time complexity is O(n^2)and thus does not meet the requirements above.

We can use a HashSet to help us tell if we have seen a given number before. We can then traverse the array only once, which gives a linear run time.

A solution with linear run time and linear space is shown below;-

public boolean hasDuplicates(int a []) {
	int n = a.length;
	if (n <=1) {
		return false;
	}
	Set<Integer> set = new HashSet<Integer>();
	
	for (int i = 0; i < a.length; i++) {
		if (set.contains(a[i])) {
			return true;
		}else {
			set.add(a[i]);
		}
	}
	//If we successfully added all the elements into the set, then there are no duplicates
	return false;
}

11. LinkedHashMap and LinkedHashSet

Recall that both HashMap and HashSet do not guarantee that the order in which items were added will be preserved.

However, in a linkedList, the order of item insertion is preserved.

A Java LinkedHashMap is a Hash table and linked list implementation of the Map interface, with predictable iteration order.

Similarly, a Java LinkedHashSet  is a Hash table and linked list implementation of the Set interface, with predictable iteration order.

Sample problem 10: LRU cache obtained from Leetcode problem number 146

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

  • LRUCache cache = new LRUCache( 2 /* capacity */ );
  • cache.put(1, 1);
  • cache.put(2, 2);
  • cache.get(1);       // returns 1
  • cache.put(3, 3);    // evicts key 2
  • cache.get(2);       // returns -1 (not found)
  • cache.put(4, 4);    // evicts key 1
  • cache.get(1);       // returns -1 (not found)
  • cache.get(3);       // returns 3
  • cache.get(4);       // returns 4

If you do not understand what Caching is, watch this video.

Understanding caching 

Because the LinkedHashSet keeps the order in which items are placed, we can easily know the item that is least recently accessed - it will be at the head of the linked list.

The complete solution for this problem is explained here.  

Have you noticed that the implemented java data structures are in the java.util package?

12. Binary Tree

A binary tree is a recursive data structure where each node can have 2 children at most.

A binary tree has not been implemented in Java but it can created by using Java class definition and taking advantage of class object address.

See the class representation below:

public class TreeNode {
	int value;
	TreeNode right;
	TreeNode left;
	public TreeNode(int val) {
		this.value = val;
		this.right = null;
		this.left = null;
	}
}

Notice the following:

  • value is the data we store, right is the address pointing to the right child and left is the address pointing to the left child.
  • The data type of an address e.g. left is the class name, which will store the address of an object in memory, when a class instance is created.
  • The constructor creates a node that has a value but with no child - left and right is null.

13. Graph

Just like a tree, Java does not ship with a graph. However, it can be implemented using the data structures we have already described. The two ways of implementing a graph is using:-

  • Adjacency matrix - you use a 2D-Array
  • Adjacency list - using a Java List, which is implemented by Java ArrayList or Java Map - list of a list or map with key as a node and value as a list containing neighbors of key.

Our objective was to review data structures already implemented in Java. Thus, implementing them ourselves is outside the scope of this article. Learn how to implement Graphs in Java using adjacency matrix and adjacency list.

Data structures and algorithms materials to help you sharpen problem solving skills

  1. Leetcode - http://leetcode.com
  2. Hackerrank - http://hackerrank.com
  3. Codility - https://codility.com/
  4. Topcoder - https://topcoder.com/
  5. Geeks for geeks - https://geeksforgeeks.org/
  6. Codechef - https://codechef.com/

Answers to the teaser!

  1. Linked list
  2. Stack
  3. Graph
  4. Hash table
  5. Priority Queue

Voila! We are done.

I will be glad to hear from you in the comments section.

You've successfully subscribed to Decoded For Devs
Welcome back! You've successfully signed in.
Great! You've successfully signed up.
Your link has expired
Success! Your account is fully activated, you now have access to all content.