Improving search speed in Singly Linked List
Improving search speed in Singly Linked List
Note: By improving search speed, we mean the search speed to retrieve an item located at 'nth' position.
We have previously discussed about Linked list in Linked list part 1.
In Linked list part 1 we primarily looked at the advantages and disadvantages of arrays, and tried to understand the importance of linked list. Additionally we even looked at 2 types of linked list, Singly Linked list and Doubly linked list in that post.
In this post we are primarily interested in Singly linked list, and we will like to discuss about how search speed can be improved in linked list, and we will further discuss about a paper in general.
Linked List: They are a logically connected sequential list of items. Logical connections can be defined as per our criteria, and use.
Indexing : It is a way to optimise the data structure by minimising the access to a particular item, it is used commonly in database. We can think of indexing as a table using which we can access nodes.
 |
| Fig.1 |
Fig.1 depicts index table used for retrieving information such as first element, last element and mid element.
Now back to our main topic, How can we improve the search speed in singly linked list?
We can improve it by assigning each node an index (id), which increases in ascending order. So if we know that the id's are ordered, we can simply make an index table pointing to the locations defined by us and then comparing the table elements with the index which we are searching for, thereby skipping most of the elements which we didn't include in the table, thereby increasing the search speed.
There are various indexing methods which we can apply, which include :
- Uniform Indexing
- Clustered Indexing
- Multi-level Indexing
- Indexing using Series
- Uniform Indexing : It adds a link in index table after every 'k' element. It is a good method and can be used for efficiently searching an element if we assume that the linked list will remain static, thereby we can find the optimal index position to minimise the time taken, but it is not the case in practical applications, as the reason we use linked list is due to its dynamic nature itself.
- Clustered Indexing : It uses properties of the elements, arranges them in clusters and thus reducing the load, it is a good method overall but defining what we will consider is hard in itself and so as the definition of cluster change, the speed of searching will change accordingly.
- Multi-level Indexing : Multi-level Indexing can be used to make a super fast linked list, but the disadvantage is its development complexity increases as the death of indexing increase. Refer for more information on multi-level Indexing
- Indexing using Series : Indexing using various series as the base to index, uses the properties of the series and thus can be used to make your linked list quite fast as compared to other methods while keeping the complexity of program development minimum. Speeding Up search in singly linked list using series .
Written By, Sarvesh Bhatnagar
