Efficient search with removal I want to search from a given set of elements. Along with that I also want to remove that searched element. The problem is that the number of these queries is $q=O(n)$, where $n$ is the number of total elements. Which data structure should I use. Also, I want to avoid hashing.
Without any additional information about your setting or requirements, an obvious first choice is some self-balancing binary search tree, such as a red-black tree. It allows you to insert and remove elements in $O(\log n)$ time, where $n$ is the number of elements.

Following a standard engineering approach, try it out first. If it doesn't meet your requirements, analyze your situation more carefully, and try something else.