Posts

Tree data structure

Image
Tree Data structure Till now we have seen linear data structures such as arrays and linked lists. In these data structures, we had only one child following the previous parent. 5 is parent of 7 7 is parent of 3 3 is parent of 4 Tree are hierarchical data structures. Here each node can have multiple children. A popular implementation of Tree is a Binary tree where each node has at most 2 children (known as the left child and right child). The top most node is known as the root of the tree similar to the head node in a linked list.  The node directly above some node is called its parent. Application: Trees can are used in various applications that we see every day.  For example, the directory structure that we see in our operating systems (file explorer in Windows, finder in MacOS) is a great example of using tree where each folder is a node and each sub folder are its children, the files can be considered as leaf nodes i.e. the bottom most nodes in the tree whic
Post a Comment
Keep reading

Sieve of Eratosthenes (find prime numbers smaller than N)

Image
Given a number (n), find all the prime numbers smaller than or equal to n. Sieve of Eratosthenes is one of the most efficient algorithms to find all prime numbers smaller than or equal to n. when n is smaller than 10 million or so. A prime number is a number divisible only by itself and one. Example 13, 17, 7, etc. Algorithm: We use a boolean array which has a size of N i.e. arr[1...n]. We start from 2 and make the array value false for all the indexes which are multiples of 2. credits: GeeksForGeeks We find the next element in the array which is True. This is our next prime number i.e. 3. We make the array value false for all the indexes which are multiples of 3. credits: GeeksForGeeks And then again find the next True value which is the next prime number. We repeat this process until we reach n. At the end, all the values in the array which are True have a prime index value. Optimization: Rather than running the loop for prime p from (2*p to
Post a Comment
Keep reading

Sort a Linked List (Merge Sort)

Image
Given, a pointer to the head of a singly linked list, sort the linked list such that all nodes are arranged in non-decreasing order of their node values. Sorting a linked list Algorithm: We have already discussed Merge Sort on arrays . The approach will be similar in the case of linked lists as well. 1. Recursively Divide the list into two havles 2. Sort the two smaller halves. 3. Merge the two halves back together. We have also discussed how to find the middle node in a singly linked list .  The find middle node function will help us divide the linked list into two halves. Once the linked list is divided into two halves, we need to sort the sub-linked lists and merge them back together using the merging function. We will use a dummy node method to store the intermediate merged linked list whose head will be returned as result. Code in Python:  # Python program to perform Merge Sort on a Signly linked list # Node class class Node: # Constructor to initialise
Post a Comment
Keep reading

Segregate Even Odd value nodes in a linked list

Image
Given the head of a singly linked list, segregate even value nodes with odd value nodes such that all the even value nodes come before all the odd value nodes in the order of their appearance. Segregate Even and Odd value nodes Algorithm: Remember the pivot logic we used in QuickSort ? In QuickSort the pivot value was used to separate all the values which are smaller than pivot towards the left of the pivot and all the values greater than pivot value towards the right of the pivot. We will use a similar logic here. 1. Find the first even value node. 2. Bring this node to the start of the linked list. (Call it pivot) 3. Find the next even value node. 4. Insert this node after the pivot and increment pivot one node ahead. 5. Repeat this until we reach Null or None. The algorithm states to bring the first even value node to the start of the linked list and make a pointer pivot point towards it. Whenever we find an even value node, we need to link the previous node to
1 comment
Keep reading

Reverse alternate k nodes in a linked list

Image
Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in alternate groups of K nodes. Reversed alternate K nodes in a linked list Algorithm: We discussed Reversing a linked list in groups of K nodes in the previous post. The logic here is also the same, the only difference is that before the recursive call we traverse K more nodes so that we can skip them. """ Perform the skip after reversing the previous k nodes """ count = 0 # traverse the k nodes to be skipped while current is not None and count < k-1: current = current.next count += 1 Code in Python: # Python program to alternately reverse a linked list in group of given size k # Node class class Node: # Constructor to initialise data and next def __init__(self, data=None): self.data = data self.next = None class SinglyLinkedList: # Constructor to initialise head def __init__(self): self
Post a Comment
Keep reading

Reverse in groups of K nodes in a linked list

Image
Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in groups of K nodes. Reversing linked list in groups of 3 nodes Algorithm: Reversing K nodes can use the reverse linked list algorithm we discussed in an earlier post. Initialize: count = 0 current = head next = prev = None 1. while current does not become Null and count < k do: 2. reverse the linked list 3. end while 4. If there are further nodes left in the linked list 5. recursively call reverse linked list for next node 6. and store the returned value in head of the current call 7. return prev at each call as new head The algorithm is fairly simple, keep on reversing the linked list until k nodes are reversed or the linked list end. As you can see in the above diagram: After reversing A-B-C to C-B-A A that was earlier the head of the k nodes group should now point to the next reversed k nodes head which is F. To do this we have to first rever
Post a Comment
Keep reading

Remove cycle in a Linked List

Image
Given a pointer to the head of a singly linked list, whose last Node points to an intermediate node of the linked list, find and remove the cycle if it exists. As you can see in the image above, Node E's next pointer points to Node C. If we remove the cycle it will point to Null which is expected by a singly linked list. The problem can be divided into two parts: 1. Finding if the cycle exists 2. Removing the cycle Finding the cycle: We discussed Finding if a cycle exists in a linked list in our previous post. We would tweak the same function to remove the cycle. Removing the cycle: Once the fast pointer equals the slow pointer, there are two methods to remove the cycle: Method 1:  1. Count number of nodes present in the loop. Let the count be k. 2. Keep slow on the head and fast on the kth node from head. 3. Move both pointers at the same pace. 4. Stop the fast node when fast.next becomes equal to slow. 5. Make fast.next = None To count the number of nod
Post a Comment
Keep reading