Data structures

Stack is a versatile data structure used in situations that need LIFO - last in first out. For an introduction to stack, read this post  Data members To implement a stack using an array, we will need an array and an index to the top of the stack.  We can have a static array or a dynamic array. Dynamic array has the advantage that size of array can be given at run time.  So let us have a dynamic array and also a data member called size. class stack { int max; int * arr; int top; public: stack( int n); void push ( int n); int pop (); bool is_empty (); bool is_full (); int peek (); ~ stack(); stack(stack & other); }; Methods In the constructor of this class we must initialize the data. We need to set top to -1, because we do not have any value in the stack currently. And as we are using dynamic array, we should allocate memory to array in the constructor. We need to also write a destru...

In the previous post we have seen how to implement a singly linked list in C++. Let us implement doubly linked list today. The difference between SLL and DLL is, DLL has two pointers in each node. One pointer points to next node and the other points to the previous node. Also, we can have two external pointers - one pointer to first node of list - head and the other pointer pointing to last node of the list - tail. So let us write structure node and class dlist. struct node { int val; struct node * next; struct node * prev; }; class d_list { private: node * head; node * tail; public: d_list(); void append ( int val); void display (); void insert_beg ( int n); node * find_node ( int n); bool delete_node ( int n); }; We have written a class with basic operations like append, display, find and delete etc. Two functions which are not needed when compared to linkedlist class are find_last() and find_previous(). Saves ...

A linked list is a versatile data structure. In this structure, values are linked to one another with the help of addresses. I have written in an earlier post about how to create a linked list in C.  C++ has a library - standard template library which has list, stack, queue etc. data structures. But if you were to implement these data structures yourself in C++, how will you implement? If you just use new, delete, cout and cin, and then claim it is your c++ program, you are not conforming to OOPS concept. Remember you have to "keep it together". Keep all the functions and variables together - in a class. You have to have class called linked list in which there are methods - append, delete, display, insert, find, find_last. And there will also be a data - head. Defining node We need a structure for all these nodes. A struct can be used for this purpose, just like C. struct node { int val; struct node * next; }; Next we need to define our class. W...

Question: Write a program to remove all duplicates from a singly linked list. For example, if the list is 2-->4--->5--->7--->2---->5--->25--->2 after deletion, the output must be something like this 2-->4-->5-->7-->25 An easy solution would be to take one node at a time, compare its value with all the other nodes, and delete if there is a match. But that would be expensive. A better solution is to sort the list and then compare adjacent values. Here is how we do it. Take a sorted list Compare a node with its previous node. If they have same value, delete the node Move to next node Repeat steps 2 to 4 until end of list But you should be careful in step 4. Because if you say, node->next, you may use a dangling pointer. For sorting the list, you can use any algorithm. Insertion sort is easiest for linked lists. Let us look at the code. void remove_duplicates (NODEPTR head) { head = sort_list(head); NODEPTR temp ...

Here was another interesting interview question on arrays How do you sort the array so that all the odd elements are before all the even elements. And both these subarrays must be sorted. We can first split the array so that all odd elements are in first subarray and all even elements come afterwards. Next we can use some sorting method to sort these two sub-arrays separately. Next comes the question. How do we split the array? For ith element in array, if it is even  remove the element from ith position move it to end of array Repeat this process for all elements from last to 0th Here is the code to split array into odd and even. int splitOddEven ( int * arr, int n) { int i; int evencount =0 ; for (i = n -1 ;i >=0 ;i -- ) { if (arr[i] %2==0 ) { move_extreme_right(arr,n,i); evencount ++ ; } } return evencount; } The function test whether arr[i] is even. If yes, to moves the element ...

Question: How do you find the merge point of two linked lists? Merge point is the first common node of two linked lists. From this node onwards, the lists have same nodes. Note: we are not talking about values in the nodes, but the actual addresses themselves. In the diagram shown, 4 is the merge point of the two lists. You may think that easy solution is traverse two list parallely and compare the respective nodes of the lists. But that does not work. In the diagram shown, if you start with head of list1 and list2, if you compare addresses of 1 and 5, then addresses of 2 and 6, addresses of 3 and 4 and so on, you will never find a match. An easy solution would be  to take one node at a time from first list and compare this with all nodes in second list. Then move on to second node of first list, compare it with all nodes of second list and so on. And continue this process until a match is found. But this process has a complexity of O(n 2 ). Another method will b...