# Overview of Data Structures in Java Programming Language

## 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*;-

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

## 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 aJava arrayandJavaScript 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. **

- You need to store social network “feeds”. You do not know the size, and things may need to be dynamically added.
- You need to store undo/redo operations in a word processor.
- You need to store the friendship information on a social networking site. i.e., who is friends with who.
- You need to store and then retrieve information in constant time (i.e.
*O*(1)). - 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

*is the length of the array.*

`n`

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 supportassociative array, however such a characteristic can easily be achieved using aMap.

## 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`

.

## 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**.

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
is equal to that at index`i`

then we need to include`i+1`

,in the output.`a[i]`

- 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:

- Open brackets must be closed by the same type of brackets.
- 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 orin 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.

The binary tree, TreeNode is defined as shown below

From the binary tree above, we start with node ** 10**, then children of

**which are**

`10`

, **and**

`5`

**We proceed to visit children of**

`30`

. **because**

`5`

, **was the first child of**

`5`

`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: ** **

## 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:-

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.

**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

*is shown below;-*

__linear space__```
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.

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

- Leetcode - http://leetcode.com
- Hackerrank - http://hackerrank.com
- Codility - https://codility.com/
- Topcoder - https://topcoder.com/
- Geeks for geeks - https://geeksforgeeks.org/
- Codechef - https://codechef.com/

## Answers to the teaser!

- Linked list
- Stack
- Graph
- Hash table
- Priority Queue

Voila! We are done.

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