* Fast search and always sorted linked list (or array), Better than BST *
I bet you all know about how BST(Binary Search Tree) or Skip List works.
Here I want to present you another extremly simple way,
so that you can understand and implement by yourself very easily, with just simple linked list or even with array.
And with this way, you can be sure of your data will always sorted, with compact memory space,
gauranteed speed ( O(log N) ) always for all operations like add, delete, find.
1. Binary Search.
The first thing and the only thing you need to understand is how you can search an item fast in an Array
(or linked list).The Idea is simple. Let's say you have a 'pre-sorted' Linked list of integer with size 100 in ascending order,
and there you have numbers from 1 to 100 respectedly. Then how can you find a number 80 in there?Of course you can search the entire Linked list from the start to the end. But this way you will get O(N) performance.
The another way is like following.You go first the middle of an Linked list and compare the value with the value you want to find.
If the value in the Linked list is bigger than the value you want to find, then the value maybe in the right side
of the Linked list because the Linked list is already sorted.So we just need to check the right-half of the Linked list. Now go to the middle of that right-half of the Linked list.
If the value in that position is bigger than the value we want to find, then we check the right-half of
that portion of Linked list we are checking on. Go left if the value is smaller than the value to find.We continue this by minimizing the search scope till we reach to the 'un-dividable' position
(where the size of search area is 1 cell) and if we couldn't find any matching one, then it means
there is no such value in the Linked list. If we find the matching value in this process, then we can
stop.If you see the following image, you will soon get the picture.
[Fig-1. Binary search in an Linked list] // Later, I will post ;)
Now, let's think about the performance of this algorithm.
As you can see. we divide the search scope by half in every step. So we can find this will give
O(Log N) performance.
2. Add/Delete
Now, this search algorithm requires an Linked list which is already sorted. How can you maintain your Linked list
sorted whenever you add or delete an item?As you can guess, we don't need any complicated algorithm like rotation in AVL, or flagging in Red-Black Tree.
When we add an item into the Linked list, we just search the Linked list. And if there is the same value,
then we do nothing (or we even can add it if we can accept the same value -or Hash- of an item).
If we reached to the end of the step, then we are in the position in which the value is less than or
bigger than the value we want to add.If the value in the last position is bigger than the value we want to add, then we add it to the 'previous'
position in the Linked list. If not, then we add it to the right next position. That's all.
[Fig-2. Add an item] // Later, I will post ;)Deletion is also simple. If we found the position in which the value is the one we need to delete, then
we remove that item from the Linked list.By the way, this kind of 'Add'/'Delete' in a Linked list can be implemented in Array also with no problem.
So, basically this algorithm can be implemented by simple Array also.The performance for this Addition and deletion is also O(Log N) because adding or deleting an item from a list
is done in fixed time only once, we just need serch time. And the search time is O(Log N) as we saw above.
In the sample project, MySearchList is the class which does everything. For strong type checking, I made this
as generic class (which is same for Template in 'C++' language)
There are 3 major functions you need to know.
public int Add(T item);
public int Delete(T item);
public bool Contains(T item, ref int iLastIndex);
If you see the code, you will be disappointed that there is no such a complicated or long sophisticated code.
It's very simple, but strong and fast.
To identify each object, and to figure out whether an object maybe reside on the left or right side of the list,
I used the Hash code of an object.
And you will see that you can use a simple Array rather than List, just by modifying
'Count' property, and Insert(), RemoveAt(), GetAt(), SetAt() member functions.
In the main function of a Main Form, I tested the functionality of my class.
I add random numbers, but you can add numbers sequencially, which usually the bad case for normal BSTs so that
they have to reorganize the structure again. In my list class, such a complicated steps are not required.
If you run this sample in the debugger, you will see more detailed Trace information.
And finally I provided 'GetEnumerator()' for simple enumeration.
This is very simple to understand and implement, but with strong abilities like 'always sorted' 'High performance'
'minimized memory space'. And you can easily convert C# class to C++ Template class.
PS>>>
** Because this algorithm is not all difficult so maybe enormous developers already are using similar ways,
** and maybe there are already maby other similar posts on the Internet.
** I want to excuse that I didn't search the Internet.
** I just hope my article help someone who needed this.
| You must Sign In to use this message board. | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
