Speeding Up Search in
Linked List

Fig.1 depicts index table used for retrieving information such as first element, last element and mid element.

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.

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:

1. Uniform Indexing
2. Clustered Indexing
3. Multi-level Indexing
4. 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 .