# Speeding Up Search in

Linked List

Linked list is a fundamental data structure which is used multitude of applications and can be used almost everywhere. It is a fundamental data structure using which multiple different datastructure can be formed.

**Fig. 1 - Linked List with Indexing**

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:

- 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
.*