Linear Data Structures
A Data structure is a data organization, management, and storage format that enables efficient access and modification.
Here’s an example to understand it better — Think of a dictionary. In a dictionary, words are organized alphabetically. This enables you to search for and find a word quickly and efficiently.
Data structures are broadly classified into — Linear and Non-Linear data structures. A Linear data structure is the one where elements are arranged in sequential order and each member element has a successor and predecessor [except for the first and last element respectively in certain cases] . They can be traversed in a single level and in a single run. Such data structures are easy to implement as computer memory is also sequential. However, the memory may not be utilized properly. Time complexity of linear data structure often increases with increase in size.
Examples of linear data structures are Linked List, Queue, Stack, Array, String etc.
Arrays
- An Array is a collection of data items having similar data types.
Let the size of the array be n.
- Accessing time of an element: O(1) [This is possible because it stores elements at contiguous locations]
- Search time of an element: O(n) for Sequential Search, O(log n) for Binary Search [If Array is sorted]
- Insertion of an Element: O(n) [The worst case occurs when insertion happens at the beginning of an array and requires shifting all of the elements]
- Deletion of an Element: O(n) [This worst case occurs when deletion occurs at the starting of an array and requires shifting all of the elements]
Sample Array-based coding questions in interviews:-
1.How do you find the missing number in a given integer array of 1 to 100?
2.How do you find duplicate numbers in an array if it contains multiple duplicates?
3.How do you find all pairs of an integer array whose sum is equal to a given number?
4.Maximum Subarray OR Largest Sum Contiguous Subarray Problem — Divide and Conquer
Linked Lists
- A Linked list is a collection of nodes, where each node has a data element and a reference to the next node in the sequence.
Types of Linked List -
Singly linked list
Singly linked list stores data and the reference to the next node or a null value.
Doubly linked list
It has two references, one for the last node and one for the previous node. This helps us traverse in both the directions and also we don’t need explicit permission for deletion of nodes.
Circular Linked List
All the nodes align to form a circle. There is no NULL at the end, it helps us to define any node as first and also helps to implement a circular queue.
- Accessing time of an element: O(n)
- Search time of an element: O(n)
- Insertion of an Element: O(1) [If we are at the position where we have to insert an element]
- Deletion of an Element: O(1) [If we know the address of node previous the node to be deleted]
The only drawback is that we cannot randomly access the nodes which were quite easy in arrays.
Sample Linked list-based coding questions in interviews:-
1.How do you check if two strings are anagrams of each other?
2.How do you find all the permutations of a string?
3.How do you check if a string contains only digits?
Advantages and disadvantages of Arrays over Linked Lists:-
Advantages:-
1. Random access is not possible in linked lists so traversal has to be done from the start. So, a binary search operation cannot be done.
2. Extra memory space with a pointer is required in the case of a linked list, this doesn’t apply to arrays.
Disadvantages:-
1. As an array’s size is fixed, we cannot insert elements more than size limit. Upper limit is to be known beforehand.
2.A new block has to be created to insert a new element which means the existing elements have to be shifted. Therefore, insertion is expensive.
Stack
- A Stack is a FILO (First In Last Out) data structure where the element that is added first will be deleted last.
It allows two operations — Push and Pop. Push allows us to add elements to the top while Pop allows removing the last element (removing the element at the top). Both operations can take place at the same end.
- Accessing time of an element: O(n)
- Search time of an element: O(n)
- Insertion of an Element: O(1)
- Deletion of an Element: O(1)
- Peek the top:- O(1)
It allows Insertion and Deletion on only one end.
Example:- As we navigate from one web page to another, those pages are placed on a stack. The current page is on the top and the first page we looked at is at the bottom of the stack. If we click on the back button, we begin to move in reverse order through the pages.(Popping each page).
Sample Stack-based coding questions in interviews:-
1.Infix to Postfix Conversion using Stack
2. Evaluation of postfix expression
3. Reverse a string using stack
4. Implement two stacks in an array
5. Check for balanced parentheses in an expression
Queues
- A Queue is a FIFO (First in First Out) data structure where the element that is added first will be deleted first.
It is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer.
- Accessing time of an element: O(n)
- Search time of an element: O(n)
- Insertion of an Element: O(1)
- Deletion of an Element: O(1)
Simple Queue
The simple queue is a normal queue where insertion takes place at the FRONT of the queue and deletion takes place at the REAR end of the queue.
Circular Queue
In a circular queue, the last node is connected to the first node.
Insertion in a circular queue happens at the FRONT and deletion at the REAR of the queue.
Priority Queue
In a priority queue, the nodes will have some predefined priority. Insertion is done in the order of arrival of the nodes. The node having the least priority will be removed first.
Dequeue (Doubly Ended Queue)
In a Double Ended Queue, insertion and deletion operations can be done at both FRONT and REAR of the queue.
Applications of Queue data structure :-
- CPU Task scheduling
- BFS algorithm to find shortest distance between two nodes in a graph.
- Website request processing
- Used as buffers in applications like MP3 media player, CD player, etc.
- Managing an Input stream
Sample Queue-based coding questions in interviews :-
- Chess Knight Problem | Find the shortest path from source to destination
- Spiral order traversal of a binary tree
- Find minimum passes required to convert all negative values in a matrix
- Convert a multilevel linked list to a singly linked list
- Check if an undirected graph contains a cycle or not
As you can see, each linear data structure has a number of different applications and uses. That said, having a basic understanding of data structures is a critical first step to becoming a good programmer. Whether you’re implementing data structures in Java or Python or C++, or studying for interview questions, understanding the most common data structures and how they work is the first step.
