Introduction
Data structure go through answers for standard problems exhaustively and give you knowledge of the fact that utilizing every last one of them is so productive. It likewise shows you the study of assessing the proficiency of a calculation. This helps you to pick the best of different decisions in problem-solving. If you want to crack the interviews and get into a high-paying company, learning DSA is mandatory. It shows the ability of the candidate to problem-solving.
- Get the ability to analyze algorithms
- Using algorithms efficiently
- Storing data and maintaining it
- Understanding time and space complexities
A data structure is a capacity that is utilized to store and sort out information. It is an approach to organizing information on a PC with the goal that it tends to be gotten to and refreshed effectively. A data structure isn’t just utilized for putting together the information. It is utilized for handling, recovering, and putting away information. Different essential and high-level kinds of data structures are utilized in pretty much every program or programming framework that has been created.
A Linked List is a linear data structure similar to arrays. Instead of storing linked list elements in a contiguous location, pointers are used to connect the elements. They are made up of a series of linked nodes. Each node stores the data as well as the next node’s address. In this article, we will look at some linked list-related questions.
In this article, we will discuss some interview questions on data structures. And we will mainly focus on linked lists in this article. For entry-level, interviewers mostly ask basics, and the following questions may help you for your interviews.
Learning Objectives
In this article, you will learn
- About linked list data structure and how to use them.
- Different types of linked lists and how they are different from each other.
- Operations can be done using these linked lists.
- You will get to know how linked lists are different from arrays.
Source: The Balance
This article was published as a part of the Data Science Blogathon.
Table of Contents
- Explain About Linked List Data Structure
- Explain a Singly Linked List
- Explain a Doubly Linked List
- Explain a Circular Singly Linked List
- Explain a Circular Double-Linked List
- How to Convert a Binary Tree into the Doubly Linked List?
- What are the Operations That can be Done Using Linked Lists?
- Which Sorting Algorithm is Best for Linked Lists?
- What are the Differences Between Arrays and Linked Lists?
- How Many Changes do you Make to Insert a Node in the Middle of a Single-Line List?
- Conclusion
Data Structure Interview Questions
Q1. Explain About Linked List Data Structure.
Linked List: A linked list is a sequence of elements that are connected together via links. Each node contains a connection to another node. Here nodes are connected through the links.
A linked list is a chain of nodes, and every node points to another node. Linked lists are in the sequence they are created. These elements in the linked lists are not stored in the contiguous locations, but in arrays, elements are stored in the contiguous locations.
Q2. Explain a Singly Linked List.
Singly Linked List: Singly linked list is unidirectional from head to tail. The first node of the linked list is called the head, and the last node of the line list is called the tail. Basically, a node contains two fields. In the first field, data is stored, and in the second field, the address of the next node is stored, and thus they are linked. The null value is stored in the address field for the tail node.
For a single linked list, node structure is defined as,
struct node
{
int data;
struct node *link;
};
Here data type of data is an integer. The link stored the node’s address, so the datatype of the link is the struct node.
Source: GeeksForGeeks
Q3. Explain a Doubly Linked List.
Doubly Linked List: Doubly linked list has two-way data access. In the single-linked list, we can send control only in the forward direction, but in the double-linked list, we can send control in both forward and backward directions. Here for the double-linked list, a node has three fields. In the first field, the address of the previous node is stored. In the second field, data is stored, and in the third field, the address of the next field is stored. For double-linked list node structure is defined as:
struct node
{
int data;
struct node *left;
struct node *right;
};
Here the datatype of data is an integer. Left and right store the addresses of previous and next nodes, so the left and right data type is struct node.
Source: Javatpoint
Q4. Explain a Circular Singly Linked List.
Circular Singly linked list: Circular singly linked list is also similar to the singly linked list, but here the last node is connected to the first node, and so it is called circular. Like a single linked list, a circular linked list also has connected nodes, and the node has two fields. In the first field, data is stored, and in the second field, the address of the next node is stored. Node structure is similar to the node structure of the single linked list.
struct node
{
int data;
struct node *link;
};
Here data type of data is an integer. The link stored the node’s address, so the datatype of the link is the struct node.
Source: Javatpoint
Q5. Explain a Circular Double-Linked List.
Circular Doubly Linked List: A circular doubly linked list is similar to a doubly linked list. It is also two-way directional. We access it from both directions. But here, the last node is connected to the first node, which is called circular. Here also, nodes are connected. In each node, there are three fields. The first field address of the previous node is stored; in the second field, data is stored; and in the third field, the address of the next field is stored. The node structure is similar to the node structure of the double-linked list.
struct node
{
int data;
struct node *left;
struct node *right;
};
Here the datatype of data is an integer. Left and right store the addresses of previous and next nodes, so the left and right data type is struct node.
Source: Javatpoint
Q6. How to Convert a Binary Tree into the Doubly Linked List?
To convert the Binary tree into a doubly linked list, the previous and the next pointers of the linked list will be the left and the right child of the binary tree, and the order of nodes in the linked list will be in Inorder of the binary tree. The leftmost child of the binary tree will be the first element of the in order, and that will be the head node of the doubly linked list.
Source: Includehelp.com
Code:
void BinaryToDLL(Node *root, Node **head, Node **previous)
{
if (!root)
return;
//Conversion of left subtree
BinaryToDLL(root->left, head, previous);
if(*head == NULL)
*head = root;
else
{
root->left = *previous;
*previous->right = root;
}
*previous = root;
// Conversion of right subtree
BinaryToDLL(root->right, head, previous);
}
Q7. What are the Operations That can be Done Using Linked Lists?
Insertion: These operations are used to insert a node into the linked list. Insertion can be done at three positions.
1. Insertion at beginning
2. Insertion in middle
3. Insertion at the ending
Deletion: These operations are used to delete a node from the linked list. Here deletion means removing the link from the previous and next nodes.
Deletion can be done at three positions.
1. Deletion at beginning
2. Deletion in middle
3. Deletion at the ending
Traversing means starting from the head node and visiting all the nodes till the last node. In arrays, when we want to access any element we can access it directly using the index of the arrays, but for the linked list, we have to traverse from the first node to reach any element in the linked list.
Q8. Which Sorting Algorithm is Best for Linked Lists?
The most preferred algorithm for sorting a linked list is merge sort. The need for random access memory is low when we use merge sort. In linked lists, we can add elements in the middle anywhere in extra space and time complexities if the reference is given to the previous node. Here using the merge sort algorithm, we can implement the merge operation without any additional operation. And also, merge sort is a stable algorithm.
Q9. What are the Differences Between Arrays and Linked Lists?
- Arrays are the linear data structure in which elements are stored in contiguous memory locations, and for linked lists, nodes are connected, and memory locations are not contiguous. And for node, there are two fields. In the first field, data is stored, and in the second field memory location of the next node is stored. But for the double-linked list, the node has 3 fields. The first field contains the address of the previous node and the second field has data, and the third field has the address of the next node.
- The memory size of arrays is always fixed and should be determined first. At the same time, the memory size of linked lists is not fixed and can be allocated during runtime.
- Elements in an array are not dependent on each other, but the list’s nodes depend on each other.
- Accessing elements is fast with arrays and slow with linked lists.
- Operations like insertion and deletion are fast with the linked list and slow with arrays.
Q10. How Many Changes do you Make to Insert a Node in the Middle of a Single-Line List?
To insert a node in a single linked list in the middle, First, we have to traverse to that node where we have to insert a new node, and then,1. We have to change the address field of the previous node to the new node’s address.2. We have to change the new node’s address field to the next node’s address. So we have to make two changes to insert a new node in the middle of a linked list.
Conclusion
To conclude, we have discussed some questions that may ask in interviews. We mainly focussed on the linked list data structure. Starting with definitions of it, we went through operations and all. This is actually an important topic in data structures. Although there are some disadvantages, like memory usage as it uses high memory, for some operations, it is time-consuming, and its implementation is very complex. But still, there are many advantages to it.
- Linked lists use memory efficiently, so they are mostly preferred to arrays.
- Some data structures, like stacks and queues, are implemented using linked lists.
- It is a dynamic data structure, unlike arrays. No need to define size initially, and also it makes insertion and deletion operations easier as there is no shift in elements.
- These are usually preferred when working with large datasets.
- So learning it is very useful to ace data structure interviews.
Connect with me on Linkedin.
The media shown in this article is not owned by Analytics Vidhya and is used at the Author’s discretion.
This is Amrutha, I am pursuing B.Tech in the Computer science Department. I am interested in developing ML Models with python and Data Analysis. And also I have an interest in Web Development. I hope my articles in Analytics Vidhya help you to learn better. Thank you!!
