As I had said in my last post, today we would be dealing with Linked Lists. Lets start off with the basics, what are linked lists and what is their use?
1)What are Linked-Lists?
Linked Lists are a collection of objects of the same data type that are linked to each other in a sequence. A linked-list is a sequential data-structure i.e the elements of a linked-list cannot be accessed randomly like that in an array.
2)What are the benefits of using Linked-Lists?
Now that you have seen that we cannot randomly access data in a linked list, you must be thinking why we really use a linked list. Well, that’s because the advantage of using linked-list overpowers its disadvantage. The major reason of using linked lists is its ability to support dynamic allocation.
In case of arrays, we allocate a fixed amount of memory and we cannot insert new data without overwriting the previous data, if the array is full. This is a major disadvantage in real world situations where the amount of data is unpredictable. To overcome this problem, Linked-Lists were introduced. Linked-Lists do not have a fixed memory allocated to them. So new data can come and join the sequence of the linked lists. Same is the case with deletion, once an element is deleted, the linked list shrinks leading to no memory wastage as in case of arrays.
TYPES OF LINKED LISTS:
There are 3 major types of linked lists, namely:
1) Singly Linked Lists– A singly linked list contains nodes, which have a data field and a next field, which contains a pointer to the next node.
The structure of a single linked list can be represented as:
struct list{
<data-type> data;
list *next;
};
2) Doubly Linked Lists – A doubly linked list consists of three fields: a data field, a next field, that contains a pointer to the next node in the list and a previous field that contains a pointer to the previous node in the list. So, we can traverse the list in both directions.
The structure of a doubly linked list can be represented as:
struct dlist{
<data-type> data;
dlist *prev;
dlist *next;
};
3)Circular Linked Lists – As the name suggests, a circular linked list is a singly linked list in which the last node’s next pointer points to the first node, thus making a loop/circle.
So where do you think linked lists are used in the real world?
Linked list are used typically in computer applications for memory allocations. The system keeps track of all the available memory with the help of a list(memory pool). So, whenever the user requests for memory, the system allocates memory to the user from the memory pool. Once allocated, the block of memory is deleted from the list. Once the user frees the memory, its added to the list again. So operations like malloc(),calloc() use linked lists internally.
Now, what are the questions that you should expect from linked lists in interviews?
1) To determine if a string is palindrome. Each character is a node in the list that is linked to the next one. Give the most efficient solution.
2)Remove duplicates from a string if:
a) You are allowed to use an additional data-structure.
b) No additional data-structure is allowed.
HINT- In the first case, make use of a hash table, inserting each character in the hash table, only if it has not been inserted earlier. If it has been already inserted, delete the node by changing the link of the previous node to point to the node next to the current one.
In this case,as we encounter each node, we check if its value is present in the nodes already encountered by us. If it is, we delete the node using the same procedure as above.
3)Find the nth to last element of a list.
HINT- Create two pointers p1 and p2 that point to the head of the list. Increment one of the pointers,say p2, by n times. Now increment both the pointers simultaneously till p2 reaches the end of the list. This means p1 points to the nth to last element of the list.
4)Given a corrupt circular linked list, write a program to return the beginning of the loop. A corrupt circular linked list is one in which there is a loop because of the last node pointing back to a node in the list,not necessarily the head of the list.
HINT- To solve this question, it’d help if you imagine a racetrack. If you are racing with someone and you are twice as fast as him, then you’d meet the person back at the starting point, as the time during which you run two laps, he’d have run one. If he underestimated your speed and gave you a k step head-start, then too you’d meet him, just not at the starting point this time, but at k steps from/before the starting point. We apply the same concept in our linked list.
We make use of two pointers,p1 and p2 where p1 will be slow runner and p2 will be fast runner(skips a node). We’ll give p2 a head start of k steps and then iterate p1 and p2 till they meet. As we know, the meeting point is k steps from the starting point, we place p1 back at the starting pint and move it simultaneously with p2. Both of them will meet at the starting point.
5) Implement malloc() and calloc().
These are the types of questions that are asked in linked lists. Your target should not only be to solve similar problems, but also to solve them optimally. The interviewers lay a great stress on optimization of code. The next topic will deal with trees and their importance.Till then, keep coding!!
Placement Corner 