Linked list is an important data structure since it is used to implement other data structures or as a base for data management tasks. Data structures is one of the favorite subjects in Computer Science Job interviews. Here is a list of frequently asked basic Linked List Interview questions.
Linked List Interview Questions-Basics
Why Linked list is called a dynamic data structure?
Linked list is defined as a sequential list of elements called nodes. The nodes consist of data part and a link part. Link part stores the address of the next node of the linked list. Linked list is always followed or accessed from the first node. Linked list is dynamic due to these reasons.
- There is no need to define the size of a linked list.
- Memory is allocated when a new node is to be added. The new node can be added at any location without dislocating existing nodes. The nodes are added by updating the pointer of the new node with next node’s address and pointer of previous node with new node’s address.
- Any node can be added or deleted as and where required.
What are the differences between an Array and a Linked list?
- An array must be declared with a size specifying maximum number of elements that can be stored in it. A linked list does not require defining the number of nodes while declaration.
- Array insertion and deletion may lead to movement of existing elements that can increase the time taken for these operations. A linked list insertion does not affect location of the existing nodes. Only pointers are updated to do these operations.
- Array elements are identified by their indices or subscripts and so they are directly accessible. Linked list nodes are identified by their memory addresses and require traversal from the first node to reach a specific node. The reason is that a node contains the address of the next node.
Is Binary Search possible in a Linked list?
To answer this linked list interview question, you need to understand the concept of binary search. Binary search can only be done on sorted data where the middle element is directly accessible. In a linked list there is no provision to access the middle node as all nodes are identified by their memory locations stored in link parts of previous nodes.
The dynamic nature of a linked list makes it impossible to keep a track of the middle element. So, you cannot perform Binary Search on a Linked list.
What are the different kinds of Linked Lists?
- Linear Linked List
- Two-way/ Doubly Linked List
- Circular Linked List
- Header Linked List
- Circular Header linked list.
Explain concept of underflow and overflow?
Underflow and overflow are two conditions in any dynamic data structure.
- Underflow is associated with delete operation. It arises when deletion operation is performed on an empty data structure like a linked list with no nodes.
- Overflow occurs when an insertion operation is performed but no memory location is available to create a new node. Here the memory is not allocated when requested by the program using the language specific memory allocation function like malloc in C language.
What is a circular Linked List? Give its implementation examples.
In a circular linked list the link part of the last node stores the address of the first node of the linked list. In traversal or search operations the comparison of link part of current node will be done with the address of the first node and not with NULL value. The examples of circular linked list implementation are.
- Round robin execution in a job scheduler
- Slide show presentation with “loop until esc”
- Playlist execution.
- Browsing through opened applications.
This is the Part-1 of the Linked List Interview Questions. Do share any questions that are still unanswered for your!!!