Data Structures for Android Developer

Bad programmers worry about the code. Good programmers worry about data structures and their relationships — Linus Torvalds
In this blog, I am going to cover all the data structures which are must for any Android Developers when it comes to cracking the interview and knowledge both.

What is a Data Structure(DS)?
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.
For example, we have some data which has, person name “ABC” and age 25. Here “ABC” is of String data type and 25 is of an integer data type. To maintain this user recode we need to use efficient DS.

Most used and most asked data structures in Android

• Array
• Linked List
• Hash Table
• Stack
• Queue
• Tree
• Graph

Array
Arrays are the most used and the easiest data structure that is used for storing the same kind of data. An array is a collection of similar items that are stored in contiguous memory locations.

You can access the elements of the array with the help of its indexes:

marks[0] // to access the 1st element i.e. element at index 0 

marks[2] // to access the 3rd element i.e. element at index 2 

marks[4] // to access the 5th element i.e. element at index 4

Some of the basic operations on Arrays:

• Insertion: Insert a given element at a particular index of the array
• Deletion: Delete a given element from the array
• Searching: Search for a particular element in the array
• Updation: Update an element of an array at a particular index
• Traversing: Print or traverse the whole array

Example on Array and other DS you can find from my Github profile.

Linked List

• A linked list is almost similar to an array i.e. 
• it is also a linear data structure to store the same kind of data. 
• Here, the data is not stored in a continuous manner(main difference from Array). 
• The data stored in the linked list is in the form of nodes 
• and each node can be connected to another node with the help of some pointers or reference to the next node

So, there are two parts of a node in a linked list i.e. the data part and the pointer or reference part.
The data part stores the data of the node, while the pointer or reference part stores the address of the next node(if any).

                                                     Example of the singly Linked list(above image) 

i.e. here we have the address of the next node only.
LinkedList Types

• “Doubly linked list”(address of the previous and next node is held by any node).
• “Circular linked list”

Some of the basic operations on Linked List:

• Insertion
• Deletion
• Searching
• Traversing

Example and question on linkedlist from my github prifile

Hash Table

• Hash Table used to store the data in the form of “Key-Value” pair
• Generate one key and with the help of that key, store the value in the Hash Table
• If the input is uniformly distributed then
• Hash Table will perform the insertion, deletion, and searching operation in O(1) time

The process of generating the key and storing the data based on that key is called “Hashing”.  To generate the key from the data, we need one function known as “Hash Function”.  The Hash Function will take the data as an input and give the key as the output.

For example, If the data to be stored is: 1, 2, 3, 4, 5, 26, 17 and the hash function used is:
hashFunction(k): k % 10
And the data will be stored in the Hash Table in the following way:

Points to think of while using Hash Table:
The Hash Function should be such that the keys generated are uniformly distributed.
The size of the Hash Table is dependent on the Hash Function. So, the choice of Hash Function should be done perfectly.
In the case of a collision in the Hash Table, apply proper collision handling technique.

Stack

• A Stack is a linear Data Structure that uses the Last In First Out order(LIFO) 
• i.e. the element inserted last will be popped out first. 

Example of a Stack

If you want to delete elements from the above Stack, then 5 will be deleted first, followed by 4, 3, 2, and 1.
Some of the basic operations on Stack:

• Push(): Push is used to insert an element at the top of the stack.
• Pop(): Pop is used to delete an element from the top of the stack.
• Top: Top is used to denote the top element of the stack.

Queue

• A Queue is a linear Data Structure that uses the First In First Out(FIFO) order
• i.e. the element coming first in the Queue will be deleted first from the Queue

In Queue, we have “Front” and “Rear”. The Front is used to point to the front element of the queue while the Rear is used to point to the rear element of the Queue.
Example of a Queue:

So, if you want to delete the elements from the above queue, then 1 will be deleted first, followed by 2, 3, 4, and 5.
Similarly, if you want to insert an element in the above queue then it will be inserted from the Rear and not from the Front.

Some of the basic operations on Queue:

• Enqueue(): Enqueue is used to insert an element at the end of the Queue.
• Dequeue(): Dequeue is used to delete an element from the front of the Queue.
• Front: It is used to denote the front element of the Queue.
• Rear: It is used to denote the Rear element of the Queue.

Tree

• A Tree is a non-linear, hierarchical Data Structure that is used to store data in the form of nodes
• All the nodes are connected with each other with the help of edges that are drawn between them
• A parent node can have no child or one child or more than one child
• But the child node can’t have more than one parent.

Example of Tree

Some of the terms related to trees are:

• Root: Root is the node that is present at the top of the tree. There can be only one root of a particular tree.
• Parent: All the nodes having at least one child is called the parent node.
• Child: The node below the parent node is called the child node of the parent node.
• Leaf: The node having zero children is called the leaf node.

Some of the types of trees are:

• General Tree
• Binary Tree
• Binary Search Tree
• AVL Tree
• Red-Black Tree
• N-ary Tree

Graph
it is a non-linear data structure that stores the data in the form of nodes and all the nodes are connected with each other with the help of edges.
The difference between trees and graphs is that there is a cycle in a Graph but there is no such cycle in case of a Tree.
A Graph consists of a finite set of nodes and a finite set of edges that are responsible for connecting the nodes.
Example of a Graph:

Tpes of Graph:

• Directed Graph: Here the edges will point to some node i.e. you will have an arrow pointing towards a node from a node.
• Undirected Graph: Here no arrow is there in between the nodes. The above example is an example of an undirected graph.

Some of the common Graph traversal techniques are:
Depth-First Search(DFS)
Breadth-First Search(BFS)

Thanks

Saurabh 

Happy Coding !!!!