Here you will get some basic and advance linked list interview questions and answers.
Linked lists happen to have very complex interview questions. They are generally small, powerful but if you fully don’t understand the principles they become complicated. Your code solutions that include linked listings are speedy and smaller.
1. What is a Linked list?
Linked list is an ordered set of data elements, each containing a link to its successor (and typically its predecessor).
2. Can you represent a Linked list graphically?
The fundamental data structure for the linked record involves 3 segments: the data itself and also the link to another element. Together (data + link) this particular structure is normally called the Node.
3. How many pointers are required to implement a simple Linked list?
You can find generally 3 pointers engaged:
- A head pointer, pointing to the start of the record.
- A tail pointer, pointing on the last node of the list. The key property in the last node is that its subsequent pointer points to nothing at all (NULL).
- A pointer in every node, pointing to the next node element.
4. How many types of Linked lists are there?
Singly linked list, doubly linked list, multiply linked list, Circular Linked list.
5. How to represent a linked list node?
The simplest representation of a linked list node is wrapping the data and the link using a typedef structure and giving the structure as a Node pointer that points to the next node. An example representation in C is
|
1 2 3 4 5 6 |
/*ll stands for linked list*/ typedef struct ll { int data; struct ll *next; } Node; |
6. Describe the steps to insert data at the starting of a singly linked list.
Inserting data at the beginning of the linked list involves creation of a new node, inserting the new node by assigning the head pointer to the new node next pointer and updating the head pointer to the point the new node. Consider inserting a temp node to the first of list
|
1 2 3 4 5 6 7 8 9 10 11 |
Node *head; void InsertNodeAtFront(int data) { /* 1. create the new node*/ Node *temp = new Node; temp->data = data; /* 2. insert it at the first position*/ temp->next = head; /* 3. update the head to point to this new node*/ head = temp; } |
7. How to insert a node at the end of Linked list?
This case is a little bit more complicated. It depends on your implementation. If you have a tail pointer, it’s simple. In case you do not have a tail pointer, you will have to traverse the list till you reach the end (i.e. the next pointer is NULL), then create a new node and make that last node’s next pointer point to the new node.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
void InsertNodeAtEnd(int data) { /* 1. create the new node*/ Node *temp = new Node; temp->data = data; temp->next = NULL; /* check if the list is empty*/ if (head == NULL) { head = temp; return; } else { /* 2. traverse the list till the end */ Node *traveller = head; while (traveler->next != NULL) traveler = traveler->next; /* 3. update the last node to point to this new node */ traveler->next = temp; } } |
8. How to insert a node in random location in the list?
As above, you’d initial produce the new node. Currently if the position is one or the list is empty, you’d insert it initially position. Otherwise, you’d traverse the list until either you reach the specified position or the list ends. Then you’d insert this new node. Inserting within the middle is that the difficult case as you have got to make sure you do the pointer assignment within the correct order. First, you’d set the new nodes next pointer to the node before that the new node is being inserted. Then you’d set the node to the position to purpose to the new node. Review the code below to get an idea.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
void InsertNode(int data, int position) { /* 1. create the new node */ Node *temp = new Node; temp->data = data; temp->next = NULL; /* check if the position to insert is first or the list is empty */ if ((position == 1) || (head == NULL)) { // set the new node to point to head // as the list may not be empty temp->next = head; // point head to the first node now head = temp; return; } else { /* 2. traverse to the desired position */ Node *t = head; int currPos = 2; while ((currPos < position) && (t->next != NULL)) { t = t->next; currPos++; } /* 3. now we are at the desired location */ /* 4 first set the pointer for the new node */ temp->next = t->next; /* 5 now set the previous node pointer */ t->next = temp; } } |
9. How to delete a node from linked list?
- The following are the steps to delete node from the list at the specified position.
Set the head to point to the node that head is pointing to. - Traverse to the desired position or till the list ends; whichever comes first
- You have to point the previous node to the next node.
10. How to reverse a singly linked list?
- First, set a pointer (*current) to point to the first node i.e. current=head.
- Move ahead until current!=null (till the end)
- set another pointer (*next) to point to the next node i.e. next=current->next
- store reference of *next in a temporary variable (*result) i.e. current->next=result
- swap the result value with current i.e. result=current
- And now swap the current value with next. i.e. current=next
- return result and repeat from step 2
- A linked list can also be reversed using recursion which eliminates the use of a temporary variable.
11. Compare Linked lists and Dynamic Arrays
A dynamic array is a data structure that allocates all elements contiguously in memory, and keeps a count of the present number of elements. If the area reserved for the dynamic array is exceeded, it’s reallocated and traced, a costly operation.
Linked lists have many benefits over dynamic arrays. Insertion or deletion of an element at a specific point of a list, is a constant-time operation, whereas insertion in a dynamic array at random locations would require moving half the elements on the average, and all the elements in the worst case.
Whereas one can delete an element from an array in constant time by somehow marking its slot as vacant, this causes fragmentation that impedes the performance of iteration.
12. What is a Circular Linked list?
In the last node of a singly linear list, the link field often contains a null reference. A less common convention is to make the last node to point to the first node of the list; in this case the list is said to be ‘circular’ or ‘circularly linked’.
13. What is the difference between singly and doubly linked lists?
A doubly linked list whose nodes contain three fields: an integer value and two links to other nodes one to point to the previous node and other to point to the next node. Whereas a singly linked list contains points only to the next node.
14. What are the applications that use Linked lists?
Both stacks and queues are often implemented using linked lists, other applications are skip list, binary tree, unrolled linked list, hash table, heap, self-organizing list.
15. How to remove loops in a linked list (or) what are fast and slow pointers used for?
The best solution runs in O(N) time and uses O(1) space. This method uses two pointers (one slow pointer and one fast pointer). The slow pointer traverses one node at a time, while the fast pointer traverses twice as fast as the first one. If the linked list has loop in it, eventually the fast and slow pointer will be at the same node. On the other hand, if the list has no loop, obviously the fast pointer will reach the end of list before the slow pointer does. Hence we detect a loop.
16. What will you prefer to use a singly or a doubly linked lists for traversing through a list of elements?
Double-linked lists require more space per node than singly liked lists, and their elementary operations such as insertion, deletion are more expensive; but they are often easier to manipulate because they allow fast and easy sequential access to the list in both directions. On the other hand, doubly linked lists cannot be used as persistent data structures. So, for traversing through a list of node, doubly linked list would be a better choice.
If you found any mistake in above linked list interview questions and answers then please mention it by commenting below.
