Introduction to built-in data structures in Java

February 03, 2021 — Technical, Java — 5 min read

In this article, we will understand various built-in data structures used in Java. By the end of this article, you will get an overview of how built-in data structures are more efficient than user-defined data structures in Java.

You will also learn how to work with built-in data structures.

Introduction
Data Structures
Conclusion
Further Reading

Introduction

According to Wikipedia, a data structure is a data organization, management, and storage format that enables efficient access and modification.

More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Built-in vs. User-defined data structures

Data structures like Stack or Queue can be created on our own using other basic data structures. For example, Stacks can be created using Arrays or Linked lists. These are known as User-defined data structures.

Built-in data structures do not require the creation of a data structure from scratch. But, we can make use of prebuilt methods that abstract the working of the data structure.

Using built-in data structures, has improved the productivity of the developer, since writing operations for the user-defined data structures is time consuming, and cannot guarantee the efficiency. Also, built-in data structures are generally written with the most efficient time and space complexities.

Time and space complexities are measures of code that ensures the effective usage of time and memory while running a code snippet. By reducing these complexities, the efficiency of data structures can be improved.

Data structures

Now, let's have a look at a few built-in data structures, and we'll see how to work with them.

ArrayList

In the java.util package, ArrayList is a built-in data structure very similar to Array.

The difference between Array and ArrayList is the size. In Array, the length is fixed, so the memory allocated for storing values is fixed. Whereas, in ArrayList, the list is resizable, that allows the developer to choose a dynamic size. Here, the memory is created dynamically.

Syntax for creating ArrayList:

1import java.util.ArrayList; // Import the ArrayList class
2
3ArrayList<String> list1 = new ArrayList<String>(); // Create an ArrayList object

Before we proceed on with the built-in methods, let's build a user-defined function for displaying all the elements of an ArrayList.

1void printArrayList(ArrayList<String> list) {
2  for (int i = 0; i < list.size(); i ++) {
3    System.out.print(list.get(i) + " ");
4  }
5  System.out.println();
6}

Add elements

When using an Array, we have to manually assign the values or variables to the particular index. But, in ArrayList adding elements to the list is made simpler with the use of the add() method.

Example:

1list1.add("Hello"); // Add "Hello" to the ArrayList
2printArrayList(); // OUTPUT: list1 = ["Hello"]
3list1.add("World"); // Add "World" to the ArrayList
4printArrayList();  // OUTPUT: list1 = ["Hello", "World"]

Output:

1Hello
2Hello World

Update Elements

Updating the elements in Array is similar to addition, where the index of the array is found and replaced with the desired value.

In ArrayList, we use the set(index, value) method to replace the element value at a particular index.

Example:

1list1.set(1, "Welcome"); // Replaces "World" with "Welcome" in list1
2printArrayList();  // OUTPUT: list1 = ["Hello", "Welcome"]

Output:

1Hello Welcome

Removing elements

In Array, the removal of elements is not possible, since the memory allocated is fixed.

In ArrayList, the removal of elements can be done using the remove(int index) method. On specifying the index, the ArrayList removes the element from the memory, and the remaining elements are moved to fill up space. Thus, it is more memory efficient.

Example:

1list1.remove(0); // Removes "Hello" from list1
2printArrayList(); // OUTPUT: list1 = ["Welcome"]
3list1.remove(1); // Remove element from Empty list
4printArrayList(); // Exception

Output:

1Welcome
2java.lang.IndexOutOfBoundsException: Index 1 out of bounds for length 0

Linked lists

Linked lists are linear data structures that are connected using pointers, and holds data. Pointers are used to store and manage the addresses of dynamically allocated blocks of memory. The memory allocation is not contiguous which makes it better than the use of Arrays.

While creating linked lists in Java, we have to create a class to define the structure of every node of the linked list. A sample class demonstrating the creation of pointers in an user-defined linked list is shown below:

1class Node { // Node class containing a single pointer and data
2  Node next; // 'next' is used as pointer
3  int data; // 'data' is used for storing values in the node
4  // Constructor for initializing the variables
5  Node() { 
6    next = null;
7    data = 0;
8  }
9}

In the java.util package, we simplify the tasks of manually creating memory handling by using the LinkedList data structure. It contains pre-defined methods for building a linked list data structure.

Syntax for creating LinkedList data structure:

1import java.util.LinkedList; // Import package
2
3LinkedList<String> list2 = new LinkedList<String>(); // Create new object

Before we proceed with the built-in methods, let's build a user-defined function for displaying all the elements of a LinkedList.

1void printLinkedList(LinkedList<String> list) {
2  for (int i = 0; i < list.size(); i ++) {
3    System.out.print(list.get(i) + " ");
4  }
5  System.out.println();
6}

Adding elements

In the user-defined linked list data structure, when adding new data, we have to manually move the pointers and assign data. Whereas, in the LinkedList data structure, we make use of the add(Object) or add(int index, Object) methods for adding new elements.

Example:

1list2.add("Hello"); // Add "Hello" to the LinkedList list2
2printLinkedList(); // OUTPUT: ["Hello"]
3list2.add("World"); // Add "World" to the LinkedList list2
4printLinkedList(); // OUTPUT: ["Hello", "World"]
5list2.add(1, "Computer"); // Add "Computer" to the LinkedList list2 at index 1
6printLinkedList(); // OUTPUT: ["Hello", "Computer", "World"]

Output:

1Hello
2Hello World
3Hello Computer World

Updating elements

To update elements in the user-defined linked list, we have to traverse the whole linked list from the "HEAD" pointer to update the particular data.

LinkedList data structure abstracts the whole process with the set(index, data) method.

Example:

1list2.set(0, "Welcome"); // Update the string at index 0 to "Welcome"
2printLinkedList(); // OUTPUT: ["Welcome", "Computer", "World"]

Output:

1Welcome Computer World

Removing elements

Similarly, when deleting an element in a user-defined linked list can be cumbersome, where the pointer of the previous element is pointed to the address of the next element. When working with huge data, working with pointers is not simple.

Deletion of an element in a user-defined linked list happens as mentioned in the steps below:

Initialize a pointer node as node = head.
Traverse the linked list until you reach the element (node.next.val != value) that you wish to delete.
On reaching the node, we point the node to node.next.next, which means, we point the previous node to the next node. node = node.next.next.

By using built-in data structures, we can avoid using the remove(Object) method to delete elements from the linked list.

Example:

1list2.remove(1); // Removes "Computer" from list2
2printLinkedList(); // OUTPUT: ["Welcome", "World"]
3list2.remove(0); // Remove "Welcome" from list2
4list2.remove(0); // Remove "World" from list2
5printLinkedList(); // Empty list
6list2.remove(0); // Remove elements from Empty list

Output:

1Welcome World
2
3java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0

HashMap

A Map is a data structure that helps us in mapping Key and Value pairs. Similarly, in Java, we make use of HashMap, which hashes the Key by an index. By hashing, we will be able to access the Value by specifying the index.

Syntax for creating a HashMap:

1import java.util.HashMap; // Importing package
2
3HashMap<Integer, String> map1 = new HashMap<Integer, String>(); // Creating a HashMap object

Adding elements

HashMap is an important data structure, when mapping the key and the value helps access the elements with very little average time complexity of O(1). To map a key with a value, we can make use of the put(key, value) method.

The average time complexity for adding or accessing or removing an element using HashMap is O(1).

Example:

1map1.put(0, "A"); // Map (0, "A") and hash the key
2map1.put(1, "B"); // Map (1, "B") and hash the key
3System.out.println(map1); // OUTPUT: map1 = {0="A", 1="B"}

Output:

1{0=A, 1=B}

Updating elements

Similarly, when updating elements, we again can make use of the same method that we used when adding a new element.

Example:

1map1.put(0, "B"); // Map (0, "B") and hash the key
2map1.put(1, "C"); // Map (1, "C") and hash the key
3System.out.println(map1); // OUTPUT: map1 = {0="B", 1="C"}

Output:

1{0=B, 1=C}

Removing elements

When removing the mapping from the HashMap, we will make use of the remove(index) method to remove the value for the mentioned index.

Example:

1map1.remove(0); // Remove mapping (0, "B") from map1
2System.out.println(map1); // OUTPUT: map1 = {1="C"}

Output:

1{1=C}

Stack

A Stack is a linear data structure that is very similar to that of the ArrayList. But, it is based on the principle of Last-In-First-Out (LIFO). In simpler words, LIFO can be explained as whichever element is added last, must be removed first.

Since it is a linear data structure based on the LIFO principle, accessing the last element is not possible by specifying the index. The series of steps for accessing values at a particular index can be avoided by making use of the Stack data structure.

Syntax for building a Stack data structure:

1import java.util.Stack; // Import Stack package
2
3Stack<Integer> stack = new Stack<Integer>(); // Creating object for Stack

Adding elements

Adding elements is also known as "PUSH". Since the stack works only based on a single pointer, only 2 operations can be performed. To push a value into a Stack, we make use of the push(value) method.

Example:

1stack.push(10); // Push value 10 into Stack
2stack.push(11); // Push value 11 into Stack
3// OUTPUT: stack = [10, 11]

Removing elements

Similarly, to remove an element from Stack, we will make use of the pop() method. Here, we need not specify the index, since, by default, it removes the last added element, according to the principle.

Example:

1stack.pop(); // Removes 11 from Stack
2// OUTPUT: stack = [10]
3stack.pop() // Remove 10 from Stack
4// OUTPUT: EmptyStackException

If your Stack is empty i.e. (stack.size() == 0), then popping of elements is not possible. If you still proceed with the pop() method, then it would raise an exception called EmptyStackException.

Queue

Alternatively, the Queue is a linear data structure, that works on the First-In-First-Out (FIFO) principle. The element that is added first into a queue, should be removed first from the queue.

Syntax for creating Queue data structure:

1import java.util.Queue; // Import Queue package
2
3Queue<Integer> queue = new Queue<Integer>(); // Create new object

Adding elements

Adding elements to the queue can be done by making use of the add(value) method.

Example:

1queue.add(1); // 1 added to queue
2queue.add(2); // 2 added to queue
3// OUTPUT: queue = [1, 2]

Removing elements

In Queue, removing elements is referred to as "Polling". Polling can be performed on one end of the queue, called the "Rear" end. Similarly, adding can be performed on the opposite end called the "Front" end.

Example:

1queue.poll(); // Removes 1 from the queue
2// OUTPUT: queue = [2]

Conclusion

To conclude, we have learned about various built-in data structures available in Java. We have also learned how to work with them.

To summarize:

We learned about various built-in data structures.
We compared them with user-defined data structures.
We learned how to work with each built-in data structure.

Introduction to built-in data structures in Java

Table of contents

Introduction

Built-in vs. User-defined data structures

Data structures

ArrayList

Add elements

Update Elements

Removing elements

Linked lists

Adding elements

Updating elements

Removing elements

HashMap

Adding elements

Updating elements

Removing elements

Stack

Adding elements

Removing elements

Queue

Adding elements

Removing elements

Conclusion

Further reading