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.
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
Source: The Balance
This article was published as a part of the Data Science Blogathon.
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.
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
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
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
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
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); }
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.
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.
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.
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.