Android Developer should know these Data Structures for the next Interview session

Tram Ho

Introduce

Bad programmers worry about the code. Good programmers worry about data structures and their relationships – Linus Torvalds

That is so right. That is why every employer is looking for a candidate with a good understanding of Data Structure in interviews. The same is true for Android developers.

In this blog, we will mention all the Data Structure needed for any Android developer. While much remains to be learned, we will cover the most frequently used and frequently asked questions in Android Interviews.

Source: https://blog.mindorks.com/android-developer-should-know-these-data-structures-for-next-interview

What is Data Structure?

Data Structure is an organization format, management and storage of data that allows efficient access and modification.

More precisely, Data Structure is a collection of data values, the relationship between them and the functions or activities that can be applied to the data.

For example, we have some data for a person named “ABC” and age 25. Here, “ABC” has a String data type and 25 is an interger data type.

We can sort this data in the same form as the User record, which will have both username and age in it. We can now collect and store user records in a file or database as a data structure.

Now, let’s learn about the most used and commonly asked data structures in Android.

The most used and asked data structure in Android

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

Array

Arrays are the most used and easiest data structure to be used to store the same type of data. An array is a collection of similar items stored in contiguous memory locations.

For example, if you are storing scores of 10 students, you can do this by creating 10 integer variables for each student and you can store points in these variables. But you have to manage 10 different variables here, which is a very difficult task because if in the future you have to store 1000 points of students, then you have to create 1000 variables if you are following this method.

So we can use arrays for this purpose. All you need to do is create an array called marks of size 10 or 1000 or whatever and then store markers in that array.

NOTE: In almost all programming languages, we use a zero-based index, that is, the index of the array will start from 0 and go to n-1 where nn is the size of the array.

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

Some basic operations on the Array:

  • Insertion : Inserts a given element into a specific array index
  • Deletion : Delete a given element from the array
  • Searching : Searching for a specific element in an array
  • Updation : Updates an element of an array at a specific index
  • Traversing : Print or browse the whole array

Linked List

A Linked List is almost similar to an array, ie it is also a linear data structure to store the same type of data. Here, data is not stored continuously. The data stored in the list is linked 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 the linked list, ie the data part and the pointer or reference part. The data section stores the data of the node, while the cursor or reference section stores the address of the next node (if any). The image above is an example of a single Linked List, ie here we only have the address of the next node. There is another Linked list called “Doubly linked list”, in which the address of the previous node and the next node are kept by any node. In addition to these two types of linked lists, we also have a “Circular linked list”.

Here in the image above, Head is pointing to the first node of the linked list and the last node of the linked list is pointing to Null, that is, no node appears after that node.

Some basic operations on Linked List:

  • Insertion : Here, you can insert nodes into the linked list. You can insert nodes anywhere anywhere linked.
  • Deletion : In the delete operation, you delete the node from any node from the linked list.
  • Searching : You will be provided with an element and you must search for that element in the Linked list.
  • Traversing : Move the entire linked list to get each element of the Linked list.

Hash Table

Hash Table is a type of data structure used to store data in the form of Key-Value key pairs. You will have some values ​​or data and based on that data, you will generate a key and with the help of that key, you will store the value in the Hash Table. If the input is distributed evenly, the Hash Table will perform the insert, delete and search operation during O (1).

The process of generating keys and storing data based on that key is called Delete Hashing. To generate keys from data, we need a function called Hash Hash Function. The Hash function takes data as input and takes the key as output.

For example, if the data to be stored is: 1, 2, 3, 4, 5, 26, 17 and the hash used is:

And the data will be stored in the Hash Table in the following way: Points to think about when using Hash Table:

  • The Hash function must be such that the generated keys are distributed evenly.
  • The size of the Hash Table depends on the Hash Function. Therefore, the selection of the Hash Function should be done perfectly.
  • In case of a collision in the Hash Table, apply the appropriate collision handling technique.

Stack

A Stack is a linear data structure that uses the Last In First Out (LIFO) order, meaning that the last inserted element will be popped first. For example, if you put one book on top of the other books and continue this process in 50 books, the top book will be prefetched. Here you may notice that the top book is the last or recently placed book.

In Stack, we have a Top variable that denotes the vertex of the Stack. This is necessary because all stack operations are performed with the help of the Top variable.

The following is an example of Stack: If you want to remove elements from the Stack above, then 5 will be deleted first, followed by 4, 3, 2 and 1.

Some basic operations on the Stack:

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

Queue

Queue is a linear data structure using the First In First Out (FIFO) order, that is, the element that comes first in the Queue will be first deleted from the Queue. For example, while standing in line to book a ticket, the first person to book will first and the first person to book the ticket must stand at the end of the Queue.

In Queue, we have Front and Rear . Font is used to point to the front element of Queue while Rear is used to point to the rear element of Queue.

The following is an example of a Queue: So if you want to remove components from the queue above, 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, it will be inserted from Rear rather than Front .

Some basic operations on Queue:

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

Tree

Tree is a hierarchical, non-linear data structure, used to store data as nodes. Here, we have nodes and all nodes are connected to each other with the help of the edges drawn between them. A parent node may not have children or one or more children. But the child cannot have more than one parent.

The following is a simple example of a Tree: Some terms related to Tree are:

  • Root : Root is the node present at the top of the tree. There can only be one root of a particular tree.
  • Parent : All nodes with at least one child are called the parent node.
  • Child : The node below the parent node is called the parent node’s child node.
  • Leaf : A node without children is called a Leaf node. Some types of plants are:
  • General Tree
  • Binary Tree
  • Binary Search Tree
  • AVL Tree
  • Red-Black Tree
  • N-ary Tree

Graph

Graph is similar to Tree , ie it is also a non-linear data structure that stores data in the form of nodes and all nodes are connected to each other with the help of edges. The difference between Tree and Graph is that there is a cycle in Graph but there is no such cycle in the case of Tree .

The graph consists of a set of finite nodes and a set of finite edges responsible for connecting the nodes.

The following is an example of a graph:

Following are the chart types:

  • Directed Graph : Here the edges will point to some nodes, ie you will have an arrow pointing to a node from a node.
  • Undirected Graph : There are no arrows between nodes. The above example is an example of a scalar graph. Some common graph transmission techniques are:
  • Depth-First Search (DFS)
  • Breadth-First Search (BFS)

Conclude

Above is some knowledge about Data Structure, hope this article will help you have a successful interview ?

Share the news now

Source : Viblo