Data structures

One of the commonly used interview question is - how do you reverse a linked list? If you talk about a recursive function to print the list in reverse order, you are so wrong. The question is to reverse the nodes of list. Not print the nodes in reverse order. So how do you go about reversing the nodes. You need to take each node and link it to previous node. But a singly linked list does not have previous pointer. So if n1 is current node, n2 = n1->next, you should set     n2->next = NULL But doing this would cut off the list at n2. So the solution is recursion. That is to reverse n nodes  n1,n2,n3... of a list, reverse the sub list from n2,n3,n4.... link n2->next to n1 set n1->next to NULL The last step is necessary because, once we reverse the list, first node must become last node and should be pointing to NULL. But now the difficulty is regarding the head? Where is head and how do we set it? Once we reach end of list  viz n1->next ==NULL, th...

You can download the complete program from here   Binary trees need to be traversed using recursion. All the three methods of traversal - inorder, preorder and post order methods employ recursion. Recursion needs stack storage. In cases where the tree is highly unbalanced, the cost on this traversal would be high. It would be nice where one could traverse a binary tree without using recursion. That is where a threaded tree comes into picture. This utilizes the pointers which are wasted on leaf nodes and uses these to save threads pointing to inorder successor or inorder predecessor. In the diagram above, node A does not have right child. Instead of NULL, a link to B is stored in A->right. Remember that B is the inorder successor of A. Similarly C does not have child nodes. So it has link to predecessor B as left thread and link to D as right thread. Only A has left link as NULL because A has no predecessor. And I has no successor, so it has right link as NULL. ...

Heap Heap is a special type binary tree where every node P is larger than its parent nodes. This is called max heap. In min heap, every node is smaller than its parent In case of max heap, the largest element is always available at the root of the tree. In min heap, the smallest element is at the root of the tree. A heap which is a complete binary tree is called binary heap. A complete binary tree is the one where each level of the tree is completely filled except for last level, which is filled from left to right. Array implementation of binary heap Because binary heap is a complete binary tree, it will be efficient store its elements in an array.  Such an array will have index of  parent and its children as follows. For every node with index i, the left child is at index 2i+1 and right child is at index 2i+2 In the diagram, a binary heap implemented using an array is shown. The indices are written next to each node. Heapify The process of rearranging the elements to maintain...

In my previous posts, we have seen what is queue data structure and how to implement it using linked list and array Is this queue full? But we have seen that the array implementation had some problem - it would say "Queue is full" even when the queue was not full. In the image above, there are 3 slots free in the begining of the array. But as back (rear) is equal to size of array -1, the program will say - queue is full. One way of overcoming this is to implement a circular queue. That is once end of array is reached, go back to beginning of array and insert elements there. Like this. Image courtesy: maxtudor.com  As can be seen in this diagram, once we reach end of array, next element 11 is inserted at the beginning of array. Then we continue from there. We can say that index = rear % MAX array[index] = new_element Similarly when dequeuing, we can say that index = front % MAX temp = array[index] That way, when front and rear exceed MAX, they continue from 0. Is the queue fu...

We have seen an introduction to Queue data structure and how to implement it using linked list. Now we shall try to implement the queue using an array. In linked list, front and rear were pointers to nodes with first element of the queue and last element of the queue respectively. In case of array, front is the  index of array which store first element of queue and rear is the index after the last element of the queue So how do we start the implementation. To start with set front and rear = 0 If front = rear, queue is empty. If rear = max , (max is size of array) queue is full enqueue If queue is not full set array[rear] to new value increment rear dequeue If queue is not empty set temp to array[front] increment front First let us write isEmpty() function which checks whether queue is empty by inspecting whether front is equal to rear int is_empty ( int front, int rear) { return front == rear; } Next to enqueue function we need to send array as a parameter, value to be in...

Queue is a linear data structure to which values are added and removed using FIFO method - first in first out. That is to say, the value which is added first, will be removed first from the queue. Exactly like the behavior of a real life queue. The other related data structure is stack, from which elements are added and removed using LIFO method - last in first out. Terminology An element is always added to the rear end of the queue. This operation is called enqueue .  An element is added from the front end of the queue. The operation of removing an element is called dequeue operation. Implementation of queue You can implement a queue using an array or a linked list. Array poses the problem that it is limited by its size. But by making the array as circular, queue can be implemented. Here when the array index reaches maximum value, queue insertion happens at the beginning of the array. But implementation of a queue with linked list is not having such limitations. If you just add o...