Data structures

Question: Write a function to delete every k th node from circular linked list until only one node is left. This has a story associated with it. Flavius Josephus was Jewish Historian from 1st century. He and 40 other soldiers were trapped in a cave by Romans. They decided to kill themselves rather than surrendering to Romans. Their method was like this. All the soldiers will stand in a circle and every k th soldier will be shot dead. Josephus said to have calculated the starting point so that he would remain alive. So we have similar problem at hand. We delete every kth node in a circular list. Eventually only one node will be left. e.g. Let us say this is our list And we are deleting every third node.  We will delete 30. Then we delete 60. Next we delete 10. Next it will be 50. Next to be deleted is 20. Next 80. This continues. Implementation   We can count k-1 nodes and delete next node. This can be repeated in  a loop. What must be the termina...

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 ...

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...

Qn: Write a function to swap the adjacent nodes of a singly linked list.i.e. If the list has nodes as 1,2,3,4,5,6,7,8, after swapping, the list should be 2,1,4,3,6,5,8,7 Image from: https://tekmarathon.com Though the question looks simple enough, it is tricky because you don't just swap the pointers. You need to take care of links as well. So let us try to understand how to go about it. Take two adjacent nodes p1 and p2 Let prevnode be previous node of p1 Now link prevnode to p2 Link p2 to p1 Link p1 to next node of p2 So the code will be prevnode -> next = p2; p1 -> next = p2 -> next; p2 -> next = p1; But what about the start node or head? head node does not have previous node If we swap head with second node, modified head should be sent back to caller  To take care of swapping first and second nodes, we can write p1 = head; p2 = head -> next; p1 -> next = p2 -> next; p2 -> next = p1; head = p2;  Now we are...

Sorting a linked list is much more complex than sorting an array. Because you need to be wary of links at each step and update them. The most convenient ways of sorting a linked list is insertion sort, where in you remove one node at a time from list and insert them to the sorted list in correct position. But merge sorting a linked list uses another approach. It splits the list into two halves, sorts them recursively and then merges them maintaining ascending order of key values. So the three basic parts of this approach are Splitting the list into two halves of equal length Sorting these halves Merging the halves Step 2 is in fact not needed if the list has only one node. One node is sorted. Hence the merge sort algorithm is If the list has more than one node Splitting the list into two halves of equal length Sorting these halves recursively using steps 2 to 4 Merging the halves   Split the list into halves We have seen in this post how to find the m...

Now let us write a function to count the number of nodes in a singly linked list. This one is pretty simple. traverse the list from first node increment count after each node count at the end of traversal is the number of nodes int get_count (NODEPTR temp) { int c = 0 ; while (temp) { c ++ ; temp = temp -> next; } return c; } The function starts with head node and loops till temp becomes NULL. Please remember that NULL has a numerical value of 0 and 0 is false and the condition ( temp ) is as good as saying ( temp!=NULL ). How about a recursive function for the same? int get_count_recursive (NODEPTR temp) { if (temp != NULL ) { return get_count_recursive(temp -> next) +1 ; } } Time to write the driver program for this function #include<stdio.h> #include<stdlib.h> struct node { int n; struct node * next; }; typedef struct node * NODEPTR; NODEPTR...

A stack data structure is a versatile data structure which is useful whenever we want output to be reverse of input, or we want a LIFO - last in first out behavior Image from Wikipedia . A function call in most languages employs a stack. The parameters and local variables are pushed to call stack. And a return statement pops out most recent call stack. Similarly when we want to check if an expression has balanced brackets, we can use a stack to store brackets. Top of stack:  Unlike a linked list where elements can be added to the end of list or beginning of a list, values are always added to the top of the stack. Just like a plate is added to the top of a stack of plates. And a value is always removed from top of the stack - similar to a stack of plates again. A stack abstract data type should define three functions push - push function inserts a value at the top of stack  pop - pop function removes a value from top of stack isempty - isempty function checks if the stack is em...